Supersingular isogeny Diffie-Hellman (SIDH) is a relatively recent
proposal for a post-quantum secure key-exchange method which I will
briefly outline here.

Most post-quantum cryptography is based on lattices, codes, multivariate quadratics or hashes. See Gustavo's post for more.

A fifth category seems to slowly establish itself: Isogeny-based crypto.

These
schemes are based on the difficulty of finding an isogeny
between two supersingular elliptic curves. Isogenies are specific
rational maps between elliptic curves which must also be a group
homomorphism for the group of points on the curve.

The original proposal [Stolbunov et al., 2006]
was to use the problem of finding isogenies between ordinary elliptic
curves but this system was shown to be breakable with a quantum computer
[Childs et al., 2010]. After that it was proposed to use supersingular elliptic curves instead [De Feo et al., 2011].

SIDH
currently has significantly worse performance than lattice based
key-exchange schemes but offers much smaller key-sizes. Compared to Frodo it is 15 times slower but the key size is only one twentieth. Compared to NewHope
it is over 100 times slower at less than one third of the keysize. This
can be relevant in scenarios like IOT where cryptographic computations
require orders of magnitude less energy then actually transmitting data
via the radio.

Although finding isogenies
between curves is difficult, Vélu's formulas allow calculating an isogeny
with a given finite subgroup as its kernel. All such isogenies are
identical up to isomorphism.

Now, starting with a
public curve \(E\) that is a system parameter we have both parties,
Alice and Bob generate an isogeny for kernels \(\langle r_a \rangle,
\langle r_b\rangle\) respectively. Let \(r_a, r_b\) be any generators of
a subgroup for now. This gives us two isogenies

$$ \phi_a: E \rightarrow E_a\\

\phi_b: E \rightarrow E_b.$$

Now
we would like to exchange $E_a, E_b$ between the partners and somehow
derive a common $E_{ab}$ using the kernels we have used. Unfortunately,
$r_a$ does not even lie on $E_b$ so we have a problem.

The
solution that was proposed by De Feo et al. is to use 4 more points
$P_a, P_b, Q_a, Q_b$ on $E$ as public parameters, two for each party.
This allows constructing

$$r_a = m_aP_a + n_aQ_a\\

r_b = m_bP_b + n_bQ_b$$ using random integers $m_a, n_a, m_b, n_b$ appropriate for the order.

Now,
after calculating the isogenies $\phi_a, \phi_b$ the parties not only
exchange the curves $E_a, E_b$ but also $\phi_a(P_b), \phi_a(Q_b)$ and
$\phi_b(P_a), \phi_b(Q_a)$.

Looking at the example of Alice she can now calculate

$$m_a\phi_b(P_a)+n_a\phi_b(Q_a)
= \phi_b(m_aP_a + n_aQ_a) = \phi_b(r_a)$$ and Bob can perform the
analogous computation. Constructing another isogeny using this $\langle
\phi_b(r_a) \rangle$ and $\langle \phi_a(r_b) \rangle$ respectively
gives Alice and Bob two curves $E_{ba}, E_{ab}$ which are isomorphic and
their j-invariant can be used as a common secret.

I will leave you with this wonderfully formula laden image from the De Feo et al. paper showing the protocol.

Hi Simon,

ReplyDeleteNice introduction to isogeny :)

You said that it is slower than Frodo and NewHope. Do you know about the secure? I mean, it could a little bit naive from me but are proofs? or some estimation about the hardness of finding an isogeny?

Well, there are algorithms that are currently assumed to be the best for finding isogenies. They have a complexity of $O(p^{1/4})$ classical and $O(p^{1/6})$ post-quantum. However SIDH is not very old maybe somebody will soon find a much better attack. :)

Delete