Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleCryptanalysis of $2r^-$ schemes.
Author(s) Faug`ere Jean-Charles, Ludovic Perret
TypeBook, Chapter in Book, Conference Proceeding
AbstractIn 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 ⌊n2⌋ 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.
KeywordsCryptanalysis, Functional Decomposition Problem (FDP), Gröbner bases, F5 algorithm.
URL http://link.springer.com/chapter/10.1007%2F11818175_21
PublisherBerlin: Springer
Translation No
Refereed No