Computer Algebra, Quantum Computing and Post-Quantum Cryptography

数字通信系统和计算机在我们日常生活中的作用不断扩大，以及对信息隐私的需求，使密码学和安全成为计算机科学和数学中最令人着迷的学科之一。在通过信道传输之前，数字消息被加密成看起来像随机的字节序列；然后在信道的另一端将该序列解密成原始消息。管理这种通信的规则集称为安全协议，执行加密和解密的算法集称为密码系统。密码系统提供的安全性通常基于一个被认为是难以解决的计算问题；这个问题可以在数学上解决，但在经典计算机上会花费太多的时间或内存来解决。20世纪80年代初，保罗·贝尼奥夫提出了一种基于量子力学的新计算模型。后来，尤里·马宁(Yuri Manin)(1980)和理查德·费曼(Richard Feynman)(1982)观察到，量子计算机模拟量子力学现象的速度比经典计算机快得多。现在，人们普遍认为量子计算机比经典计算机更强大。1994年，Peter Shor提出了解决整数分解和离散对数问题的高效量子算法。这些都是当前部署的安全系统中使用最广泛的计算问题。因此，实用量子计算机的前景将危及此类系统的安全性。为了解决这一严重的安全问题，美国国家标准与技术研究所(NIST)在2016年发起了一项关于后量子系统的建议，即可以抵抗来自量子计算机的潜在攻击的经典系统。本研究计划针对后量子密码学和量子计算中的一类实际和理论问题提出解决方案。在密码学方面，本项目集中于两个目标：i)基于后量子计算假设设计高效的量子密码系统；ii)在受限设备上设计和实现基于同源的后量子系统的优化轻量级版本。这些实施的主要应用将是物联网(IOT)。在量子计算方面，目标是为算术和代数性质的问题寻找有效的量子算法和归约；这些问题是计算机代数领域感兴趣的问题，可以分为两组：i)尚不知道通用多项式时间算法的问题，如计算一般有限群的量子傅立叶变换。Ii)已经有经典的随机多项式时间解的问题；例如，分解多项式，计算有限域的嵌入等。一个有趣的问题是，是否有最优的量子算法来解决这些问题。

The ever expanding role of digital communication systems and computers in our everyday lives, and the need for information privacy, has made Cryptography and Security one of the most fascinating subjects in Computer Science and Mathematics. Before being transmitted over a channel, a digital message is encrypted into a random--looking sequence of bytes; this sequence is then decrypted into the original message on the other end of the channel. The set of rules governing such a communication is called a security protocol and the set of algorithms performing the encryption and decryption is called a cryptosystem. The security provided by a cryptosystem is usually based on a computational problem that is assumed to be intractable; a problem that can be solved mathematically, but would take too much time or memory to solve on a classical computer. A new model of computation, based on quantum mechanics, was proposed by Paul Benioff in the early 1980s. Later, Yuri Manin (1980) and Richard Feynman (1982) observed that quantum computers could simulate quantum mechanical phenomena exponentially faster than classical computers. Quantum computers are now widely believed to be strictly more powerful than classical computers. In 1994, Peter Shor proposed efficient quantum algorithms for the integer factorization and discrete logarithm problems. These are amongst the most widely used computational problems in currently deployed security systems. The prospects of a practical quantum computer would then compromise the security of such systems. To address this serious security concern, the National Institute of Standards and Technology (NIST) initiated a call for proposals for post-qu-antum systems, i.e., classical systems that could resist potential attacks from quantum computers, in 2016. This research program proposes solutions to a certain class of practical and theoretical problems in post--quantum cryptography and quantum computing. On the cryptography front, this program concentrates on two objectives: i) Designing efficient quantum cryptosystems based on post-quantum computational assumptions ii) Design and implementation of optimized lightweight versions of isogeny-based post--quantum systems on restricted devices. The main application for these implementations will be in the Internet of Things (IOT). On the quantum computing front, the goal is to search for efficient quantum algorithms and reductions for problems of arithmetic and algebraic nature; These are the problems that are of interest in the field of Computer Algebra, and can be divided into two sets: i) Problems for which no general polynomial time algorithm is known, such as computing the quantum Fourier transform for general finite groups. ii) Problems which already have classical randomized polynomial time solutions; for example, factoring polynomials, computing embeddings of finite fields, etc. An intriguing question is if there are optimal quantum algorithms for such problems.