Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem. (English) Zbl 07913129
Guo, Jian (ed.) et al., Advances in cryptology – ASIACRYPT 2023. 29th international conference on the theory and application of cryptology and information security, Guangzhou, China, December 4–8, 2023. Proceedings. Part IV. Singapore: Springer. Lect. Notes Comput. Sci. 14441, 167-200 (2023).
Summary: \( \mathbb{Z}^n\) is one of the simplest types of lattices, but the computational problems on its rotations, such as \(\mathbb{Z}\)SVP and \(\mathbb{Z}\)LIP, have been of great interest in cryptography. Recent advances have been made in building cryptographic primitives based on these problems, as well as in developing new algorithms for solving them. However, the theoretical complexity of \(\mathbb{Z}\)SVP and \(\mathbb{Z}\)LIP are still not well understood.
In this work, we study the problems on rotations of \(\mathbb{Z}^n\) by exploiting the symmetry property. We introduce a randomization framework that can be roughly viewed as ‘applying random automorphisms’ to the output of an oracle, without accessing the automorphism group. Using this framework, we obtain new reduction results for rotations of \(\mathbb{Z}^n\). First, we present a reduction from \(\mathbb{Z}\)LIP to \(\mathbb{Z}\)SCVP. Here \(\mathbb{Z}\)SCVP is the problem of finding the shortest characteristic vectors, which is a special case of CVP where the target vector is a deep hole of the lattice. Moreover, we prove a reduction from \(\mathbb{Z}\)SVP to \(\gamma\)-\(\mathbb{Z}\)SVP for any constant \(\gamma = O(1)\) in the same dimension, which implies that \(\mathbb{Z}\)SVP is as hard as its approximate version for any constant approximation factor. Second, we investigate the problem of finding a nontrivial automorphism for a given lattice, which is called LAP. Specifically, we use the randomization framework to show that \(\mathbb{Z}\)LAP is as hard as \(\mathbb{Z}\)LIP. We note that our result can be viewed as a \(\mathbb{Z}^n\)-analogue of Lenstra and Silverberg’s result in [H. W. Lenstra jun. and A. Silverberg, J. Cryptology 30, No. 3, 760–804 (2017; Zbl 1377.94060)], but with a different assumption: they assume the \(G\)-lattice structure, while we assume the access to an oracle that outputs a nontrivial automorphism.
For the entire collection see [Zbl 07831380].
In this work, we study the problems on rotations of \(\mathbb{Z}^n\) by exploiting the symmetry property. We introduce a randomization framework that can be roughly viewed as ‘applying random automorphisms’ to the output of an oracle, without accessing the automorphism group. Using this framework, we obtain new reduction results for rotations of \(\mathbb{Z}^n\). First, we present a reduction from \(\mathbb{Z}\)LIP to \(\mathbb{Z}\)SCVP. Here \(\mathbb{Z}\)SCVP is the problem of finding the shortest characteristic vectors, which is a special case of CVP where the target vector is a deep hole of the lattice. Moreover, we prove a reduction from \(\mathbb{Z}\)SVP to \(\gamma\)-\(\mathbb{Z}\)SVP for any constant \(\gamma = O(1)\) in the same dimension, which implies that \(\mathbb{Z}\)SVP is as hard as its approximate version for any constant approximation factor. Second, we investigate the problem of finding a nontrivial automorphism for a given lattice, which is called LAP. Specifically, we use the randomization framework to show that \(\mathbb{Z}\)LAP is as hard as \(\mathbb{Z}\)LIP. We note that our result can be viewed as a \(\mathbb{Z}^n\)-analogue of Lenstra and Silverberg’s result in [H. W. Lenstra jun. and A. Silverberg, J. Cryptology 30, No. 3, 760–804 (2017; Zbl 1377.94060)], but with a different assumption: they assume the \(G\)-lattice structure, while we assume the access to an oracle that outputs a nontrivial automorphism.
For the entire collection see [Zbl 07831380].
MSC:
| 94A60 | Cryptography |
| 11Y16 | Number-theoretic algorithms; complexity |
| 11H31 | Lattice packing and covering (number-theoretic aspects) |
Keywords:
lattice automorphism; randomized reduction; \( \mathbb{Z}\)LIP; gradient descent; characteristic vectors of the unimodular latticeCitations:
Zbl 1377.94060Software:
HawkReferences:
| [1] | Aggarwal, D., Bennett, H., Golovnev, A., Stephens-Davidowitz, N.: Fine-grained hardness of CVP(P) - everything that we can prove (and nothing else). In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, 10-13 January 2021, pp. 1816-1835. SIAM (2021). doi:10.1137/1.9781611976465.109 · Zbl 07788447 |
| [2] | Aggarwal, D., Dadush, D., Regev, O., Stephens-Davidowitz, N.: Solving the shortest vector problem in \(2{}^{\text{n}}\) time using discrete gaussian sampling: extended abstract. In: Servedio, R.A., Rubinfeld, R. (eds.) Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC 2015), Portland, 14-17 June 2015, pp. 733-742. ACM (2015). doi:10.1145/2746539.2746606 · Zbl 1321.68426 |
| [3] | Aggarwal, D., Li, J., Nguyen, P.Q., Stephens-Davidowitz, N.: Slide reduction, revisited—filling the gaps in SVP approximation. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 274-295. Springer, Cham (2020). doi:10.1007/978-3-030-56880-1_10 · Zbl 1504.94089 |
| [4] | Aggarwal, D., Li, Z., Stephens-Davidowitz, N.: A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-hermite SVP, and an improved time-approximation tradeoff for (H)SVP. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 467-497. Springer, Cham (2021). doi:10.1007/978-3-030-77870-5_17 · Zbl 07440589 |
| [5] | Aggarwal, D., Stephens-Davidowitz, N.: Just take the average! an embarrassingly simple \(2{^n}\)-time algorithm for SVP (and CVP). In: Seidel, R. (ed.) 1st Symposium on Simplicity in Algorithms, SOSA 2018, 7-10 January 2018, New Orleans. OASIcs, vol. 61, pp. 12:1-12:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018). doi:10.4230/OASIcs.SOSA.2018.12 · Zbl 1433.68474 |
| [6] | Aggarwal, D., Ursu, B., Vaudenay, S.: Faster sieving algorithm for approximate SVP with constant approximation factors. Cryptology ePrint Archive (2019) |
| [7] | Babai, L.: Graph isomorphism in quasipolynomial time [extended abstract]. In: Wichs, D., Mansour, Y. (eds.) Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016) Cambridge, 18-21 June 2016, pp. 684-697. ACM (2016). doi:10.1145/2897518.2897542 · Zbl 1376.68058 |
| [8] | Bennett, H.: The complexity of the shortest vector problem. Electron. Colloquium Comput. Complex. TR22-170 (2022). https://eccc.weizmann.ac.il/report/2022/170 |
| [9] | Bennett, H., Ganju, A., Peetathawatchai, P., Stephens-Davidowitz, N.: Just how hard are rotations of \({Z}^{{n}}\)? algorithms and cryptography with the simplest lattice. IACR Cryptol. ePrint Arch., p. 1548 (2021). https://eprint.iacr.org/2021/1548 · Zbl 1528.94035 |
| [10] | Bennett, H., Golovnev, A., Stephens-Davidowitz, N.: On the quantitative hardness of CVP. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), Berkeley, 15-17 October 2017, pp. 13-24. IEEE Computer Society (2017). doi:10.1109/FOCS.2017.11 |
| [11] | Blanks, T.L., Miller, S.D.: Generating cryptographically-strong random lattice bases and recognizing rotations of \(\mathbb{Z}^n\). In: Cheon, J.H., Tillich, J.-P. (eds.) PQCrypto 2021 2021. LNCS, vol. 12841, pp. 319-338. Springer, Cham (2021). doi:10.1007/978-3-030-81293-5_17 · Zbl 1485.94059 |
| [12] | Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) Symposium on Theory of Computing Conference (STOC 2013), Palo Alto, 1-4 June 2013, pp. 575-584. ACM (2013). doi:10.1145/2488608.2488680 · Zbl 1293.68159 |
| [13] | Cai, J., Nerurkar, A.: An improved worst-case to average-case connection for lattice problems. In: 38th Annual Symposium on Foundations of Computer Science (FOCS 1997), Miami Beach, 19-22 October 1997, pp. 468-477. IEEE Computer Society (1997). doi:10.1109/SFCS.1997.646135 |
| [14] | Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 523-552. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13190-5_27 · Zbl 1280.94043 |
| [15] | Collins, B.; Śniady, P., Integration with respect to the haar measure on unitary, orthogonal and symplectic group, Commun. Math. Phys., 264, 3, 773-795, 2006 · Zbl 1108.60004 · doi:10.1007/s00220-006-1554-3 |
| [16] | Diaconis, P.; Shahshahani, M., The subgroup algorithm for generating uniform random variables, Probab. Eng. Inf. Sci., 1, 1, 15-32, 1987 · Zbl 1133.60300 · doi:10.1017/S0269964800000255 |
| [17] | Ducas, L., Gibbons, S.: Hull attacks on the lattice isomorphism problem. IACR Cryptol. ePrint Arch., p. 194 (2023). https://eprint.iacr.org/2023/194 · Zbl 1527.94033 |
| [18] | Ducas, L., Postlethwaite, E.W., Pulles, L.N., van Woerden, W.P.J.: Hawk: module LIP makes lattice signatures fast, compact and simple. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022. LNCS, vol. 13794, pp. 65-94. Springer, Cham (2022). doi:10.1007/978-3-031-22972-5_3 · Zbl 1519.94220 |
| [19] | Ducas, L., van Woerden, W.P.J.: On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13277, pp. 643-673. Springer, Cham (2022). doi:10.1007/978-3-031-07082-2_23 · Zbl 1502.94033 |
| [20] | Ducas, L.: Provable lattice reduction of \({Z}^n\) with blocksize \(n/2\). Cryptology ePrint Archive, Paper 2023/447 (2023). https://eprint.iacr.org/2023/447 |
| [21] | Dutour Sikirić, M.; Haensch, A.; Voight, J.; van Woerden, WP, A canonical form for positive definite matrices, Open Book Ser., 4, 1, 179-195, 2020 · Zbl 1471.11209 · doi:10.2140/obs.2020.4.179 |
| [22] | Eisenträger, K., Hallgren, S., Kitaev, A.Y., Song, F.: A quantum algorithm for computing the unit group of an arbitrary degree number field. In: Shmoys, D.B. (ed.) Symposium on Theory of Computing, STOC 2014, New York, 31 May-03 June 2014, pp. 293-302. ACM (2014). doi:10.1145/2591796.2591860 · Zbl 1315.68134 |
| [23] | Geißler, K., Smart, N.P.: Computing the \(M = U U{}^{\text{ t }}\) integer matrix decomposition. In: Paterson, K.G. (ed.) Cryptography and Coding. LNCS, vol. 2898, pp. 223-233. Springer, Heidelberg (2003). doi:10.1007/978-3-540-40974-8_18 · Zbl 1123.94338 |
| [24] | Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Dwork, C. (ed.) Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, 17-20 May 2008, pp. 197-206. ACM (2008). doi:10.1145/1374376.1374407 · Zbl 1231.68124 |
| [25] | Gentry, C., Szydlo, M.: Cryptanalysis of the revised NTRU signature scheme. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 299-320. Springer, Heidelberg (2002). doi:10.1007/3-540-46035-7_20 · Zbl 1055.94015 |
| [26] | Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Jr., B.S.K. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112-131. Springer, Heidelberg (1997). doi:10.1007/BFb0052231 · Zbl 0889.94011 |
| [27] | Haviv, I., Regev, O.: Hardness of the covering radius problem on lattices. Chic. J. Theor. Comput. Sci. (2012). https://cjtcs.cs.uchicago.edu/articles/2012/4/contents.html · Zbl 1286.68192 |
| [28] | Haviv, I., Regev, O.: On the lattice isomorphism problem. In: Chekuri, C. (ed.) Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, 5-7 January 2014, pp. 391-404. SIAM (2014). doi:10.1137/1.9781611973402.29 · Zbl 1421.68085 |
| [29] | Hoeffding, W.: Probability inequalities for sums of bounded random variables. In: The Collected Works of Wassily Hoeffding, pp. 409-426 (1994) |
| [30] | Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.: NTRUSign: digital signatures using the NTRU lattice. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 122-140. Springer, Heidelberg (2003). doi:10.1007/3-540-36563-X_9 · Zbl 1039.94525 |
| [31] | Hunkenschröder, C.: Deciding whether a lattice has an orthonormal basis is in co-np. arXiv preprint arXiv:1910.03838 (2019) |
| [32] | Lenstra, H.W., Jr., Silverberg, A.: Revisiting the gentry-szydlo algorithm. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 280-296. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44371-2_16 · Zbl 1343.94070 |
| [33] | Lenstra, HW Jr; Silverberg, A., Lattices with symmetry, J. Cryptol., 30, 3, 760-804, 2017 · Zbl 1377.94060 · doi:10.1007/s00145-016-9235-7 |
| [34] | Khot, S.: Hardness of approximating the shortest vector problem in lattices. In: Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), October 17-19 2004, Rome, pp. 126-135. IEEE Computer Society (2004). doi:10.1109/FOCS.2004.31 |
| [35] | Köbler, J., Schöning, U., Torán, J.: The graph isomorphism problem: its structural complexity. Prog. Theor. Comput. Sci., Birkhäuser/Springer (1993). doi:10.1007/978-1-4612-0333-9 · Zbl 0813.68103 |
| [36] | Kuperberg, G.: The hidden subgroup problem for infinite groups (2020). https://simons.berkeley.edu/sites/default/files/docs/21261/berkeley.pdf |
| [37] | Kuperberg, G.: The hidden subgroup problem for \(\mathbb{Z}^k\) for infinite-index subgroups (2022). https://simons.berkeley.edu/sites/default/files/docs/21261/berkeley.pdf |
| [38] | Lenstra, AK; Lenstra, HW; Lovász, L., Factoring polynomials with rational coefficients, Math. Annalen, 261, 515-534, 1982 · Zbl 0488.12001 · doi:10.1007/BF01457454 |
| [39] | Liu, M., Wang, X., Xu, G., Zheng, X.: Shortest lattice vectors in the presence of gaps. Cryptology ePrint Archive (2011) |
| [40] | Luks, E.M.: Permutation groups and polynomial-time computation. In: Finkelstein, L., Kantor, W.M. (eds.) Groups and Computation, Proceedings of a DIMACS Workshop, New Brunswick, 7-10 October 1991. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 11, pp. 139-175. DIMACS/AMS (1991). doi:10.1090/dimacs/011/11 · Zbl 0813.20004 |
| [41] | Martinet, J.: Perfect Lattices in Euclidean Spaces, vol. 327. Springer, Heidelberg (2013). doi:10.1007/978-3-662-05167-2 · Zbl 1017.11031 |
| [42] | Mezzadri, F.: How to generate random matrices from the classical compact groups. arXiv preprint arXiv:math-ph/0609050 (2006) · Zbl 1156.22004 |
| [43] | Nguyen, P.Q., Regev, O.: Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 271-288. Springer, Heidelberg (2006). doi:10.1007/11761679_17 · Zbl 1140.94365 |
| [44] | Elkies, N.D.: Intro to SPLAG (2002). https://people.math.harvard.edu/ elkies/M55a.02/lattice.html |
| [45] | Peikert, C., A decade of lattice cryptography, Found. Trends Theor. Comput. Sci., 10, 4, 283-424, 2016 · Zbl 1391.94788 · doi:10.1561/0400000074 |
| [46] | Plesken, W.; Souvignier, B., Computing isometries of lattices, J. Symb. Comput., 24, 3-4, 327-334, 1997 · Zbl 0882.11042 · doi:10.1006/jsco.1996.0130 |
| [47] | Regev, O.: Quantum computation and lattice problems. In: Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, pp. 520-529. IEEE Computer Society (2002). doi:10.1109/SFCS.2002.1181976 |
| [48] | Regev, O., Stephens-Davidowitz, N.: A reverse minkowski theorem. In: Hatami, H., McKenzie, P., King, V. (eds.) Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), Montreal, 19-23 June 2017, pp. 941-953. ACM (2017). doi:10.1145/3055399.3055434 · Zbl 1370.11073 |
| [49] | Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 20-22 November 1994, pp. 124-134. IEEE Computer Society (1994). doi:10.1109/SFCS.1994.365700 |
| [50] | Sikiric, M.D., Schürmann, A., Vallentin, F.: Complexity and algorithms for computing voronoi cells of lattices. Math. Comput. 78(267), 1713-1731 (2009). doi:10.1090/S0025-5718-09-02224-8 · Zbl 1215.11067 |
| [51] | Stephens-Davidowitz, N.: Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one. In: Jansen, K., Mathieu, C., Rolim, J.D.P., Umans, C. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, 7-9 September 2016, Paris. LIPIcs, vol. 60, pp. 19:1-19:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016). doi:10.4230/LIPIcs.APPROX-RANDOM.2016.19 · Zbl 1398.68685 |
| [52] | Stewart, GW, The efficient generation of random orthogonal matrices with an application to condition estimators, SIAM J. Numer. Anal., 17, 3, 403-409, 1980 · Zbl 0443.65027 · doi:10.1137/0717034 |
| [53] | Szydlo, M.: Hypercubic lattice reduction and analysis of GGH and NTRU signatures. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 433-448. Springer, Heidelberg (2003). doi:10.1007/3-540-39200-9_27 · Zbl 1038.94558 |
| [54] | Wei, W., Liu, M., Wang, X.: Finding shortest lattice vectors in the presence of gaps. In: Nyberg, K. (ed.) CT-RSA 2015. LNCS, vol. 9048, pp. 239-257. Springer, Cham (2015). doi:10.1007/978-3-319-16715-2_13 · Zbl 1332.94083 |
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.
