Abstract
We present a framework for building practical anonymous credential schemes based on the hardness of lattice problems. The running time of the prover and verifier is independent of the number of users and linear in the number of attributes. The scheme is also compact in practice, with the proofs being as small as a few dozen kilobytes for arbitrarily large (say up to \(2^{128}\)) numbers of users with each user having several attributes. The security of our scheme is based on a new family of lattice assumptions which roughly states that given short pre-images of random elements in some set S, it is hard to create a pre-image for a fresh element in such a set. We show that if the set admits efficient zero-knowledge proofs of knowledge of a commitment to a set element and its pre-image, then this yields practically-efficient privacy-preserving primitives such as blind signatures, anonymous credentials, and group signatures. We propose a candidate instantiation of a function from this family which allows for such proofs and thus yields practical lattice-based primitives.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
It is of course possible to construct these schemes using succinct zero-knowledge proofs such as STARKs, but the cost of these constructions appears to be in the hundreds of kilobytes range.
- 2.
Note that \(x'\) can be equal to one of the x, as long as \(\vec {s}'\ne \vec {s}\).
- 3.
We will also want the set [N] to be exponentially large so that there is a negligible chance of obtaining pre-images on the same f(x).
- 4.
Still, investigating this stronger assumption with appropriate functions f could be an interesting research direction. The one-more-ISIS assumption in [3] does allow the adversary access to an oracle to obtain pre-images of arbitrary vectors, but requires him to find pre-images for a random set of vectors to win the game.
- 5.
For example, the expected squared norm of a 512-dimensional Gaussian of standard deviation \(\sigma \) is \(512\sigma ^2\). The probability that the sum of three such Gaussians have squared norm less than this is less than \(2^{-160}\).
- 6.
This implies that the scheme would be instantiated over some polynomial ring rather than \(\mathbb {Z}_p\), as in the description in this section. But since \(\mathbb {Z}_p\) is a sub-ring of the polynomial ring, all operations in the polynomial ring can also be described as operations over vectors over \(\mathbb {Z}_p\), and so the description in this section is actually more general than we will need to be.
- 7.
The blind signature protocol of [10] does require a zero-knowledge proof involving \(\textsf{H}(\cdot )\), but this proof is only done in the intermediate interaction between the user and the signer, and so its relative inefficiency does not affect the signature size.
- 8.
This is similar to how the SIS and LWE problems were first introduced – solving their random instances was shown to be as hard as solving lattice problems in the worst case [4, 48, 53], but now the SIS and LWE problems are used with parameters which do not satisfy these original reductions because these problems have since been very well-studied on their own.
- 9.
- 10.
We recall the skew-circulant matrices and the function \(\textsf{rot}\) in Sect. 2.
- 11.
Obviously, one could try to use ILP for smaller \(k\) to decrease the bound on \(\textbf{s}^*\).
- 12.
The signature should also contain a verifiable encryption of i using the opener’s public key.
References
Agrawal, S., Boneh, D., Boyen, X.: Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 98–115. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_6
Agrawal, S., Stehlé, D., Yadav, A.: Towards practical and round-optimal lattice-based threshold and blind signatures. IACR Cryptol. ePrint Arch., p. 381 (2021)
Agrawal, S., Kirshanova, E., Stehlé, D., Yadav, A.: Practical, round-optimal lattice-based blind signatures (2022)
Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: STOC, pp. 99–108 (1996)
Albrecht, M.R., Cini, V., Lai, R.W.F., Malavolta, G., Thyagarajan, S.A.: Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable. In: Dodis, Y., Shrimpton, T. (eds) CRYPTO 2022. LNCS, vol. 13508. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_4
Attema, T., Lyubashevsky, V., Seiler, G.: Practical product proofs for lattice commitments. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 470–499. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_17
Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen 296(1): 625–635 (1993). ISSN 1432–1807. https://doi.org/10.1007/BF01445125. https://doi.org/10.1007/BF01445125
Bellare, M., Micciancio, D., Warinschi, B.: Foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 614–629. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_38
Beullens, W., Seiler, G.: Labrador: compact proofs for R1CS from module-sis. IACR Cryptol. ePrint Arch., p. 1341 (2022)
Beullens, W., Lyubashevsky, V., Nguyen, N.K., Seiler, G.: Lattice-based blind signatures: Short, efficient, and round-optimal. Cryptology ePrint Archive, Paper 2023/077 (2023). https://eprint.iacr.org/2023/077. https://eprint.iacr.org/2023/077
Bootle, J., Lyubashevsky, V., Seiler, G.: Algebraic techniques for short(er) exact lattice-based zero-knowledge proofs. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 176–202. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_7
Bootle, J., Delaplace, C., Espitau, T., Fouque, P.-A., Tibouchi, M.: LWE without modular reduction and improved side-channel attacks against BLISS. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11272, pp. 494–524. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03326-2_17
Bos, J.W., et al.: CRYSTALS - kyber: a cca-secure module-lattice-based KEM. In: 2018 IEEE European Symposium on Security and Privacy, EuroS &P, pp. 353–367 (2018)
Boschini, C., Takahashi, A., Tibouchi, M.: Musig-l: Lattice-based multi-signature with single-round online phase. Cryptology ePrint Archive, Paper 2022/1036 (2022). https://eprint.iacr.org/2022/1036. https://eprint.iacr.org/2022/1036
Boudgoust, K., Jeudy, C., Roux-Langlois, A., Wen, W.: Towards classical hardness of module-LWE: the linear rank case. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 289–317. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_10
Camenisch, J., Drijvers, M., Lehmann, A.: Anonymous attestation using the strong Diffie Hellman assumption revisited. In: Franz, M., Papadimitratos, P. (eds.) Trust 2016. LNCS, vol. 9824, pp. 1–20. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45572-3_1
Camenisch, J., Lysyanskaya, A.: A signature scheme with efficient protocols. In: Cimato, S., Persiano, G., Galdi, C. (eds.) SCN 2002. LNCS, vol. 2576, pp. 268–289. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36413-7_20
Chaum, D.: Security without identification: transaction systems to make big brother obsolete. Commun. ACM 28(10), 1030–1044 (1985). https://doi.org/10.1145/4372.4373. https://doi.org/10.1145/4372.4373
Chen, L.: Access with pseudonyms. In: Dawson, E., Golić, J. (eds.) CPA 1995. LNCS, vol. 1029, pp. 232–243. Springer, Heidelberg (1996). https://doi.org/10.1007/BFb0032362
Damgård, I.B.: Payment systems and credential mechanisms with provable security against abuse by individuals. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 328–335. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_26
Ducas, L., Lyubashevsky, V., Prest, T.: Efficient identity-based encryption over NTRU lattices. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 22–41. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_2
Ducas, L., Nguyen, P.Q.: Learning a zonotope and more: cryptanalysis of NTRUSign countermeasures. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 433–450. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_27
Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehlé, D.: Crystals-dilithium: a lattice-based digital signature scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018(1), 238–268 (2018)
Esgin, M.F., Nguyen, N.K., Seiler, G.: Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 259–288. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_9
Esgin, M.F., Steinfeld, R., Liu, J.K., Liu, D.: Lattice-Based Zero-Knowledge Proofs: New Techniques for Shorter and Faster Constructions and Applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 115–146. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_5
Esgin, M.F., Zhao, R.K., Steinfeld, R., Liu, J.K., Liu, D.: Matrict: Efficient, scalable and post-quantum blockchain confidential transactions protocol. In: CCS, pp. 567–584. ACM (2019)
Fischlin, M.: Round-Optimal Composable Blind Signatures in the Common Reference String Model. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 60–77. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_4
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197–206 (2008)
Herold, G., May, A.: LP solutions of vectorial integer subset sums – cryptanalysis of galbraith’s binary matrix LWE. In: Fehr, S. (ed.) PKC 2017. LNCS, vol. 10174, pp. 3–15. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54365-8_1
Hyperledger Foundation. Hyperledger Aries. https://www.hyperledger.org/use/aries. Accessed 06 Oct 2022
Hyperledger Foundation. Hyperledger Indy. https://www.hyperledger.org/use/hyperledger-indy. Accessed 06 Oct 2022
Jeudy, C., Roux-Langlois, A., Sanders, O.: Lattice signature with efficient protocols, application to anonymous credentials. Cryptology ePrint Archive, Paper 2022/509 (2022). https://eprint.iacr.org/2022/509
Lai, Q., Liu, F.-H., Lysyanskaya, A., Wang, Z.: Lattice-based commit-transferrable signatures and applications to anonymous credentials. Cryptology ePrint Archive, Paper 2023/766, (2023). https://eprint.iacr.org/2023/766
Langlois, A., Stehlé, D.: Worst-case to average-case reductions for module lattices. Des. Codes Crypt. 75(3), 565–599 (2015)
Looker, T., Kalos, V., Whitehead, A., Lodder, M.: The BBS Signature Scheme (2022). https://www.ietf.org/id/draft-looker-cfrg-bbs-signatures-01.html. Accessed 06 Oct 2022
Lysyanskaya, A., Rivest, R.L., Sahai, A., Wolf, S.: Pseudonym Systems. In: Heys, H., Adams, C. (eds.) SAC 1999. LNCS, vol. 1758, pp. 184–199. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-46513-8_14
Lyubashevsky, V.: Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 598–616. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_35
Lyubashevsky, V.: Lattice signatures without trapdoors. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 738–755. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_43
Lyubashevsky, V., Micciancio, D.: Asymptotically efficient lattice-based digital signatures. Cryptology ePrint Archive, Paper 2013/746 (2013). https://eprint.iacr.org/2013/746
Lyubashevsky, V., Micciancio, D.: Asymptotically efficient lattice-based digital signatures. J. Cryptol., 31(3), 774–797 (2018). https://eprint.iacr.org/2013/746. Preliminary version appeared in TCC 2008
Lyubashevsky, V., Nguyen, N.K.: Bloom: bimodal lattice one-out-of-many proofs and applications. Cryptology ePrint Archive, Paper 2022/1307 (2022). https://eprint.iacr.org/2022/1307
Lyubashevsky, V., Nguyen, N.K., Plançon, M.: Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general. IACR Cryptol. ePrint Arch., p. 284 (2022). Appears in Crypto 2022
Lyubashevsky, V., Nguyen, N.K., PlanM.: Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general. In: Dodis, Y., Shrimpton, T. (eds) CRYPTO 2022. LNCS, vol. 13508, pp. 71–101. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_3
Lyubashevsky, V., Nguyen, N.K., Seiler, G.: SMILE: set membership from ideal lattices with applications to ring signatures and confidential transactions. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12826, pp. 611–640. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84245-1_21
Lyubashevsky, V., Nguyen, N.K., Plancon, M., Seiler, G.: Shorter lattice-based group signatures via “Almost Free’’ encryption and other optimizations. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13093, pp. 218–248. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92068-5_8
MATTR. MATTR. https://github.com/mattrglobal. Accessed 06 Oct 2022
Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_41
Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007)
NFCW. Digital identity market revenues to reach US\$53bn in 2026 (2022). https://www.nfcw.com/2022/01/31/375825/digital-identity-market-revenues-to-reach-us53bn-in-2026/. Accessed 06 Oct 2022
del Pino, R., Katsumata, S.: A new framework for more efficient round-optimal lattice-based (partially) blind signature via trapdoor sampling. Cryptology ePrint Archive, Paper 2022/834 (2022). https://eprint.iacr.org/2022/834. https://eprint.iacr.org/2022/834
del Pino, R., Lyubashevsky, V., Seiler, G.: Lattice-based group signatures and zero-knowledge proofs of automorphism stability. In: ACM Conference on Computer and Communications Security, pp. 574–591. ACM (2018)
Prest, T., et al.: FALCON. Technical report, National Institute of Standards and Technology (2017). https://csrc.nist.gov/projects/post-quantum-cryptography/ round-1-submissions
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6) (2009)
The AnonCreds Specification Working Group. The AnonCreds Specification. https://github.com/AnonCreds-WG/anoncreds-spec (2022). Accessed 06 Oct 2022
Veramo. Veramo core development. https://github.com/uport-project. Accessed 06 Oct 2022
Wee, H., Wu, D.J.: Succinct vector, polynomial, and functional commitments from lattices. Cryptology ePrint Archive, Paper 2022/1515 (2022). https://eprint.iacr.org/2022/1515. https://eprint.iacr.org/2022/1515
Yang, R., Au, M.H., Zhang, Z., Xu, Q., Yu, Z., Whyte, W.: Efficient lattice-based zero-knowledge arguments with standard soundness: construction and applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 147–175. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_6
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 International Association for Cryptologic Research
About this paper
Cite this paper
Bootle, J., Lyubashevsky, V., Nguyen, N.K., Sorniotti, A. (2023). A Framework for Practical Anonymous Credentials from Lattices. In: Handschuh, H., Lysyanskaya, A. (eds) Advances in Cryptology – CRYPTO 2023. CRYPTO 2023. Lecture Notes in Computer Science, vol 14082. Springer, Cham. https://doi.org/10.1007/978-3-031-38545-2_13
Download citation
DOI: https://doi.org/10.1007/978-3-031-38545-2_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-38544-5
Online ISBN: 978-3-031-38545-2
eBook Packages: Computer ScienceComputer Science (R0)