Post-quantum cryptography from isogenies

点击翻译按钮获取中文摘要

Public-key cryptography is the foundation of internet security as we know it today, allowing for two parties to communicate securely without the need to exchange confidential key material in advance. All public key cryptosystems in widespread use today are based on either the problem of factoring large integers, or the problem of computing discrete logarithms in some group. In a seminal paper from 1994, Shor showed that both of these problems would be easy to solve on a quantum computer, one which uses quantum mechanics to perform calculations faster than any classical computer can achieve. Since then, much work has been done on the topic of constructing post-quantum public-key cryptosystems which would be secure against quantum computers. Some progress towards constructing quantum computers has been made, although no quantum computers with serious computing power have yet been built. Nevertheless, we believe it is prudent to plan ahead for future needs, because it normally takes many decades to change cryptosystem deployments, due to network effects. Recent announcements by the US government of upcoming plans to require post-quantum cryptosystems for all future US government security applications have provided new impetus to develop and deploy post-quantum cryptosystems. Our goal is to develop post-quantum cryptosystems in anticipation of the future construction of quantum computers. In particular, we aim to construct more (and more efficient) post-quantum protocols based on supersingular elliptic curve isogenies, which we believe offer several advantages compared to other approaches for post-quantum cryptography. Namely, isogeny-based cryptosystems are unique among all known post-quantum cryptosystems in the following ways: their security level is determined by a simple choice of a single public parameter; they achieve the smallest possible public key size; they are based on number-theoretic complexity assumptions; and implementations can leverage existing widely deployed software libraries to achieve necessary features such as side-channel resilience. We propose a number of research objectives intended to further improve the performance and security of isogeny-based cryptosystems. In addition, we also propose to develop new post-quantum aware security models for popular protocols for which no such security models are currently available in the literature, such as authenticated encryption and authenticated key exchange. We expect that isogeny-based cryptosystems will emerge as a viable mainstream option for post-quantum cryptography. Such systems will be much easier for end users to manage than the alternatives, and in many cases represent drop-in replacements for existing (non-post-quantum) cryptosystems. Student trainees from the project will be well-positioned to play a leading role in the future development of quantum computing and post-quantum cryptography.