An elliptic curve trapdoor system (Q2499265): Difference between revisions

The paper proposes a trapdoor system based on a pair \((E_s, E_{pb})\)\, of isogenous elliptic curves defined over the field \(\mathbb F_{2^{161}}\),\, which can be useful in cryptographic key escrow applications (allowing wire tapping under legal authorization). The pair \((E_s, E_{pb})\)\, is defined as follows: The (secret) curve \(E_s\)\, is a cryptographically interesting elliptic curve over \(\mathbb F_{2^{161}}= \mathbb F_{{(2^{23})}^7} \),\, such that the GHS Weil attack [see \textit{P. Gaudry, F. Hess}, and \textit{N. P. Smart}, J. Crypto. 15, 19--46 (2002; Zbl 0996.94036)] produces a hyperelliptic curve over \(\mathbb F_{2^{23}}\)\, of genus 7 (i.e. \(m=4\), and \(g=2^{m-1}-1\), where \(m\)\, is the magic number for \(E\)). This only happens for a small fraction of all elliptic curves over \(\mathbb F_{2^{161}}\). For technical reasons \(E_s\) is also chosen with square free discriminant D (then for any elliptic curve \(E\),\, isogenous to \(E_s\), the ring End\((E)\)\, is the maximal order of \(Q(\sqrt D)\), and for any prime \(l\) the volcano of \(l\)-isogenies of \(E\) reduces to the crater, see \textit{D. Kohel} [PhD. Thesis, U. of California (1996)]). The curve \(E_{pb}\)\, is isogenous to \(E_s\)\, (selected by a pseudo-random walk in the isogeny class of \(E_s\)) but with \(m=7\). \(E_{pb}\) is public and can be used for implementation of the elliptic curve discrete logarithm problem (ECDLP) while \(E_s\)\, is kept by a trusted authority. The GHS attack allows to reduce the ECDLP over \(E_s\)\, to a HCDLP over a hyperelliptic curve of genus 7, problem feasible using the \textit{A. Enge, P. Gaudry} index calculus method [Acta Arith. 102, 83--103 (2002; Zbl 1028.11079)], but not trivial: in the author's words \` \` can be solved in an estimated 25.000 days on a 1 GHz workstation''. This way the authority, knowing \(E_s\)\, and perhaps the isogeny relating \(E_s\) and \(E_{pb}\)\, can, if necessary, solve any instance of ECDLP over \(E_{pb}\), but \` \` has to invest a considerable amount of computation, which make applications such as widespread wire-tapping impossible''. The first two sections of the paper are introductory. Section 3 studies the behavior of the magic number \(m\) under isogenies. Details of the construction of the trapdoor system are given in section 4, its security is analyzed in section 5 and its efficiency in section 6. Section 7 studies other (binary) finite fields which can also be used for a similar trapdoor: Table 3 list all finite fields \(\mathbb F_{2^N},\, (150<N<600)\)\, that are possible suitable. An appendix gives an instance of the trapdoor system.