Algebraic attack on NTRU using Witt vectors and Gröbner bases
We present an algebraic attack on NTRU (restricted to the case where the parameter q is a power of two) using the method of the Witt vectors proposed by Silverman, Smart and Vercauteren [Springer: 278–298, 2005]; the latter considered only the first two bits of a Witt vector attached to the recoveri...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2009-09-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/JMC.2009.011 |
| _version_ | 1811279453258514432 |
|---|---|
| author | Bourgeois Gérald Faugère Jean-Charles |
| author_facet | Bourgeois Gérald Faugère Jean-Charles |
| author_sort | Bourgeois Gérald |
| collection | DOAJ |
| description | We present an algebraic attack on NTRU (restricted to the case where the parameter q is a power of two) using the method of the Witt vectors proposed by Silverman, Smart and Vercauteren [Springer: 278–298, 2005]; the latter considered only the first two bits of a Witt vector attached to the recovering of the secret key in order to reduce the problem to the resolution of an algebraic system over 𝔽2. The theoretical complexity of this resolution was not studied by the authors. In this paper, we use the first three bits of the Witt vectors to obtain supplementary equations which allow us to reduce the complexity of the attack. Using Gröbner basis complexity results of overdetermined systems, we have been able to provide a theoretical complexity analysis. Additionally we provide experimental results illustrating the efficiency of this approach. Moreover, we prove that the use of the fourth bit does not improve the complexity, what is surprising. Unfortunately, for standard values of the NTRU parameters, the proven complexity is around 2246 and this attack does not make it possible to find the private key. |
| first_indexed | 2024-04-13T00:54:54Z |
| format | Article |
| id | doaj.art-fb49600960dd46f39df4667c404021cd |
| institution | Directory Open Access Journal |
| issn | 1862-2976 1862-2984 |
| language | English |
| last_indexed | 2024-04-13T00:54:54Z |
| publishDate | 2009-09-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-fb49600960dd46f39df4667c404021cd2022-12-22T03:09:44ZengDe GruyterJournal of Mathematical Cryptology1862-29761862-29842009-09-013320521410.1515/JMC.2009.011Algebraic attack on NTRU using Witt vectors and Gröbner basesBourgeois Gérald0Faugère Jean-Charles1Département de Mathématiques, Université de la Polynésie Francaise, BP 6570, 98702 Faa'a, Tahiti, French Polynesia, France. Email: bourgeois.gerald@gmail.comINRIA, Centre Paris-Rocquencourt, SALSA Project, UPMC, Univ Paris 06, LIP6, CNRS, UMR 7606, LIP6, Université Pierre et Marie Curie Paris 6, UFR Ingénierie 919, LIP6 Passy Kennedy, bureau 733, Boite Courrier 169, 4, Place Jussieu 75252 Paris cedex 05, France. Email: Jean-Charles.Faugere@inria.frWe present an algebraic attack on NTRU (restricted to the case where the parameter q is a power of two) using the method of the Witt vectors proposed by Silverman, Smart and Vercauteren [Springer: 278–298, 2005]; the latter considered only the first two bits of a Witt vector attached to the recovering of the secret key in order to reduce the problem to the resolution of an algebraic system over 𝔽2. The theoretical complexity of this resolution was not studied by the authors. In this paper, we use the first three bits of the Witt vectors to obtain supplementary equations which allow us to reduce the complexity of the attack. Using Gröbner basis complexity results of overdetermined systems, we have been able to provide a theoretical complexity analysis. Additionally we provide experimental results illustrating the efficiency of this approach. Moreover, we prove that the use of the fourth bit does not improve the complexity, what is surprising. Unfortunately, for standard values of the NTRU parameters, the proven complexity is around 2246 and this attack does not make it possible to find the private key.https://doi.org/10.1515/JMC.2009.011ntrualgebraic attackgröbner baseswitt vectorsfgb |
| spellingShingle | Bourgeois Gérald Faugère Jean-Charles Algebraic attack on NTRU using Witt vectors and Gröbner bases Journal of Mathematical Cryptology ntru algebraic attack gröbner bases witt vectors fgb |
| title | Algebraic attack on NTRU using Witt vectors and Gröbner bases |
| title_full | Algebraic attack on NTRU using Witt vectors and Gröbner bases |
| title_fullStr | Algebraic attack on NTRU using Witt vectors and Gröbner bases |
| title_full_unstemmed | Algebraic attack on NTRU using Witt vectors and Gröbner bases |
| title_short | Algebraic attack on NTRU using Witt vectors and Gröbner bases |
| title_sort | algebraic attack on ntru using witt vectors and grobner bases |
| topic | ntru algebraic attack gröbner bases witt vectors fgb |
| url | https://doi.org/10.1515/JMC.2009.011 |
| work_keys_str_mv | AT bourgeoisgerald algebraicattackonntruusingwittvectorsandgrobnerbases AT faugerejeancharles algebraicattackonntruusingwittvectorsandgrobnerbases |