Computational Problems in Post-Quantum Cryptography

The security of current public-key cryptosystems relies on the hardness of factoring large integers or solving discrete logarithm problems. However, these computational problems can be solved in polynomial time using a quantum computer. This vulnerability has prompted research into post-quantum cryptography (PQC) using alternative mathematical problems that are secure in the era of quantum computers. In this talk, we give an overview of recent developments in the research on PQC. We explain a standardization project of PQC conducted by the National Institute of Standards and Technology (NIST). We then introduce an efficient digital signature, QR-UOV, based on the hardness of solving a system of multivariate quadratic polynomial equations over a finite field (the MQ problem). We also introduce a computational challenge problem, Fukuoka MQ Challenge, which aims at evaluating the hardness of the MQ problem with practical parameters.