1999 | OriginalPaper | Chapter
Cryptanalysis of “2R” Schemes
Authors : Ye Ding-Feng, Lam Kwok-Yan, Dai Zong-Duo
Published in: Advances in Cryptology — CRYPTO’ 99
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The function decomposition problem can be stated as: Given the algebraic expression of the composition of two mappings, how can we identify the two factors? This problem is believed to be in general intractable [1]. Based on this belief, J. Patarin and L. Goubin designed a new family of candidates for public key cryptography, the so called “2R—schemes” [10], [11]. The public key of a “2R”-scheme is a composition of two quadratic mappings, which is given by n polynomials in n variables over a finite field K with q elements. In this paper, we contend that a composition of two quadratic mappings can be decomposed in most cases as long as q > 4. Our method is based on heuristic arguments rather than rigorous proofs. However, through computer experiments, we have observed its effectiveness when applied to the example scheme “D**” given in [10].