Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures
Event details
| Date | 06.06.2013 |
| Hour | 10:00 › 11:00 |
| Speaker | Léo Ducas, Ecole Normale Supérieure, Paris |
| Location | |
| Category | Conferences - Seminars |
Lattices have attracted a lot of interest in the domain of Public Key Cryptography; and they are now well understood tools to build scheme which security can be reduced to the hardness of lattice problems
such as finding the shortest vector. Yet, the early signature scheme NTRUSign, from 2003, does not rely on those recent tools, and its security was an open question. Despite the existence of provably secure schemes, this question remains essential in practice because its efficiency is far better than provably secure ones.
A first step was done by Nguyen and Regev in 2006, showing that a "raw" version of NTRUSign was subject to a statistical attack. Precisely, they showed that the signature belong to a parallelepiped, which is related to the secret key; and that it is possible to learn that parallelepiped given enough signatures.
Yet the full version of NTRUSign contained a preventive countermeasure against this kind of attack, consisting of a adding a randomized perturbation, hoping to prevent any statistical attacks. In this work will first show that this perturbation results in a Zonotope, and that it is still possible to learn that zonotope; this attack was implemented and the full secret key could be recovered from about 5000 signatures. We will also tackle alternative perturbation techniques, interestingly leading to the famous Graph Isomorphism problem.
such as finding the shortest vector. Yet, the early signature scheme NTRUSign, from 2003, does not rely on those recent tools, and its security was an open question. Despite the existence of provably secure schemes, this question remains essential in practice because its efficiency is far better than provably secure ones.
A first step was done by Nguyen and Regev in 2006, showing that a "raw" version of NTRUSign was subject to a statistical attack. Precisely, they showed that the signature belong to a parallelepiped, which is related to the secret key; and that it is possible to learn that parallelepiped given enough signatures.
Yet the full version of NTRUSign contained a preventive countermeasure against this kind of attack, consisting of a adding a randomized perturbation, hoping to prevent any statistical attacks. In this work will first show that this perturbation results in a Zonotope, and that it is still possible to learn that zonotope; this attack was implemented and the full secret key could be recovered from about 5000 signatures. We will also tackle alternative perturbation techniques, interestingly leading to the famous Graph Isomorphism problem.
Links
Practical information
- General public
- Free
Organizer
- SuRI 2013
Contact
- Simone Muller