Abstract | ||
---|---|---|
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]. |
Year | DOI | Venue |
---|---|---|
1999 | 10.1007/3-540-48405-1_20 | CRYPTO |
Keywords | Field | DocType |
finite field,public key cryptography,public key,functional decomposition,computer experiment | Computer experiment,Discrete mathematics,Heuristic,Finite field,Polynomial,Algebra,Functional decomposition,Quadratic equation,Theoretical computer science,Mathematical proof,Algebraic expression,Mathematics | Conference |
ISBN | Citations | PageRank |
3-540-66347-9 | 10 | 0.66 |
References | Authors | |
9 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dingfeng Ye | 1 | 54 | 7.67 |
Kwok-Yan Lam | 2 | 440 | 69.66 |
Zong-duo Dai | 3 | 203 | 25.53 |