Speaker: | Takagi Tsuyoshi (Dept. of Mathematical Informatics, The University of Tokyo) |
---|---|
Title: | Computational Challenge Problems in Post-Quantum Cryptography |
Date (JST): | Wed, Jun 18, 2025, 15:30 - 17:00 |
Place: | Lecture Hall |
Abstract: |
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. References: [1] H. Furue, Y. Ikematsu, Y. Kiyomura, T. Takagi, "A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV", Asiacrypt 2021, LNCS 13093, pp.187-217, 2021. [2] T. Yasuda, X. Dahan, Y.-J. Huang, T. Takagi, K. Sakurai, "A Multivariate Quadratic Challenge toward Post-Quantum Generation Cryptography", ACM Communications in Computer Algebra, Vol.49, pp.105-107, 2015. [3] NIST Post-Quantum Cryptography Standardization https://csrc.nist.gov/projects/post-quantum-cryptography [4] 高木剛、現代暗号理論、岩波数学叢書, 2024. https://www.iwanami.co.jp/book/b652389.html |