Computer Algebra, Quantum Computing and Post-Quantum Cryptography

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

• 批准号: RGPIN-2021-04223
• 负责人: Doliskani, Jake
• 金额: $ 2.48万
• 依托单位: Ryerson University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=742138
• 关键词: 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）在1980年代初提出了一种基于量子力学的新计算模型。后来，Yuri Manin（1980）和Richard Feynman（1982）观察到，量子计算机可以比经典计算机更快地模拟量子机械现象。现在，人们普遍认为，量子计算机比古典计算机更强大。 1994年，彼得·谢尔（Peter Shor）提出了用于整数分解和离散对数问题的有效量子算法。这些是当前部署安全系统中使用最广泛的计算问题之一。然后，实用量子计算机的前景将损害此类系统的安全性。为了解决这一严重的安全问题，美国国家标准技术研究所（NIST）发起了呼吁提出关于后验证后系统的建议，即可能在2016年抗拒量子计算机的潜在攻击的经典系统。该研究计划提出了解决方案，以解决某些类别的实用和理论问题 - Quantum Cryptums和Quantum Cyptum和量词计算机的实用性和理论问题。在密码图上，该程序集中在两个目标上：i）基于量词后计算假设设计有效的量子密码系统ii）设计和实施优化的基于iSEGEN的基于下降的邮政 - Quantum Systems-Quantum Systems在受限设备上。这些实现的主要应用程序将在物联网（IoT）中。在量子计算方面，目标是寻找有效的量子算法，并减少算术和代数性质问题。这些是计算机代数领域中感兴趣的问题，可以分为两组：i）不知道一般多项式时间算法的问题，例如计算一般有限基团的量子傅立叶变换。 ii）已经具有经典的随机多项式时间解决方案的问题；例如，分解多项式，有限字段的计算嵌入等。一个有趣的问题是，是否有针对此类问题的最佳量子算法。