nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Computing Generator in Cyclotomic Integer Rings

A Subfield Algorithm for the Principal Ideal Problem in and Application to the Cryptanalysis of a FHE Scheme

verfasst von : Jean-François Biasse, Thomas Espitau, Pierre-Alain Fouque, Alexandre Gélin, Paul Kirchner

Erschienen in: Advances in Cryptology – EUROCRYPT 2017

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

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 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).

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 Short Generators Without Quantum Computers: The Case of Multiquadratics

Nächstes Kapitel Robust Transforming Combiners from Indistinguishability Obfuscation to Functional Encryption

Nur mit Berechtigung zugänglich

Short means that we have a norm. In our case, it is derived from the canonical embedding of the number field into a Euclidean space.

There was a small mistake in the original description which was corrected in a subsequent version.

BKZ and DBKZ are exponential in the block size.

One should notice that if m is a prime power, \(\zeta _m^i-1\) is not a unit, but \(\mathbf {b}_i\) is.

The definition of the HNF is recalled for completeness in Appendix A.

The smallest security parameters of the Smart and Vercauteren scheme is \(N = 256\).

Justification of this choice appears explicitly when we study the complexity of the \(\mathfrak {q}\)-descent in the algorithm.

We can always run an additional step in the \(\mathfrak {q}\)-descent without changing the whole complexity.

Another possibility is to use the saturation method which might run in polynomial time [7].

Factorizing an integer N is done in \(L_N\left( 1/3\right) \).

We define here the absolute norm of an ideal.

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

Bach, E.: Explicit bounds for primality testing and related problems. Math. Comput. 55, 355–380 (1990)MathSciNetCrossRefMATH

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)

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)MathSciNetCrossRefMATH

Biasse, J.F.: Subexponential time relations in the class group of large degree number fields. Adv. Math. Commun. 8(4), 407–425 (2014)MathSciNetCrossRefMATH

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)

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)

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)MathSciNetCrossRefMATH

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)

10.

Bistritz, Y., Lifshitz, A.: Bounds for resultants of univariate and bivariate polynomials. Linear Algebra Appl. 432, 1995–2005 (2010)MathSciNetCrossRefMATH

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., Erdős, P., Pomerance, C.: On a problem of Oppenheim concerning ‘factorisatio numerorum’. J. Number Theory 17, 1–28 (1983)MathSciNetCrossRefMATH

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)MATH

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 CrossRef

18.

Dixon, J.D.: Exact solution of linear equations using \(p\)-adic expansions. Numer. Math. 40, 137–141 (1982)MathSciNetCrossRefMATH

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 CrossRef

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)

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 CrossRef

23.

Hafner, J.L., McCurley, K.S.: A rigorous subexponential algorithm for computation of class groups. J. Am. Math. Soc. 2, 839–850 (1989)MathSciNetCrossRefMATH

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 CrossRef

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 CrossRef

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)MathSciNetCrossRefMATH

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 CrossRef

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)

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 CrossRef

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)

32.

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. J. ACM 60(6), 1–23 (2013)MathSciNetCrossRefMATH

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 CrossRef

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)

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 CrossRef

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)

37.

Miller, J.C.: Class numbers of totally real fields and applications to the Weber class number problem. Acta Arith. 164, 381–397 (2014)MathSciNetCrossRefMATH

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)MathSciNetCrossRefMATH

41.

Seysen, M.: A probabilistic factorization algorithm with quadratic forms of negative discriminant. Math. Comput. 84, 757–780 (1987)MathSciNetCrossRefMATH

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 CrossRef

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 CrossRef

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)CrossRefMATH

Titel: Computing Generator in Cyclotomic Integer Rings
verfasst von: Jean-François Biasse
Thomas Espitau
Pierre-Alain Fouque
Alexandre Gélin
Paul Kirchner
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2017
Print ISBN: 978-3-319-56619-1

Electronic ISBN: 978-3-319-56620-7

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-56620-7_3

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"