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)已经有经典随机多项式时间解的问题；例如，分解多项式，计算有限域的嵌入等。一个有趣的问题是，是否存在解决此类问题的最佳量子算法。