×

Strongly unforgeable ring signature scheme from lattices in the standard model. (English) Zbl 1442.94053

Summary: In a ring signature scheme, a user selects an arbitrary ring to be able to sign a message on behalf of the ring without revealing the signer’s identity. Whistle-blowers especially find this useful. To date, various ring signature schemes have been proposed, all considered to be secure as existentially unforgeable with respect to insider corruption; that is, an adversary who chooses ring-message pairs for which he requests signatures, corrupts honest users, and obtains their signing keys can not produce forgeries for new ring-message pairs. Lattice-based ring signature schemes offer lower computational overhead and security from quantum attacks. In this paper, we offer a lattice-based scheme. We begin by showing that the existing ring signature schemes are not sufficiently secure, because existential unforgeability still permits a signer to potentially produce a new signature on previously signed messages. Furthermore, we show that existing ring signature schemes from lattices are not even existentially unforgeable with respect to insider corruption. We then improve previous schemes by applying, for the first time, the concept of strong unforgeability with respect to insider corruption to a ring signature scheme in lattices. This offers more security than any previous ring signature scheme: adversaries cannot produce new signatures for any ring-message pair, including previously signed ring-message pairs.

MSC:

94A62 Authentication, digital signatures and secret sharing
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Rivest, R. L.; Shamir, A.; Tauman, Y.; Boyd, C., How to leak a secret, Advances in Cryptology—ASIACRYPT 2001. Advances in Cryptology—ASIACRYPT 2001, Lecture Notes in Computer Science, 2248, 552-565 (2001), Berlin, Germany: Springer, Berlin, Germany
[2] Dodis, Y.; Kiayias, A.; Nicolosi, A.; Shoup, V.; Cachin, C.; Camenisch, J., Anonymous identification in ad hoc groups, Advances in Cryptology—EUROCRYPT 2004. Advances in Cryptology—EUROCRYPT 2004, Lecture Notes in Computer Science, 3027, 609-626 (2004), Berlin, Germany: Springer, Berlin, Germany
[3] Fiat, A.; Shamir, A.; Odlyzko, A. M., How to prove yourself: practical solutions to identification and signature problems, Advances in Cryptology—CRYPTO ’86. Advances in Cryptology—CRYPTO ’86, Lecture Notes in Computer Science, 263, 186-194 (1987), Berlin, Germany: Springer, Berlin, Germany · Zbl 0636.94012
[4] Bender, A.; Katz, J.; Morselli, R., Ring signatures: stronger definitions, and constructions without random oracles, Journal of Cryptology, 22, 1, 114-138 (2009) · Zbl 1163.94431
[5] Shacham, H.; Waters, B.; Okamoto, T.; Wang, X., Efficient ring signatures without random oracles, Public Key Cryptography—PKC 2007. Public Key Cryptography—PKC 2007, Lecture Notes in Computer Science, 4450, 166-180 (2007), Berlin, Germany: Springer, Berlin, Germany · Zbl 1127.94027
[6] Wang, C.-H.; Liu, C.-Y., A new ring signature scheme with signer-admission property, Information Sciences, 177, 3, 747-754 (2007) · Zbl 1130.94330
[7] Jeong, I. R.; Kwon, J. O.; Lee, D. H., Ring signature with weak linkability and its applications, IEEE Transactions on Knowledge and Data Engineering, 20, 8, 1145-1148 (2008)
[8] Chow, S. S. M., Blind signature and ring signature schemes: rehabilitation and attack, Computer Standards & Interfaces, 31, 4, 707-712 (2009)
[9] Hwang, J. Y., A note on an identity-based ring signature scheme with signer verifiability, Theoretical Computer Science, 412, 8-10, 796-804 (2011) · Zbl 1208.94057
[10] Melchor, C. A.; Cayrel, P.-L.; Gaborit, P.; Laguillaumie, F., A new efficient threshold ring signature scheme based on coding theory, IEEE Transactions on Information Theory, 57, 7, 4833-4842 (2011) · Zbl 1365.94396
[11] Zeng, S.; Jiang, S.; Qin, Z., An efficient conditionally anonymous ring signature in the random oracle model, Theoretical Computer Science, 461, 106-114 (2012) · Zbl 1259.94065
[12] Shor, P. W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, 26, 5, 1484-1509 (1997)
[13] Gentry, C.; Peikert, C.; Vaikuntanathan, V.; Dwork, C., Trapdoors for hard lattices and new cryptographic constructions, Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC ’08) · Zbl 1231.68124
[14] Buchmann, J.; Lindner, R.; Rückert, M.; Schneider, M., Post-quantum cryptography: lattice signatures, Computing, 85, 1-2, 105-125 (2009) · Zbl 1170.94010
[15] Cash, D.; Hofheinz, D.; Kiltz, E.; Peikert, C., Bonsai trees, or how to delegate a lattice basis, Journal of Cryptology, 25, 4, 601-639 (2012) · Zbl 1277.94017
[16] Boyen, X.; Nguyen, P. Q.; Pointcheval, D., Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more, Public Key Cryptography—PKC 2010. Public Key Cryptography—PKC 2010, Lecture Notes in Computer Science, 6056, 499-517 (2010), Berlin, Germany: Springer, Berlin, Germany · Zbl 1281.94074
[17] Rückert, M.; Sendrier, N., Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles, Post-Quantum Cryptography. Post-Quantum Cryptography, Lecture Notes in Computer Science, 6061, 182-200 (2010), Berlin, Germany: Springer, Berlin, Germany · Zbl 1286.94085
[18] Micciancio, D.; Peikert, C.; Pointcheval, D.; Johansson, T., Trapdoors for lattices: simpler, tighter, faster, smaller, Advances in Cryptology—EUROCRYPT 2012. Advances in Cryptology—EUROCRYPT 2012, Lecture Notes in Computer Science, 7237, 700-718 (2012), Berlin, Germany: Springer, Berlin, Germany · Zbl 1297.94090
[19] Brakerski, Z.; Kalai, Y. T., A framework for efficient signatures, ring signatures and identity based encryption in the standard model
[20] Cayrel, P.; Lindner, R.; Rückert, M.; Silva, R.; Abdalla, M.; Barreto, P. S. L. M., A lattice-based thresh-old ring signature scheme, Progress in Cryptology—LATINCRYPT 2010. Progress in Cryptology—LATINCRYPT 2010, Lecture Notes in Computer Science, 6212, 255-272 (2010), Berlin, Germany: Springer, Berlin, Germany · Zbl 1285.94046
[21] Wang, J.; Sun, B.; Qing, S.; Susilo, W.; Wang, G.; Liu, D., Ring signature schemes from lattice basis delegation, Information and Communications Security. Information and Communications Security, Lecture Notes in Computer Science, 7043, 15-28 (2011), Berlin, Germany: Springer, Berlin, Germany
[22] Aguilar Melchor, C.; Bettaieb, S.; Boyen, X.; Fousse, L.; Gaborit, P.; Youssef, A.; Nitaj, A.; Hassanien, A. E., Adapting Lyubashevsky’s signature schemes to the ring signature setting, Progress in Cryptology—AFRICACRYPT 2013. Progress in Cryptology—AFRICACRYPT 2013, Lecture Notes in Computer Science, 7918, 1-25 (2013), Berlin, Germany: Springer, Berlin, Germany · Zbl 1312.94108
[23] An, J. H.; Dodis, Y.; Rabin, T.; Knudsen, L. R., On the security of joint signature and encryption, Advances in Cryptology—EUROCRYPT 2002. Advances in Cryptology—EUROCRYPT 2002, Lecture Notes in Computer Science, 2332, 83-107 (2002), Berlin, Germany: Springer, Berlin, Germany
[24] Boneh, D.; Boyen, X.; Cachin, C.; Camenisch, J., Short signatures without random oracles, Advances in Cryptology—EUROCRYPT 2004. Advances in Cryptology—EUROCRYPT 2004, Lecture Notes in Computer Science, 3027, 56-73 (2004), Berlin, Germany: Springer, Berlin, Germany
[25] Boneh, D.; Shen, E.; Waters, B.; Yung, M.; Dodis, Y.; Kiayias, A.; Malkin, T., Strongly unforgeable signatures based on computational Diffie-Hellman, Public Key Cryptography—PKC 2006. Public Key Cryptography—PKC 2006, Lecture Notes in Computer Science, 3958, 229-240 (2006), Berlin, Germany: Springer, Berlin, Germany
[26] Ajtai, M.; Miller, G. L., Generating hard instances of lattice problems, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC ’96)
[27] Micciancio, D.; Regev, O., Worst-case to average-case reductions based on Gaussian measures, SIAM Journal on Computing, 37, 1, 267-302 (2007) · Zbl 1142.68037
[28] Peikert, C.; Rosen, A.; Halevi, S.; Rabin, T., Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices, Theory of Cryptography. Theory of Cryptography, Lecture Notes in Computer Science, 3876, 145-166 (2006), Berlin, Germany: Springer, Berlin, Germany
[29] Banaszczyk, W., New bounds in some transference theorems in the geometry of numbers, Mathematische Annalen, 296, 1, 625-635 (1993) · Zbl 0786.11035
[30] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2009), London, UK: The MIT Press, London, UK
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.