Paper 2022/692

LIKE – Lattice Isomorphism-based Non-Interactive Key Exchange via Group Actions

Abstract

We propose a new Diffie-Hellman-like Non-Interactive Key Exchange that uses the Lattice Isomorphisms as a building block. Our proposal also relies on a group action structure, implying a similar security setup as in the Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) protocol where Kuperberg's algorithm applies. We short label our scheme as LIKE. As with the original Diffie-Hellman protocol, our proposed scheme is also passively secure. We provide a proof-of-concept constant-time C-code implementation of LIKE, and conservatively propose LIKE-1, LIKE-3, and LIKE-5 instances with equivalent asymptotic Kuperberg's algorithm complexity than CSIDH-4096, CSIDH-6144, and CSIDH-8192. Our experiments illustrate that LIKE-1 is about 3.8x faster than CTIDH-512 (the current fastest variant of CSIDH-512), and it is about 641.271x faster than CSIDH-4096 when deriving shared keys (while LIKE-1 key generation is about 2.16x faster than CSIDH-4096); oppositely, LIKE-1 public keys are 32.25x larger than CSIDH-4096.