nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Towards Compact Identity-Based Encryption on Ideal Lattices

verfasst von : Huiwen Jia, Yupu Hu, Chunming Tang, Lin Wang

Erschienen in: Topics in Cryptology – CT-RSA 2024

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Basic encryption and signature on lattices have comparable efficiency to their classical counterparts in terms of speed and key size. However, Identity-based Encryption (IBE) on lattices is much less efficient in terms of compactness, even when instantiated on ideal lattices and in the Random Oracle Model (ROM). This is because the underlying preimage sampling algorithm used to extract the users’ secret keys requires huge public parameters. In this work, we specify a compact IBE instantiation for practical use by introducing various optimizations. Specifically, we first propose a modified gadget that offers a tradeoff between security and compactness, making it more suitable for the instantiation of practical IBEs. Then, by incorporating our gadget and the non-spherical Gaussian technique, we provide an efficient preimage sampling algorithm, based on which, we give a specification of a compact IBE on ideal lattice. Finally, two parameter sets and a proof-of-concept implementation are presented. Given the importance of the preimage sampling algorithm in lattice-based cryptography, we believe that our technique can also be applied to the practical instantiation of other advanced cryptographic schemes.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Identity-Based Encryption from LWE with More Compact Master Public Key

Nächstes Kapitel Ascon MAC, PRF, and Short-Input PRF

Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert, H. (ed.) Advances in Cryptology - EUROCRYPT 2010. Lecture Notes in Computer Science, vol. 6110, pp. 553–572. Springer, Berlin (2010). https://doi.org/10.1007/978-3-642-13190-5_28CrossRef

Agrawal, S., Boneh, D., Boyen, X.: Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. In: Rabin, T. (ed.) Advances in Cryptology - CRYPTO 2010. Lecture Notes in Computer Science, vol. 6223, pp. 98–115. Springer, Berlin (2010). https://doi.org/10.1007/978-3-642-14623-7_6CrossRef

Ajtai, M.: Generating hard instances of lattice problems. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 99–108 (1996)

Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange-a new hope. In: USENIX Security 2016, pp. 327–343 (2016)

Apon, D., Fan, X., Liu, F.H.: Compact identity based encryption from LWE. Cryptology ePrint Archive, Report 2016/125 (2016)

Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: SODA 2016, pp. 10–24 (2016)

Bellare, M., Waters, B., Yilek, S.: Identity-based encryption secure against selective opening attack. In: Ishai, Y. (ed.) Theory of Cryptography. Lecture Notes in Computer Science, vol. 6597, pp. 235–252. Springer, Berlin (2011). https://doi.org/10.1007/978-3-642-19571-6_15CrossRef

Bert, P., Eberhart, G., Prabel, L., Roux-Langlois, A., Sabt, M.: Implementation of lattice trapdoors on modules and applications. In: Cheon, J.H., Tillich, J.P. (eds.) Post-Quantum Cryptography. Lecture Notes in Computer Science(), vol. 12841, pp. 195–214. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-81293-5_11CrossRef

Bert, P., Fouque, P.A., Roux-Langlois, A., Sabt, M.: Practical implementation of Ring-SIS/LWE based signature and IBE. In: Lange, T., Steinwandt, R. (eds.) Post-Quantum Cryptography. Lecture Notes in Computer Science(), vol. 10786, pp. 271–291. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-79063-3_13CrossRef

10.

Boldyreva, A., Goyal, V., Kumar, V.: Identity-based encryption with efficient revocation. In: ACM CCS 2008, pp. 417–426 (2008)

11.

Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. In: Kilian, J. (ed.) Advances in Cryptology - CRYPTO 2001. Lecture Notes in Computer Science, vol. 2139, pp. 213–229. Springer, Berlin (2001). https://doi.org/10.1007/3-540-44647-8_13CrossRef

12.

Brakerski, Z., Lombardi, A., Segev, G., Vaikuntanathan, V.: Anonymous IBE, leakage resilience and circular security from new assumptions. In: Nielsen, J., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT 2018. Lecture Notes in Computer Science(), vol. 10820, pp. 535–564. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_20CrossRef

13.

Brakerski, Z., Vaikuntanathan, V., Wee, H., Wichs, D.: Obfuscating conjunctions under entropic ring LWE. In: ITCS 2016, pp. 147–156 (2016)

14.

Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. In: Gilbert, H. (ed.) Advances in Cryptology - EUROCRYPT 2010. Lecture Notes in Computer Science, vol. 6110, pp. 523–552. Springer, Berlin (2010). https://doi.org/10.1007/978-3-642-13190-5_27CrossRef

15.

Chen, Y., Genise, N., Mukherjee, P.: Approximate trapdoors for lattices and smaller hash-and-sign signatures. In: Galbraith, S., Moriai, S. (eds.) Advances in Cryptology - ASIACRYPT 2019. Lecture Notes in Computer Science(), vol. 11923, pp. 3–32. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34618-8_1CrossRef

16.

Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) Advances in Cryptology - ASIACRYPT 2011. Lecture Notes in Computer Science, vol. 7073, pp. 1–20. Springer, Berlin (2011). https://doi.org/10.1007/978-3-642-25385-0_1CrossRef

17.

Chung, C.M.M., et al.: NTT multiplication for NTT-unfriendly rings: new speed records for saber and NTRU on Cortex-M4 and AVX2. IACR Trans. CHES 2021 (2), 159–188 (2021)

18.

Cocks, C.: An identity based encryption scheme based on quadratic residues. In: Honary, B. (ed.) Cryptography and Coding. Lecture Notes in Computer Science, vol. 2260, pp. 360–363. Springer, Berlin (2001). https://doi.org/10.1007/3-540-45325-3_32CrossRef

19.

Döttling, N., Garg, S.: Identity-based encryption from the Diffie-Hellman assumption. In: Katz, J., Shacham, H. (eds.) Advances in Cryptology - CRYPTO 2017. Lecture Notes in Computer Science(), vol. 10401, pp. 537–569. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_18CrossRef

20.

Ducas, L., Galbraith, S., Prest, T., Yu, Y.: Integral matrix gram root and lattice gaussian sampling without floats. In: Canteaut, A., Ishai, Y. (eds.) Advances in Cryptology - EUROCRYPT 2020. Lecture Notes in Computer Science(), vol. 12106, pp. 608–637. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_21CrossRef

21.

Ducas, L., Lyubashevsky, V., Prest, T.: Efficient identity-based encryption over NTRU lattices. In: Sarkar, P., Iwata, T. (eds.) Advances in Cryptology - ASIACRYPT 2014. Lecture Notes in Computer Science, vol. 8874, pp. 22–41. Springer, Berlin (2014). https://doi.org/10.1007/978-3-662-45608-8_2CrossRef

22.

Ducas, L., Nguyen, P.Q.: Learning a zonotope and more: cryptanalysis of NTRUSign countermeasures. In: Wang, X., Sako, K. (eds.) Advances in Cryptology - ASIACRYPT 2012. Lecture Notes in Computer Science, vol. 7658, pp. 433–450. Springer, Berlin (2012). https://doi.org/10.1007/978-3-642-34961-4_27CrossRef

23.

Ducas, L., Prest, T.: Fast fourier orthogonalization. In: ISSAC 2016, pp. 191–198 (2016)

24.

Espitau, T., et al.: MITAKA: a simpler, parallelizable, maskable variant of FALCON. In: Dunkelman, O., Dziembowski, S. (eds.) Advances in Cryptology - EUROCRYPT 2022. Lecture Notes in Computer Science, vol. 13277, pp. 222–253. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-07082-2_9CrossRef

25.

Espitau, T., Tibouchi, M., Wallet, A., Yang, Yu.: Shorter hash-and-sign lattice-based signatures. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology - CRYPTO 2022. Lecture Notes in Computer Science, vol. 13508, pp. 245–275. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_9CrossRef

26.

Fujioka, A., Suzuki, K., Xagawa, K., Yoneyama, K.: Strongly secure authenticated key exchange from factoring, codes, and lattices. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) Public Key Cryptography - PKC 2012. Lecture Notes in Computer Science, vol. 7293, pp. 467–484. Springer, Berlin (2012). https://doi.org/10.1007/978-3-642-30057-8_28CrossRef

27.

Fujisaki, E., Okamoto, T.: How to enhance the security of public-key encryption at minimum cost. In: Public Key Cryptography. Lecture Notes in Computer Science, vol. 1560, pp. 53–68. Springer, Berlin (1999). https://doi.org/10.1007/3-540-49162-7_5CrossRef

28.

Genise, N., Micciancio, D.: Faster gaussian sampling for trapdoor lattices with arbitrary modulus. In: Nielsen, J., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT 2018. Lecture Notes in Computer Science(), vol. 10820, pp. 174–203. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_7CrossRef

29.

Genise, N., Micciancio, D., Peikert, C., Walter, M.: Improved discrete gaussian and subgaussian analysis for lattice cryptography. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) Public-Key Cryptography - PKC 2020. Lecture Notes in Computer Science(), vol. 12110, pp. 623–651. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45374-9_21CrossRef

30.

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC 2008, pp. 197–206 (2008)

31.

Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski, B.S. (ed.) Advances in Cryptology - CRYPTO 1997. Lecture Notes in Computer Science, vol. 1294, pp. 112–131. Springer, Berlin (1997). https://doi.org/10.1007/BFb0052231CrossRef

32.

Gorbunov, S., Vaikuntanathan, V., Wee, H.: Attribute-based encryption for circuits. In: STOC 2013, pp. 545–554 (2013)

33.

Gorbunov, S., Vaikuntanathan, V., Wee, H.: Predicate encryption for circuits from LWE. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology - CRYPTO 2015. Lecture Notes in Computer Science(), vol. 9216, pp. 503–523. Springer, Berlin (2015). https://doi.org/10.1007/978-3-662-48000-7_25CrossRef

34.

Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.: NTRUSIGN: digital signatures using the NTRU lattice. In: Joye, M. (ed.) Topics in Cryptology- CT-RSA 2003. Lecture Notes in Computer Science, vol. 2612, pp. 122–140. Springer, Berlin (2003). https://doi.org/10.1007/3-540-36563-x_9CrossRef

35.

Hofheinz, D., Hövelmanns, K., Kiltz, E.: A modular analysis of the Fujisaki-Okamoto transformation. In: Kalai, Y., Reyzin, L. (eds.) Theory of Cryptography. Lecture Notes in Computer Science(), vol. 10677, pp. 341–371. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_12CrossRef

36.

Howe, J., Prest, T., Ricosset, T., Rossi, M.: Isochronous gaussian sampling: from inception to implementation. In: Ding, J., Tillich, J.P. (eds.) Post-Quantum Cryptography. Lecture Notes in Computer Science(), vol. 12100, pp. 53–71. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_4CrossRef

37.

Hu, Y., Jia, H.: A new gaussian sampling for trapdoor lattices with arbitrary modulus. Des. Codes Cryptogr. 87, 2553–2570 (2019)MathSciNetCrossRef

38.

Jia, H., Hu, Y., Tang, C.: Lattice-based hash-and-sign signatures using approximate trapdoor, revisited. IET Inf. Secur. 16(1), 41–50 (2022)CrossRef

39.

Jiang, H., Zhang, Z., Chen, L., Wang, H., Ma, Z.: IND-CCA-secure key encapsulation mechanism in the quantum random oracle model, revisited. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology - CRYPTO 2018. Lecture Notes in Computer Science(), vol. 10993, pp. 96–125. Springer, Cham. (2018). https://doi.org/10.1007/978-3-319-96878-0_4CrossRef

40.

Jutla, C.S., Roy, A.: Shorter quasi-adaptive NIZK proofs for linear subspaces. In: Sako, K., Sarkar, P. (eds.) Advances in Cryptology - ASIACRYPT 2013. Lecture Notes in Computer Science, vol. 8269, pp. 1–20. Springer, Berlin (2013). https://doi.org/10.1007/978-3-642-42033-7_1CrossRef

41.

Katsumata, S., Yamada, S.: Partitioning via non-linear polynomial functions: more compact IBEs from ideal lattices and bilinear maps. In: Cheon, J., Takagi, T. (eds.) Advances in Cryptology - ASIACRYPT 2016. Lecture Notes in Computer Science(), vol. 10032, pp. 682–712. Springer, Berlin (2016). https://doi.org/10.1007/978-3-662-53890-6_23CrossRef

42.

Laarhoven, T.: Search problems in cryptography. PhD thesis, PhD thesis, Eindhoven University of Technology, 2016 (2016)

43.

Lewko, A.: Tools for simulating features of composite order bilinear groups in the prime order setting. In: Pointcheval, D., Johansson, T. (eds.) Advances in Cryptology - EUROCRYPT 2012. Lecture Notes in Computer Science, vol. 7237, pp. 318–335. Springer, Berlin (2012). https://doi.org/10.1007/978-3-642-29011-4_20CrossRef

44.

Lu, X., et al.: LAC: practical Ring-LWE based public-key encryption with byte-level modulus. Cryptology ePrint Archive, Paper 2018/1009 (2018)

45.

Lyubashevsky, V., et al.: Dilithium: submission to the NIST’s post-quantum cryptography standardization process (2022)

46.

McCarthy, S., Smyth, N., O’Sullivan, E.: A practical implementation of identity-based encryption over NTRU lattices. In: O’Neill, M. (ed.) Cryptography and Coding. Lecture Notes in Computer Science(), vol. 10655, pp. 227–246. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71045-7_12CrossRef

47.

Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) Advances in Cryptology - EUROCRYPT 2012. Lecture Notes in Computer Science, vol. 7237, pp. 700–718. Springer, Berlin (2012). https://doi.org/10.1007/978-3-642-29011-4_41CrossRef

48.

DMicciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput., 372–381 (2004)

49.

Micciancio, D., Walter, M.: Practical, predictable lattice basis reduction. In: Fischlin, M., Coron, J.S. (eds.) Advances in Cryptology - EUROCRYPT 2016. Lecture Notes in Computer Science(), vol. 9665, pp. 820–849. Springer, Berlin (2016). https://doi.org/10.1007/978-3-662-49890-3_31CrossRef

50.

Nguyen, P.Q., Regev, O.: Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. In: Vaudenay, S. (ed.) Advances in Cryptology - EUROCRYPT 2006. Lecture Notes in Computer Science, vol. 4004, pp. 271–288. Springer, Berlin (2006). https://doi.org/10.1007/11761679_17CrossRef

51.

Peikert, C.: An efficient and parallel Gaussian sampler for lattices. In: Rabin, T. (ed.) Advances in Cryptology - CRYPTO 2010. Lecture Notes in Computer Science, vol. 6223, pp. 80–97. Springer, Berlin (2010). https://doi.org/10.1007/978-3-642-14623-7_5CrossRef

52.

Prest, T.: Gaussian sampling in lattice-based cryptography. PhD thesis, PhD thesis, École Normale Supérieure Paris (2015)

53.

Prest, T., et al.: Falcon: submission to the NIST’s post-quantum cryptography standardization process (2022)

54.

Schnorr, C.-P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181–199 (1994)MathSciNetCrossRef

55.

Schwabe, P., et al.: Kyber: submission to the NIST’s post-quantum cryptography standardization process (2020)

56.

Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakley, G.R., Chaum, D. (eds.) Advances in Cryptology. Lecture Notes in Computer Science, vol. 196, pp. 47–53. Springer, Berlin (1984). https://doi.org/10.1007/3-540-39568-7_5CrossRef

57.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)MathSciNetCrossRef

58.

Waters, B.: Dual system encryption: Realizing fully secure IBE and HIBE under simple assumptions. In: Halevi, S. (ed.) Advances in Cryptology - CRYPTO 2009. Lecture Notes in Computer Science, vol. 5677, pp. 619–636. Springer, Berlin (2009). https://doi.org/10.1007/978-3-642-03356-8_36CrossRef

59.

Yamada, S.: Adaptively secure identity-based encryption from lattices with asymptotically shorter public parameters. In: Fischlin, M., Coron, J.S. (eds.) Advances in Cryptology - EUROCRYPT 2016. Lecture Notes in Computer Science(), vol. 9666, pp. 32–62. Springer, Berlin (2016). https://doi.org/10.1007/978-3-662-49896-5_2CrossRef

60.

Yang, Yu., Ducas, L.: Learning strikes again: the case of the DRS signature scheme. In: Peyrin, T., Galbraith, S. (eds.) Advances in Cryptology - ASIACRYPT 2018. Lecture Notes in Computer Science(), vol. 11273, pp. 525–543. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_18CrossRef

61.

Yu, Y., Jia, H., Wang, X.: Compact lattice gadget and its applications to hash-and-sign signatures. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology - CRYPTO 2023. Lecture Notes in Computer Science, vol. 14085, pp. 390–420. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-38554-4_13CrossRef

62.

Zhang, S., Yang, Yu.: Towards a simpler lattice gadget toolkit. In: Hanaoka, G., Shikata, J., Watanabe, Y. (eds.) Public-Key Cryptography - PKC 2022. Lecture Notes in Computer Science(), vol. 13177, pp. 498–520. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-97121-2_18CrossRef

Titel: Towards Compact Identity-Based Encryption on Ideal Lattices
verfasst von: Huiwen Jia
Yupu Hu
Chunming Tang
Lin Wang
Verlag: Springer Nature Switzerland
Buch: Topics in Cryptology – CT-RSA 2024
Print ISBN: 978-3-031-58867-9

Electronic ISBN: 978-3-031-58868-6

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-3-031-58868-6_14

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner