Asiacrypt 2020

This year at Asiacrypt a total of 7 papers on isogeny-based cryptography were presented. For those who couldn’t attend, I’ve briefly described each paper. I also give links to the papers and corresponding talks (on YouTube) for more details.

SQISign: Compact Post Quantum signatures from Quaternions and Isogenies

[Paper]

Winning the best paper award, De Feo, Kohel, Leroux, Petit and Wesolowski introduce a new signature scheme from isogeny graphs of supersingular elliptic curves. This paper builds on work by Galbraith, Petit and Silva (GPS) ¹ who proposed a signature scheme constructed from the KLPT algorithm ². We note that the KLPT algorithm solves the quaternion analog of the $l$-isogeny path problem under the Deuring correspondence. The GPS scheme was mainly theoretical and was not implemented (to the best of my knowledge).

In the SQISign paper, a new generic KLPT algorithm is presented, which produces a smaller output than the original algorithm. Using this, the authors construct a new interactive zero knowledge identification protocol, resulting in an unforgeable signature scheme. New algorithms for efficient instantiation of the protocol, parameters targeting NIST-1 level post-quantum security and a complete implementation of the signature scheme in both C and Magma are also given in the paper.

Cryptographic Group Actions and Applications

[Paper] [Talk]

In my opinion this paper tackles two issues with isogeny-based cryptography:

• For someone without a strong Maths background, who for example doesn’t know what an isogeny is, it’s quite a difficult to get into this field and develop cryptographic primitives based on isogenies.

• Isogenies are not as expressive as lattices, so it is harder (and maybe not even possible) to construct certain primitives with isogenies. However, having primitives with post-quantum instantiations based only on lattice assumptions is dangerous as an attack on the underlying hardness problems for lattices may be found in the future.

This paper by Alamati, De Feo, Montgomery and Patranabis proposes a new framework based on group actions that enables the use of isogeny-based assumptions, even for those who aren’t extremely familiar with the underlying maths. The authors achieve this by abstracting the group action and hardness assumptions in CSIDH ³ and CSI-FiSh ⁴. This new framework can be leveraged to construct several primitives not previously known from isogeny-based assumptions, such as smooth projective hashing, dual-mode PKE and a Naor-Raingold style PRF.

In addition, they introduce a new assumption over group actions, called the Linear Hidden Shift assumption. This can be used to obtain symmetric KDM-secure encryption, which in turn enables the construction of many other primitives.

B-SIDH: Supersingular Isogeny Diffie-Hellman Using Twisted Torsion

[Paper] [Talk]

In SIDH, a prime $p = 2^m3^n - 1$ is used and Alice and Bob represent each isomorphism class by a supersingular curve $E/\mathbb{F}_{p^2}$ with group order #$E(\mathbb{F}_{p^2}) = (p+1)^2 = (2^m3^n)^2$. This choice was made by Jao and De Feo to allow full $\mathbb{F}_{p^2}$-rational $2^m$-torsion and full $\mathbb{F}_{p^2}$-rational $3^n$-torsion. This means that the corresponding isogeny computations are also $\mathbb{F}_{p^2}$-rational, and so can be done efficiently.

However, Costello observes that there are in general two choices of $\mathbb{F}_{p^2}$-rational elliptic curve groups corresponding to every node in the supersingular isogeny graph: those whose group orders are $(p+1)^2$ and those whose groups orders are $(p-1)^2$. Elliptic curves from these two sets are not isomorphic over $\mathbb{F}_{p^2}$, but they are isomorphic over $\mathbb{F}_{p^4}$ and so have the same $j$-invariant.

Using this, a variant of SIDH, called B-SIDH, is constucted. An important fact shown by Costello is that we can still work over $\mathbb{F}_{p^2}$ while using both curves. The use of both curves unlocks a wealth of trade-offs. For example, B-SIDH can give significantly smaller key sizes with no known loss of security. Adj, Chi-Domínguez and Rodríguez-Henríquez present a concrete analysis of B-SIDH’s efficiency ⁵, showing B-SIDH outperforms any CSIDH instantiation. However, it is still less efficient than SIDH. Techniques developed in eSIDH ⁶ could also be used to introduce parallelisation and facilitate computations.

The search for smooth parameters that will give a reasonably efficient B-SIDH protocol is non-trivial and is a key focus of the paper, as well as a topic of subsequent research ⁷. With respect to security, as at least one of Alice or Bob must now perform walks comprised of steps in multiple $l$-isogeny graphs, the underlying hardness assumption is slightly different. However, there is no reason to believe this modification makes the problem easier as long as the number of destination nodes remains roughly the same size as in SIDH.

Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices

[Paper] [Talk]

This paper constructs concretely efficient logarithmic ring signatures and linkable ring signatures from isogeny-based and lattice-based hardness assumptions, giving Calamari and Falafl respectively. First, Beullens, Katsumata and Pintore construct a (linkable) ring signature scheme based on a group action that satisfies certain cryptographic propoerties and then instantiate with the CSIDH group action or a MLWE-bsaed group action.

A key advantage of this scheme is that the signature scheme scales well with the ring size $N$ compared to other logarithmic (linkable) ring signatures. Indeed, the term in the signature size that depends on $\log N$ is independent of the SIDH or lattice parameters. Instead, it is due to to the signatures containing a small number of paths in Merkle trees of depth $\log N$.

For the isogeny istantiation, they consider the CSIDH-512 parameter set used in CSI-FiSh ⁴. The authors then give an estimate for the signature size: $\log N + 3.5$ KB, and a signing time of 79s for $N = 8$. As is usually the case, we get smaller signatures but longer signing time compared to the lattice-based instantiation.

Radical Isogenies

[Paper] [Talk]

This paper is mainly concerned with improving the efficiency of isogeny computations. Castryck, Decru, and Vercauteren introduce a new approach called ‘radical isogenies’ and a corresponding method to compute chains of $N$-isogenies, which is very efficient for small $N$. Indeed, compared to the state-of-the-art, their method results in an order of magnitude speed-up for $N \leq 13$. When applied to CSIDH, it gives a speed-up of about 19\% over the implementation in ⁸ for the CSURF-512 parameters ⁹.

Oblivious Pseudorandom Functions from Isogenies

[Paper] [Talk]

In this paper, Boneh, Kogan and Woo construct an oblivious PRF (OPRF) and a verifiable OPRF from isognies. The first construction uses isogenies of supersingular curves over $\mathbb{F}_{p^2}$ and adapted the Diffie-Hellman OPRF to this setting. In order to overcome the attack due to Galbraith, Petit, Shani and Ti presented at Asiacrypt 2016 ¹⁰, they develop two zero-knowledge protocols to convince each party they were sent valid messages. This construction results in an OPRF in the SIDH setting. The second construction is a Naor-Reingold-like PRF in the CSIDH setting.

SiGamal: A Supersingular Isogeny-Based PKE and Its Application to a PRF

[Paper] [Talk]

SiGamal is a PKE scheme, similar to ElGamal, which is based on CSIDH and provides IND-CPA security without using hash functions. The paper also constructs a compressed version of SiGamal called C-SiGamal. The security is based on decisional problem closely related to that of CSIDH, which arises from the assumed difficulty of computing the image of a given point under a hidden isogeny.

There is, however, a trade-off with efficiency. The computational costs of group actions in SiGamal-512 sending 256-bit plaintexts are around $2.6 \times$ that of a group action in CSIDH-512. Furthermore, SiGamal is not IND-CCA secure. Increasing efficiency and finding a PKE scheme that achieves IND-CCA security without the use of hash functions are possible directions of future research.

In the paper, Moriya, Onuki and Takagi also propose a Naor-Reingold type PRF based on SiGamal. They defined a new hardness assumption and show their proposed function is a PRF provided it holds. This new assumption guarantees the security of CSIDH that uses a prime $p$ in the setting of SiGamal. The authors also estimate the computational costs of the group actions needed to compute the PRF.