How does the key size in supersingular isogeny schemes relate to their security level?

Question

I'm looking at the De Feo, Jao, and Plût 2014 paper:

Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies.

My understanding of section 3.2 Key Exchange, is that Alice's private key is the isogeny $\phi_A : E \rightarrow E_A$, which can be represented by 2 integers; private key: $(m_A, n_A)$.

Her public key consists of the curve $E_A$, represented by the polynomials $a,b$ from its Weierstrass equation $E_A: y^2 = x^3 + ax + b$, and the images of the two torsion bases $P_B, Q_B$ under her private isogeny, which appear to be 2 complex points each = 8 integers. Public key: $(E_A, \phi_A(P_B), \phi_A(Q_B) )$. So my fuzzy understanding thinks that the public key should contain around 10 - 16 pieces of information, depending on how those polynomials are represented.

In the experimental section, section 7, there's a table comparing runtimes of the key exchange algorithm for key sizes of 512 bits, 768 bits, and 1024 bits.

My question: Where do those key sizes come from? Do they ever state the bit widths of the different components of the public key, and which one(s) they are varying to change the key size? Better yet, did I miss an analysis of the relationship between the key size and the security level of the system?

Answer 1

Those numbers for the key sizes come from the bit length of the prime chosen for the finite field $F_p$. To clarify, there are no complex numbers used at all. The elliptic curve is over a quadratic extension of $F_p$, i.e. $K = F_{p^2}$, and a root $i$ of $x^2+1$ is chosen, so that elements of $K$ can be represented as uniquely as elements of $F_p \oplus i\cdot F_p$, i.e. $a+ib$ for $a,b\in F_p$. If $p$ is $N$ bits long, then general elements of $K$ are $2N$ bits long. Points $(x,y)$ on the elliptic curve $E$ have $x,y \in K$, so they are then $2\cdot2N = 4N$ bits long. The coefficients of $E$ are also elements of $K$, so they're also $2N$ bits long.

The public key consists of the two $K$ coefficients to express the elliptic curve $E_A$ (so $4N$ bits), and the two points in $E_A$, $\phi_A(P_B)$ and $\phi_A(Q_B)$, which are each $4N$ bits long. The total length of the public key is then $12N$ bits. However, it is possible to compress this, as you can see in Costello-Longa-Naehrig, where they get this down to $6N$ with some clever techniques. Later work improves this to about $3.5N$ while reducing the computational effort at the same time.

The relationship between key size and security level is covered in section 5.1. So far, the best classical attack is $O(\sqrt[4]{p})$, so $N/4$ bits of classical security, and the best quantum attack is $O(\sqrt[6]{p})$, so $N/6$ bits of quantum security. That's why the 768-bit p has 768/6 = 128 bits of quantum security. I really recommend reading Costello-Longa-Naehrig, as some of the details are made more explicit.

Answer 2

The hard underlying problem of supersingular isogeny map defines the security level of the protocol. Simply put, the hard problem can be defined as follows:

Given two points $P, Q$ on $E_1$ and their images $\phi(P), \phi(Q)$ on $E_2$ , find the secret isogeny map $\phi$. The best-known attack on this problem is the Claw finding attack which has the following complexity: $\mathcal{O}(\ell^{1/2})$ and $\mathcal{O}(\ell^{1/3})$ on classical and quantum attacks, respectively, where $\ell$ is the degree of the isogeny. Therefore, if you have only 2 different torsion subgroups (SIKE and SIDH) with roughly same bit-length (balanced security), your finite field is defined over a prime of the form $p=\ell_A^{e_A}\ell_B^{e_B}-1$, and therefore since the prime bit-length is divided into only 2 parts, the security level can be described as $\mathcal{O}(p^{1/4})$ and $\mathcal{O}(p^{1/6})$ on classical and quantum attacks, respectively. However, considering other isogeny-based cryptography schemes such as Supersingular Isogeny-Based Undeniable Signature which is constructed on three different torsion subgroups, i.e. $p=\ell_A^{e_A}\ell_B^{e_B}\ell_C^{e_C}-1$, the security level would be $\mathcal{O}(p^{1/6})$ and $\mathcal{O}(p^{1/9})$ on classical and quantum attacks, respectively!