Post-quantum cryptography from isogenies

公钥密码术是我们今天所知的互联网安全的基础，允许双方安全地通信，而不需要事先交换机密密钥材料。今天广泛使用的所有公钥密码系统要么基于大整数的因式分解问题，要么基于在某个群中计算离散对数的问题。肖尔在1994年的一篇开创性论文中指出，这两个问题在量子计算机上都很容易解决，量子计算机使用量子力学进行计算的速度比任何经典计算机都快。从那时起，人们在构建后量子公钥密码系统这一主题上做了大量工作，以确保量子计算机的安全。在建造量子计算机方面已经取得了一些进展，尽管还没有制造出具有真正计算能力的量子计算机。然而，我们认为提前计划未来的需求是谨慎的，因为由于网络影响，通常需要几十年的时间来改变密码系统的部署。美国政府最近宣布，即将出台的计划要求所有未来的美国政府安全应用程序使用后量子密码系统，这为开发和部署后量子密码系统提供了新的动力。 我们的目标是发展后量子密码系统，以期待未来量子计算机的构建。特别是，我们的目标是基于超奇异椭圆曲线同源构造更多(也更有效)的后量子协议，我们认为与其他后量子密码学方法相比，这具有一些优势。也就是说，在所有已知的后量子密码系统中，基于同源的密码系统在以下方面是独一无二的：它们的安全级别通过简单地选择单个公共参数来确定；它们实现了尽可能小的公钥大小；它们基于数论复杂性假设；并且实现可以利用现有的广泛部署的软件库来实现必要的特征，例如侧信道弹性。我们提出了一些旨在进一步提高基于同源密码系统的性能和安全性的研究目标。此外，我们还建议开发新的后量子感知安全模型，用于目前文献中没有此类安全模型的流行协议，如认证加密和认证密钥交换。 我们期望基于同源的密码系统将成为后量子密码学的一种可行的主流选择。这样的系统对终端用户来说将比替代系统更容易管理，并且在许多情况下是现有(非后量子)密码系统的临时替代。该项目的学员将处于有利地位，将在未来量子计算和后量子密码学的发展中发挥主导作用。

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.