×

An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero. (English) Zbl 1404.94053

Summary: Let \(\mathbf f\) and \(\mathbf g\) be polynomials of a bounded Euclidean norm in the ring \(\mathbb{Z}[X]/\langle X^{n}+1\rangle\). Given the polynomial \([\mathbf f/\mathbf g]_{q}\in \mathbb{Z}_{q}[X]/\langle X^{n}+1\rangle\), the NTRU problem is to find \(\mathbf a,\mathbf b\in \mathbb{Z}[X]/\langle X^{n}+1\rangle\) with a small Euclidean norm such that \([\mathbf a/\mathbf b]_{q}=[\mathbf f/\mathbf g]_{q}\). We propose an algorithm to solve the NTRU problem, which runs in \(2^{O(\log^{2}\lambda)}\) time when \(\|\mathbf g\|,\|\mathbf f\|\), and \(\|\mathbf g^{-1}\|\) are within some range. The main technique of our algorithm is the reduction of a problem on a field to one on a subfield. The GGH scheme, the first candidate of an (approximate) multilinear map, was recently found to be insecure by the Hu-Jia attack using low-level encodings of zero, but no polynomial-time attack was known without them. In the GGH scheme without low-level encodings of zero, our algorithm can be directly applied to attack this scheme if we have some top-level encodings of zero and a known pair of plaintext and ciphertext. Using our algorithm, we can construct a level-\(0\) encoding of zero and utilize it to attack a security ground of this scheme in the quasi-polynomial time of its security parameter using the parameters suggested by S. Garg et al. [Eurocrypt 2013, Lect. Notes Comput. Sci. 7881, 1–17 (2013; Zbl 1300.94055)].

MSC:

94A60 Cryptography
11Y16 Number-theoretic algorithms; complexity
68Q25 Analysis of algorithms and problem complexity
68W40 Analysis of algorithms

Citations:

Zbl 1300.94055

Software:

NTRUSign; NTRU
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Miles, Advances in cryptology – CRYPTO 2016 pp 491– (2016)
[2] DOI: 10.1007/978-3-662-53018-4_6 · Zbl 1351.94019 · doi:10.1007/978-3-662-53018-4_6
[3] DOI: 10.1007/978-3-642-55220-5_14 · Zbl 1332.94071 · doi:10.1007/978-3-642-55220-5_14
[4] DOI: 10.1007/978-3-662-49890-3_21 · Zbl 1385.94044 · doi:10.1007/978-3-662-49890-3_21
[5] DOI: 10.1007/BFb0054868 · doi:10.1007/BFb0054868
[6] DOI: 10.1007/978-3-642-40041-4_26 · Zbl 1309.94139 · doi:10.1007/978-3-642-40041-4_26
[7] DOI: 10.1007/3-540-36563-X_9 · doi:10.1007/3-540-36563-X_9
[8] DOI: 10.1007/978-3-662-53008-5_21 · Zbl 1391.94739 · doi:10.1007/978-3-662-53008-5_21
[9] DOI: 10.1007/978-3-662-49890-3_20 · Zbl 1385.94020 · doi:10.1007/978-3-662-49890-3_20
[10] Gentry, Advances in cryptology – EUROCRYPT 2002 (2002)
[11] Cheon, Advances in cryptology – EUROCRYPT 2015 pp 3– (2015)
[12] Garg, Theory of cryptography 2015 pp 498– (2015)
[13] DOI: 10.1007/978-3-642-38348-9_1 · Zbl 1300.94055 · doi:10.1007/978-3-642-38348-9_1
[14] Bos, Cryptography and coding 2013 pp 45– (2013)
[15] DOI: 10.1007/978-3-642-40041-4_3 · Zbl 1310.94141 · doi:10.1007/978-3-642-40041-4_3
[16] DOI: 10.1090/conm/324/05731 · doi:10.1090/conm/324/05731
[17] DOI: 10.1007/978-3-662-47989-6_13 · Zbl 1375.94116 · doi:10.1007/978-3-662-47989-6_13
[18] DOI: 10.1007/978-3-662-48800-3_31 · Zbl 1382.94041 · doi:10.1007/978-3-662-48800-3_31
[19] López-Alt, Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing 2012 pp 1219– (2012)
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.