Computer Algebra, Quantum Computing and Post-Quantum Cryptography

计算机代数、量子计算和后量子密码学

• 批准号: RGPIN-2021-04223
• 负责人: Doliskani, Jake
• 金额: $ 2.48万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749806
• 关键词: Computer; Algebra; Quantum; Computing; Post

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.

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