Abstract
Group encryption (GE), the encryption analog of group signatures, is a fundamental primitive that offers a privacy-preserving service for a specific receiver concealed within a group of certified users. Like other cryptographic primitives, GE constructions are always considered relative to the potential danger of quantum computations. The only existing lattice-based variant appeared in the work of Libert et al. (Asiacrypt’16). Despite its non-trivial achievement, the construction suffers in terms of efficiency due to the extensive use of lattice trapdoors. In this paper, we develop an integrated zero-knowledge argument system that is friendly to both accumulated values and hidden matrices and supports efficient designs from lattices. Based on this system, we propose efficiency enhancing GE where only group users are required to possess the lattice trapdoors and the other parties are not. In particular, we utilize lattice-based cryptographic accumulators to confirm prospective group members and use the dual Regev encryption scheme to provide privacy for ciphertext recipients. These modifications significantly increase GE efficiency. In addition, under the intractability assumptions of the standard lattice problems, we prove the security of the proposed scheme in the standard model (assuming interaction during the proof phase), which retains the strongest level of security as the only currently available candidate.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Kiayias A, Tsiounis Y, Yung M. Group encryption. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Kuching, 2007. 181–199
Chaum D, Heyst E V. Group signatures. In: Proceedings of Workshop on the Theory and Application of of Cryptographic Techniques, Brighton, 1991. 257–265
Trolin M, Wikström D. Hierarchical group signatures. In: Proceedings of International Colloquium on Automata, Languages, and Programming, Lisbon, 2005. 446–458
Libert B, Ling S, Mouhartem M, et al. Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, 2016. 101–131
Regev O. On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, 2005. 84–93
Ajtai M. Generating hard instances of the short basis problem. In: Proceedings of International Colloquium on Automata, Languages, and Programming, Prague, 1999. 1–9
Libert B, Ling S, Mouhartem M, et al. Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, 2016. 373–403
Lyubashevsky V. Lattice signatures without trapdoors. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, 2012. 738–755
Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, 2008. 197–206
Micciancio D, Peikert C. Trapdoors for lattices: simpler, tighter, faster, smaller. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, 2012. 700–718
Zhang J, Yu Y, Fan S Q, et al. Improved lattice-based CCA2-secure PKE in the standard model. Sci China Inf Sci, 2020, 63: 182101
Alwen J, Peikert C. Generating shorter bases for hard random lattices. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, Freiburg, 2009. 75–86
Libert B, Ling S, Nguyen K, et al. Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, 2016. 1–31
Ling S, Nguyen K, Wang H X, et al. Lattice-based group signatures: achieving full dynamicity with ease. In: Proceedings of International Conference on Applied Cryptography and Network Security, Kanazawa, 2017. 293–312
Cash D, Hofheinz D, Kiltz E, et al. Bonsai trees, or how to delegate a lattice basis. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco, 2010. 523–552
Camenisch J, Lysyanskaya A. A signature scheme with efficient protocols. In: Proceedings of International Conference on Security in Communication Networks, Amalfi, 2002. 268–289
Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques, Prague, 1999. 223–238
Cathalo J, Libert B, Yung M. Group encryption: non-interactive realization in the standard model. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, 2009. 179–196
Aimani L E, Joye M. Toward practical group encryption. In: Proceedings of the 11th International Conference on Applied Cryptography and Network Security, Banff, 2013. 237–252
Libert B, Yung M, Joye M, et al. Traceable group encryption. In: Proceedings of International Workshop on Public Key Cryptography, Buenos Aires, 2014. 592–610
Kiayias A, Tsiounis Y, Yung M. Traceable signatures. In: Proceedings of the 23rd Annual Eurocrypt Conference, Interlaken, 2004. 571–589
Izabachène M, Pointcheval D, Vergnaud D. Mediated traceable anonymous encryption. In: Proceedings of the 1st International Conference on Cryptology and Information Security in Latin America, Puebla, 2010. 40–60
Naor M, Yung M. Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, 1990. 427–437
Micciancio D, Peikert C. Hardness of SIS and LWE with small parameters. In: Proceedings of Annual Cryptology Conference, Santa Barbara, 2013. 21–39
Brakerski Z, Langlois A, Peikert C, et al. Classical hardness of learning with errors. In: Proceedings of A Symposium on Theory of Computing Conference, Palo Alto, 2013. 575–584
Peikert C. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, Bethesda, 2009. 333–342
Baric N, Pfitzmann B. Collision-free accumulators and fail-stop signature schemes without trees. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Konstanz, 1997. 480–494
Camenisch J, Lysyanskaya A. Dynamic accumulators and application to efficient revocation of anonymous credentials. In: Proceedings of the 22nd Annual International Cryptology Conference, Santa Barbara, 2002. 61–76
Nguyen N. Accumulators from bilinear pairings and applications. In: Proceedings of Cryptographers’ Track at the RSA Conference, San Francisco, 2005. 275–292
Tsudik G, Xu S H. Accumulating composites and improved group signing. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Taipei, 2003. 265–286
Stern J. A new paradigm for public key identification. IEEE Trans Inform Theory, 1996, 42: 1757–1768
Benhamouda F, Camenisch J, Krenn S, et al. Better zero-knowledge proofs for lattice encryption and their application to group signatures. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, 2014. 551–572
Jain A, Krenn S, Pietrzak K, et al. Commitments and efficient zero-knowledge proofs from learning parity with noise. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Beijing, 2012. 663–680
Langlois A, Ling S, Nguyen K, et al. Lattice-based group signature scheme with verifier-local revocation. In: Proceedings of International Workshop on Public Key Cryptography, Buenos Aires, 2014. 345–361
Ling S, Nguyen K, Stehlé D, et al. Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications. In: Proceedings of International Workshop on Public Key Cryptography, Nara, 2013. 107–124
Ling S, Nguyen K, Wang H X. Group signatures from lattices: simpler, tighter, shorter, ring-based. In: Proceedings of IACR International Workshop on Public Key Cryptography, Gaithersburg, 2015. 427–449
Kawachi A, Tanaka K, Xagawa K. Concurrently secure identification schemes based on the worst-case hardness of lattice problems. In: Proceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, 2008. 372–389
Agrawal S, Boneh D, Boyen X. Efficient lattice (H)IBE in the standard model. In: Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco, 2010. 553–572
Yang R P, Au M H, Zhang Z F, et al. Efficient lattice-based zero-knowledge arguments with standard soundness: construction and applications. In: Proceedings of Annual International Cryptology Conference, 2019. 147–175
Albrecht M R, Player R, Scott S. On the concrete hardness of Learning with Errors. J Math Cryptology, 2015, 9: 169–203
Kosba A E, Zhao Z C, Miller A, et al. CøCø: a framework for building composable zero-knowledge proofs. Cryptology ePrint Archive, Report 2015/1093, 2005
Alkim E, Ducas L, Pöppelmann T, et al. Post-quantum key exchange — a new hope. In: Proceedings of the 25th USENIX Security Symposium, Austin, 2016. 327–343
Albrecht M R, Curtis R R, Deo A, et al. Estimate all the {LWE, NTRU} schemes! In: Proceedings of International Conference on Security and Cryptography for Networks, Amalfi, 2018. 351–367
Chen Y M, Nguyen P Q. BKZ 2.0: better lattice security estimates. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Seoul, 2011. 1–20
Zheng Z X, Wang X Y, Xu G W, et al. Orthogonalized lattice enumeration for solving SVP. Sci China Inf Sci, 2018, 61: 032115
Sahai A. Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, New York, 1999. 543–553
Damgård I. Efficient concurrent zero-knowledge in the auxiliary string model. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Bruges, 2000. 418–430
Acknowledgements
This work was supported by the National Cryptography Development Fund (Grant No. MMJJ20180110) and National Natural Science Foundation of China (Grant No. 61960206014).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Pan, J., Zhang, J., Zhang, F. et al. Lattice-based group encryptions with only one trapdoor. Sci. China Inf. Sci. 65, 152304 (2022). https://doi.org/10.1007/s11432-020-3226-6
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11432-020-3226-6