Cryptography Reference
In-Depth Information
computer could easily break the scheme, and indeed in this case the scheme is
also easily broken classically by using a few calls to the oracle to compute a gen-
erator of the kernel of the dual isogeny φ A . However, it does not seem possible
to translate the values of φ A on E 0 [ e B ]intovalueson E 0 [ e A ].
Finally, we discuss the possibility of adapting the quantum algorithm of Childs
et al. [5] for the ordinary case to the supersingular case. For both ordinary and
supersingular curves, there is a natural bijection between isogenies (up to isomor-
phism) and (left) ideal classes in the endomorphism ring. The algorithm of Childs
et al. depends crucially on the fact that the ideal classes in the ordinary case form
an abelian group. In the supersingular case, the endomorphism ring is a maximal
order in a noncommutative quaternion algebra, and the left ideal classes do not
form a group at all (multiplication is not well defined). Thus we believe that no
reasonable variant of this strategy would apply to supersingular curves.
6
Implementation Results and Example
We have implemented our cryptosystem in the computer algebra system Sage [17]
using a mixed C/Cython/Sage architecture. This allows us to access the large
palette of number theoretic algorithms distributed with Sage, while still permit-
ting very ecient code in C/Cython for the critical parts such as the algorithms
of Section 4.2. The source code can be downloaded from the second author's web
page.
Arithmetic in
F p 2
is written in C. We use the library GMP for arithmetic
F p 2 [ X ] / ( X 2 + 1) (this requires p =
3 mod 4); using this representation, one multiplication in
modulo p . The field
F p 2
is implemented as
F p 2 requires three mul-
tiplications (3 M )in F p ,one
F p 2
squaring requires two multiplications (2 M )in
F p ,andone
F p 2 inversion requires one inversion, two squarings, and two multi-
plications ( I +2 S +2 M )in
F p . Our experiments show that, for the sizes we are
interested in, I =10 M and S =0 . 8 M .
We implemented the isogeny-based key exchange algorithm for =2 , 3and
the multiplication-based algorithm for > 2. The main loop is implemented in
Cython, while the isogeny evaluation and the Montgomery ladder formulas are
writteninC.
Finally, the parameter generation is implemented in plain Sage. Because Sage
is a collection of many open source mathematical systems, various of its subsys-
tems are involved in this last part. Of these, Pari [23] plays an important role
because it is used to compute Hilbert class polynomials and to factor polynomials
over finite fields.
All tests ran on a 2.4 GHz Opteron running in 64-bit mode. The results are
summarized in Table 2. At the quantum 128-bit security level (768-bit p ), our
numbers improve upon Stolbunov's reported performance figures [19, Table 1]
by over two orders of magnitude (.758 seconds vs. 229 seconds). This is the
highest security level appearing in [19, Table 1], so comparisons at higher levels
are di cult. Nevertheless, it seems safe to assume that the improvement is even
greater at the 256-bit security level. Our results demonstrate that the proposed
scheme is practical.
 
Search WWH ::




Custom Search