Hawk: module LIP makes lattice signatures fast, compact and simple. (English) Zbl 1519.94220
Agrawal, Shweta (ed.) et al., Advances in cryptology – ASIACRYPT 2022. 28th international conference on the theory and application of cryptology and information security, Taipei, Taiwan, December 5–9, 2022. Proceedings. Part IV. Cham: Springer. Lect. Notes Comput. Sci. 13794, 65-94 (2023).
Summary: We propose the signature scheme Hawk, a concrete instantiation of proposals to use the Lattice Isomorphism Problem (LIP) as a foundation for cryptography that focuses on simplicity. This simplicity stems from LIP, which allows the use of lattices such as \(\mathbb{Z}^n\), leading to signature algorithms with no floats, no rejection sampling, and compact precomputed distributions. Such design features are desirable for constrained devices, and when computing signatures inside FHE or MPC. The most significant change from recent LIP proposals is the use of module lattices, reusing algorithms and ideas from NTRUSign and Falcon. Its simplicity makes Hawk competitive. We provide cryptanalysis with experimental evidence for the design of Hawk and implement two parameter sets, Hawk-512 and Hawk-1024. Signing using Hawk-512 and Hawk-1024 is four times faster than Falcon on x86 architectures, produces signatures that are about 15% more compact, and is slightly more secure against forgeries by lattice reduction attacks. When floating-points are unavailable, Hawk signs 15 times faster than Falcon.
We provide a worst case to average case reduction for module LIP. For certain parametrisations of Hawk this applies to secret key recovery and we reduce signature forgery in the random oracle model to a new problem called the one more short vector problem.
For the entire collection see [Zbl 1517.94004].
We provide a worst case to average case reduction for module LIP. For certain parametrisations of Hawk this applies to secret key recovery and we reduce signature forgery in the random oracle model to a new problem called the one more short vector problem.
For the entire collection see [Zbl 1517.94004].
MSC:
| 94A62 | Authentication, digital signatures and secret sharing |
| 94A60 | Cryptography |
| 81P94 | Quantum cryptography (quantum-theoretic aspects) |
| 68P25 | Data encryption (aspects in computer science) |
Keywords:
post-quantum cryptography; signatures; module lattice isomorphism problem; concrete design; quadratic formsReferences:
| [1] | Agrawal, S., Kirshanova, E., Stehle, D., Yadav, A.: Practical, round-optimal lattice-based blind signatures. Cryptology ePrint Archive, Paper 2021/1565 (2021). https://eprint.iacr.org/2021/1565 |
| [2] | Agrawal, S., Stehle, D., Yadav, A.: Round-optimal lattice-based threshold signatures, revisited. Cryptology ePrint Archive, Paper 2022/634 (2022). https://eprint.iacr.org/2022/634 |
| [3] | Albrecht, M.R., Ducas, L.: Lattice Attacks on NTRU and LWE: A History of Refinements, pp. 15-40. London Mathematical Society Lecture Note Series, Cambridge University Press (2021). doi:10.1017/9781108854207.004 · Zbl 1483.94030 |
| [4] | Babai, L., On Lovász’ lattice reduction and the nearest lattice point problem, Combinatorica, 6, 1, 1-13 (1986) · Zbl 0593.68030 · doi:10.1007/BF02579403 |
| [5] | Bai, S.; Stehlé, D.; Wen, W.; Peyrin, T.; Galbraith, S., Measuring, simulating and exploiting the head concavity phenomenon in BKZ, Advances in Cryptology - ASIACRYPT 2018, 369-404 (2018), Cham: Springer, Cham · Zbl 1446.94097 · doi:10.1007/978-3-030-03326-2_13 |
| [6] | Banaszczyk, W., New bounds in some transference theorems in the geometry of numbers, Math. Ann., 296, 1, 625-635 (1993) · Zbl 0786.11035 · doi:10.1007/BF01445125 |
| [7] | Bennett, H., Ganju, A., Peetathawatchai, P., Stephens-Davidowitz, N.: Just how hard are rotations of \(\mathbb{{Z}}^n\)? algorithms and cryptography with the simplest lattice. Cryptology ePrint Archive, Report 2021/1548 (2021). https://eprint.iacr.org/2021/1548 |
| [8] | Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Boneh, D., Roughgarden, T., Feigenbaum, J., (eds.) 45th ACM STOC, pp. 575-584. ACM Press (2013). doi:10.1145/2488608.2488680 · Zbl 1293.68159 |
| [9] | Chen, Y.; Nguyen, PQ; Lee, DH; Wang, X., BKZ 2.0: better lattice security estimates, Advances in Cryptology - ASIACRYPT 2011, 1-20 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.94037 · doi:10.1007/978-3-642-25385-0_1 |
| [10] | Dachman-Soled, D.; Ducas, L.; Gong, H.; Rossi, M.; Micciancio, D.; Ristenpart, T., LWE with side information: attacks and concrete security estimation, Advances in Cryptology - CRYPTO 2020, 329-358 (2020), Cham: Springer, Cham · Zbl 1504.94128 · doi:10.1007/978-3-030-56880-1_12 |
| [11] | Ducas, L.; Durmus, A.; Lepoint, T.; Lyubashevsky, V.; Canetti, R.; Garay, JA, Lattice signatures and bimodal Gaussians, Advances in Cryptology - CRYPTO 2013, 40-56 (2013), Heidelberg: Springer, Heidelberg · Zbl 1310.94141 · doi:10.1007/978-3-642-40041-4_3 |
| [12] | Ducas, L.; Nguyen, PQ; Wang, X.; Sako, K., Faster Gaussian lattice sampling using lazy floating-point arithmetic, Advances in Cryptology - ASIACRYPT 2012, 415-432 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94058 · doi:10.1007/978-3-642-34961-4_26 |
| [13] | Ducas, L.; Nguyen, PQ; Wang, X.; Sako, K., Learning a zonotope and more: cryptanalysis of NTRUSign countermeasures, Advances in Cryptology - ASIACRYPT 2012, 433-450 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94059 · doi:10.1007/978-3-642-34961-4_27 |
| [14] | Ducas, L., Prest, T.: Fast Fourier orthogonalization. In: Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2016, Association for Computing Machinery, New York, NY, USA, pp. 191-198 (2016). doi:10.1145/2930889.2930923 · Zbl 1365.65105 |
| [15] | Ducas, L.; van Woerden, WPJ; Dunkelman, O.; Dziembowski, S., On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography, EUROCRYPT 2022, Part III, 643-673 (2022), Heidelberg: Springer, Heidelberg · Zbl 1502.94033 · doi:10.1007/978-3-031-07082-2_23 |
| [16] | Ducas, L., Postlethwaite, E.W., Pulles, L.N., van Woerden, W.: Hawk: Module LIP makes lattice signatures fast, compact and simple. Cryptology ePrint Archive, Paper 2022/1155 (2022). https://eprint.iacr.org/2022/1155 · Zbl 1519.94220 |
| [17] | Espitau, T.; Dunkelman, O.; Dziembowski, S., Mitaka: a simpler, parallelizable, maskable variant of falcon, EUROCRYPT 2022, Part III, 222-253 (2022), Heidelberg: Springer, Heidelberg · Zbl 1496.94042 · doi:10.1007/978-3-031-07082-2_9 |
| [18] | Genise, N.; Micciancio, D.; Nielsen, JB; Rijmen, V., Faster Gaussian sampling for trapdoor lattices with arbitrary modulus, Advances in Cryptology - EUROCRYPT 2018, 174-203 (2018), Cham: Springer, Cham · Zbl 1423.94073 · doi:10.1007/978-3-319-78381-9_7 |
| [19] | Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C., (eds.) 40th ACM STOC, pp. 197-206. ACM Press (2008). doi:10.1145/1374376.1374407 · Zbl 1231.68124 |
| [20] | Gentry, C.; Szydlo, M.; Knudsen, LR, Cryptanalysis of the revised NTRU signature scheme, Advances in Cryptology — EUROCRYPT 2002, 299-320 (2002), Heidelberg: Springer, Heidelberg · Zbl 1055.94015 · doi:10.1007/3-540-46035-7_20 |
| [21] | Golomb, S.: Run-length encodings (corresp.). IEEE Trans. Inf. Theory 12(3), 399-401 (1966). doi:10.1109/TIT.1966.1053907 · Zbl 0141.14202 |
| [22] | Hoffstein, J.; Howgrave-Graham, N.; Pipher, J.; Silverman, JH; Whyte, W.; Joye, M., NTRUSign: digital signatures using the NTRU lattice, Topics in Cryptology — CT-RSA 2003, 122-140 (2003), Heidelberg: Springer, Heidelberg · Zbl 1039.94525 · doi:10.1007/3-540-36563-X_9 |
| [23] | Kirchner, P.: Algorithms on ideal over complex multiplication order. Cryptology ePrint Archive, Report 2016/220 (2016). https://eprint.iacr.org/2016/220 |
| [24] | Lenstra, HW; Silverberg, A., Lattices with symmetry, J. Cryptol., 30, 3, 760-804 (2016) · Zbl 1377.94060 · doi:10.1007/s00145-016-9235-7 |
| [25] | Lyubashevsky, V.; Peikert, C.; Regev, O.; Gilbert, H., On ideal lattices and learning with errors over rings, Advances in Cryptology - EUROCRYPT 2010, 1-23 (2010), Heidelberg: Springer, Heidelberg · Zbl 1279.94099 · doi:10.1007/978-3-642-13190-5_1 |
| [26] | Micciancio, D.; Regev, O., Worst-case to average-case reductions based on Gaussian measures, SIAM J. Comput., 37, 1, 267-302 (2007) · Zbl 1142.68037 · doi:10.1137/S0097539705447360 |
| [27] | Nguyen, PQ; Regev, O., Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures, J. Cryptol., 22, 2, 139-160 (2008) · Zbl 1159.94369 · doi:10.1007/s00145-008-9031-0 |
| [28] | Peikert, C.; Rabin, T., An efficient and parallel Gaussian sampler for lattices, Advances in Cryptology - CRYPTO 2010, 80-97 (2010), Heidelberg: Springer, Heidelberg · Zbl 1280.94091 · doi:10.1007/978-3-642-14623-7_5 |
| [29] | Pornin, T.; Prest, T.; Lin, D.; Sako, K., More efficient algorithms for the NTRU key generation using the field norm, Public-Key Cryptography - PKC 2019, 504-533 (2019), Cham: Springer, Cham · Zbl 1509.94131 · doi:10.1007/978-3-030-17259-6_17 |
| [30] | Postlethwaite, EW; Virdia, F.; Garay, JA, On the success probability of solving unique SVP via BKZ, Public-Key Cryptography - PKC 2021, 68-98 (2021), Cham: Springer, Cham · Zbl 1479.94244 · doi:10.1007/978-3-030-75245-3_4 |
| [31] | Prest, T.: Gaussian sampling in lattice-based cryptography. Ph.D. thesis, Ecole normale supérieure-ENS PARIS (2015) |
| [32] | Prest, T., et al.: FALCON. Technical report, National Institute of Standards and Technology (2020). https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions |
| [33] | Szydlo, M.; Biham, E., Hypercubic lattice reduction and analysis of GGH and NTRU signatures, Advances in Cryptology — EUROCRYPT 2003, 433-448 (2003), Heidelberg: Springer, Heidelberg · Zbl 1038.94558 · doi:10.1007/3-540-39200-9_27 |
| [34] | T.F. development team: fpylll, a Python wraper for the fplll lattice reduction library, Version: 0.5.6 (2021). https://github.com/fplll/fpylll |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
