Computer Algebra, Quantum Computing and Post-Quantum Cryptography

点击翻译按钮获取中文摘要

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.