×

Computing generator in cyclotomic integer rings. A subfield algorithm for the principal ideal problem in \(L_{|\varDelta_\mathbb {K}|}\left(\frac{1}{2}\right)\) and application to the cryptanalysis of a FHE scheme. (English) Zbl 1410.94047

Coron, Jean-Sébastien (ed.) et al., Advances in cryptology – EUROCRYPT 2017. 36th annual international conference on the theory and applications of cryptographic techniques, Paris, France, April 30 – May 4, 2017. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 10210, 60-88 (2017).
Summary: The Principal Ideal problem (resp. Short Principal Ideal problem), shorten as PIP (resp. SPIP), consists in finding a generator (resp. short generator) of a principal ideal in the ring of integers of a number field. Several lattice-based cryptosystems rely on the presumed hardness of these two problems. In practice, most of them do not use an arbitrary number field but a power-of-two cyclotomic field. The Smart and Vercauteren fully homomorphic encryption scheme and the multilinear map of Garg, Gentry, and Halevi epitomize this common restriction. Recently, Cramer, Ducas, Peikert, and Regev [R. Cramer et al., Eurocrypt 2016, Lect. Notes Comput. Sci. 9666, 559–585 (2016; Zbl 1371.94630)]] showed that solving the SPIP in such cyclotomic rings boiled down to solving the PIP. In this paper, we present a heuristic algorithm that solves the PIP in prime-power cyclotomic fields in subexponential time \(L_{|\varDelta_\mathbb {K}|}\left(1/2\right)\), where \(\varDelta_\mathbb {K}\) denotes the discriminant of the number field. This is achieved by descending to its totally real subfield. The implementation of our algorithm allows to recover in practice the secret key of the Smart and Vercauteren scheme, for the smallest proposed parameters (in dimension 256).
For the entire collection see [Zbl 1360.94005].

MSC:

94A60 Cryptography
11Y40 Algebraic number theory computations

Citations:

Zbl 1371.94630
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adleman, L.M., DeMarrais, J.: A Subexponential algorithm for discrete logarithms over all finite fields. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 147–158. Springer, Heidelberg (1994). doi: 10.1007/3-540-48329-2_13 · Zbl 0871.11094 · doi:10.1007/3-540-48329-2_13
[2] Bach, E.: Explicit bounds for primality testing and related problems. Math. Comput. 55, 355–380 (1990) · Zbl 0701.11075 · doi:10.1090/S0025-5718-1990-1023756-8
[3] Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 10–24 (2016) · Zbl 1410.68093 · doi:10.1137/1.9781611974331.ch2
[4] Biasse, J.F.: An L(1/3) algorithm for ideal class group and regulator computation in certain number fields. Math. Comput. 83, 2005–2031 (2014) · Zbl 1346.11065 · doi:10.1090/S0025-5718-2014-02651-3
[5] Biasse, J.F.: Subexponential time relations in the class group of large degree number fields. Adv. Math. Commun. 8(4), 407–425 (2014) · Zbl 1358.11125 · doi:10.3934/amc.2014.8.407
[6] Biasse, J.F.: A fast algorithm for finding a short generator of a principal ideal of \[ \mathbb{Q}(\zeta _{2^n}) \] . arXiv:1503.03107v1 (2015)
[7] Biasse, J.F., Fieker, C.: Improved techniques for computing the ideal class group and a system of fundamental units in number fields. In: Proceedings of the 10th Algorithmic Number Theory Symposium (ANTS X) 2012, vol. 1, pp. 113–133 (2012) · Zbl 1344.11088
[8] Biasse, J.F., Fieker, C.: Subexponential class group and unit group computation in large degree number fields. LMS J. Comput. Math. 17, 385–403 (2014) · Zbl 1369.11103 · doi:10.1112/S1461157014000345
[9] Biasse, J.F., Song, F.: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 893–902 (2016) · Zbl 1409.68121 · doi:10.1137/1.9781611974331.ch64
[10] Bistritz, Y., Lifshitz, A.: Bounds for resultants of univariate and bivariate polynomials. Linear Algebra Appl. 432, 1995–2005 (2010) · Zbl 1220.13021 · doi:10.1016/j.laa.2009.08.012
[11] Buchmann, J.: A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. Séminaire de Théorie des Nombres, Paris 1988–1989, pp. 27–41 (1990)
[12] Campbell, P., Groves, M., Shepherd, D.: SOLILOQUY: a cautionary tale. In: ETSI 2nd Quantum-Safe Crypto Workshop (2014). http://docbox.etsi.org/workshop/2014/201410_CRYPTO/S07_Systems_and_Attacks/S07_Groves.pdf
[13] Canfield, E.R., Erdos, P., Pomerance, C.: On a problem of Oppenheim concerning ’factorisatio numerorum’. J. Number Theory 17, 1–28 (1983) · Zbl 0513.10043 · doi:10.1016/0022-314X(83)90002-1
[14] Cheon, J.H., Lee, C.: Approximate algorithms on lattices with small determinant. Cryptology ePrint Archive, Report 2015/461 (2015). http://eprint.iacr.org/2015/461
[15] Cohen, H.: A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics, vol. 138. Springer, New York (1993) · Zbl 0786.11071 · doi:10.1007/978-3-662-02945-9
[16] Computational Algebra Group, University of Sydney: MAGMA, version 2.22.2 (2016). http://magma.maths.usyd.edu.au/magma/
[17] Cramer, R., Ducas, L., Peikert, C., Regev, O.: Recovering short generators of principal ideals in cyclotomic rings. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 559–585. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-49896-5_20 · Zbl 1371.94630 · doi:10.1007/978-3-662-49896-5_20
[18] Dixon, J.D.: Exact solution of linear equations using \[ p \] -adic expansions. Numer. Math. 40, 137–141 (1982) · Zbl 0492.65016 · doi:10.1007/BF01459082
[19] The FPLLL development team: fplll, version 5.0 (2016). https://github.com/fplll/fplll
[20] Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-38348-9_1 · Zbl 1300.94055 · doi:10.1007/978-3-642-38348-9_1
[21] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 169–178 (2009) · Zbl 1304.94059 · doi:10.1145/1536414.1536440
[22] 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 · doi:10.1007/3-540-46035-7_20
[23] Hafner, J.L., McCurley, K.S.: A rigorous subexponential algorithm for computation of class groups. J. Am. Math. Soc. 2, 839–850 (1989) · Zbl 0702.11088 · doi:10.1090/S0894-0347-1989-1002631-0
[24] Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998). doi: 10.1007/BFb0054868 · Zbl 1067.94538 · doi:10.1007/BFb0054868
[25] Joux, A., Lercier, R., Smart, N., Vercauteren, F.: The number field sieve in the medium prime case. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 326–344. Springer, Heidelberg (2006). doi: 10.1007/11818175_19 · Zbl 1161.11417 · doi:10.1007/11818175_19
[26] Kirchner, P.: Algorithms on ideal over complex multiplication order. Cryptology ePrint Archive, Report 2016/220 (2016). http://eprint.iacr.org/2016/220
[27] Landau, E.: Neuer beweis des primzahlsatzes und beweis des primidealsatzes. Math. Ann. 56, 645–670 (1903) · JFM 34.0228.03 · doi:10.1007/BF01444310
[28] Langlois, A., Stehlé, D., Steinfeld, R.: GGHLite: more efficient multilinear maps from ideal lattices. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 239–256. Springer, Heidelberg (2014). doi: 10.1007/978-3-642-55220-5_14 · Zbl 1332.94071 · doi:10.1007/978-3-642-55220-5_14
[29] Lenstra, A.K., Lenstra Jr., H.W., Manasse, M.S., Pollard, J.M.: The number field sieve. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 564–572 (1990) · doi:10.1145/100216.100295
[30] Lenstra, H.W., 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 · doi:10.1007/978-3-662-44371-2_16
[31] Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: a modest proposal for FFT hashing. In: Fast Software Encryption, FSE 2008, pp. 54–72 (2008) · Zbl 1154.68403 · doi:10.1007/978-3-540-71039-4_4
[32] Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. J. ACM 60(6), 1–23 (2013) · Zbl 1281.68140 · doi:10.1145/2535925
[33] Lyubashevsky, V., Peikert, C., Regev, O.: A toolkit for ring-LWE cryptography. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 35–54. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-38348-9_3 · Zbl 1300.94082 · doi:10.1007/978-3-642-38348-9_3
[34] Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. In: Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS 2002, pp. 356–365 (2002) · doi:10.1109/SFCS.2002.1181960
[35] Micciancio, D., Walter, M.: Practical, predictable lattice basis reduction. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 820–849. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-49890-3_31 · Zbl 1385.94062 · doi:10.1007/978-3-662-49890-3_31
[36] Micciancio, D., Warinschi, B.: A linear space algorithm for computing the Hermite normal form. In: Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation, ISSAC 2001, pp. 231–236 (2001) · Zbl 1356.68288 · doi:10.1145/384101.384133
[37] Miller, J.C.: Class numbers of totally real fields and applications to the Weber class number problem. Acta Arith. 164, 381–397 (2014) · Zbl 1305.11098 · doi:10.4064/aa164-4-4
[38] The PARI Group, Bordeaux: PARI/GP, version 2.7.6 (2016). http://pari.math.u-bordeaux.fr/
[39] Schank, J.: LOGCVP, Pari implementation of CVP in \[ \log \mathbb{Z}[\zeta _{2^n}]^* \] (2015). https://github.com/jschanck-si/logcvp
[40] Scourfield, E.: On ideals free of large prime factors. J. Théorie Nombres Bordx. 16(3), 733–772 (2004) · Zbl 1073.11061 · doi:10.5802/jtnb.468
[41] Seysen, M.: A probabilistic factorization algorithm with quadratic forms of negative discriminant. Math. Comput. 84, 757–780 (1987) · Zbl 0619.10004 · doi:10.1090/S0025-5718-1987-0878705-X
[42] Shoup, V.: NTL: A Library for doing Number Theory, version 9.11.0 (2016). http://www.shoup.net/ntl/
[43] Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 420–443. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-13013-7_25 · Zbl 1281.94055 · doi:10.1007/978-3-642-13013-7_25
[44] Stehlé, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 617–635. Springer, Heidelberg (2009). doi: 10.1007/978-3-642-10366-7_36 · Zbl 1267.94132 · doi:10.1007/978-3-642-10366-7_36
[45] Thiel, C.: On the complexity of some problems in algorithmic algebraic number theory. Ph.D. thesis, Universität des Saarlandes (1995). https://www.cdc.informatik.tu-darmstadt.de/reports/reports/Christoph_Thiel.diss.pdf
[46] Washington, L.C.: Introduction to Cyclotomic Fields. Graduate Texts in Mathematics, vol. 83, 2nd edn. Springer, New York (1997) · Zbl 0966.11047 · doi:10.1007/978-1-4612-1934-7
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.