Cryptanallysis of 2R(-) schemes
(2006) 26th Annual International Cryptology Conference — Location: Santa Barbara(Ca) (20.August.2006)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- In this paper, we study the security of 2R(-) schemes [17,18], which are the "minus variant" of two-round schemes. This variant consists in removing some of the n polynomials of the public key, and permits to thwart an attack described at Crypto'99 [25] against two-round schemes. Usually, the "minus variant" leads to a real strengthening of the considered schemes. We show here that this is actually not true for 2R(-) schemes. We indeed propose an efficient algorithm for decomposing 2R(-) schemes. For instance, we can remove up to [(n)/(2)] equations and still be able to recover a decomposition in O(n(12)). We provide experimental results illustrating the efficiency of our approach. In practice, we have been able to decompose 2R(-) schemes in less than a handful of hours for most of the challenges proposed by the designers [18]. We believe that this result makes the principle of two-round schemes, including 2R(-) schemes, useless.
- Affiliations
Citations
Faugere, J.-C., & Perret, L. (2006). Cryptanallysis of 2R(-) schemes. Lecture Notes in Computer Science, 4117, 357-372. https://hdl.handle.net/2078.5/23511 (Original work published 2006)