Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies

We present new candidates for quantum-resistant public-key cryptosystems based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. The main technical idea in our scheme is that we transmit the images of torsion bases under the isogeny in order to allow the two parties to arrive at a common shared key despite the noncommutativity of the endomorphism ring. Our work is motivated by the recent development of a subexponential-time quantum algorithm for constructing isogenies between ordinary elliptic curves. In the supersingular case, by contrast, the fastest known quantum attack remains exponential, since the noncommutativity of the endomorphism ring means that the approach used in the ordinary case does not apply. We give a precise formulation of the necessary computational assumption along with a discussion of its validity. In addition, we present implementation results showing that our protocols are multiple orders of magnitude faster than previous isogeny-based cryptosystems over ordinary curves.

我们基于在超奇异椭圆曲线之间寻找同源（isogenies）的推测难度，提出了抗量子公钥密码系统的新候选方案。我们方案中的主要技术思路是，我们传输同源下挠基（torsion bases）的像，以便双方能够得到一个共同的共享密钥，尽管自同态环（endomorphism ring）是非交换的。我们的工作是受到最近构建普通椭圆曲线之间同源的亚指数时间量子算法发展的推动。相比之下，在超奇异情形下，已知最快的量子攻击仍然是指数级的，因为自同态环的非交换性意味着普通情形中使用的方法不适用。我们给出了必要计算假设的精确表述，并讨论了其有效性。此外，我们给出的实现结果表明，我们的协议比之前基于普通曲线上同源的密码系统快多个数量级。