CORAL: Faster Isogeny Group Action for Post-Quantum NIKE

There are two kinds of cryptographic group actions: restricted and unrestricted. While unrestricted actions like (qt-)PEGASIS are needed for more advanced constructions, restricted ones like dCTIDH are sufficient for instantiating a NIKE and are usually much more efficient.

In this work, we propose CORAL, a significantly faster algorithm to evaluate the same action as (qt-)PEGASIS, but in a restricted fashion; CORAL only computes two-dimensional two-isogenies to evaluate the action and outperforms both recent unrestricted (KLaPoTi, (qt-)PEGASIS) and (restricted) CSIDH-based approaches (SQALE, dCTIDH). In essence, CORAL trades off unrestrictedness for efficiency.

Our unoptimised C implementation evaluates a group-action in 178 ms with a 2032-bit prime. When used to construct a non-interactive key exchange, CORAL yields an actively secure post-quantum NIKE with compact public keys (e.g. 256 bytes for 2032-bit primes).