Performance comparison of quantum-safe multivariate polynomial public key encapsulation algorithm

被引：0
作者：
Kuang, Randy [1 ]
Perepechaenko, Maria [1 ]
Toth, Ryan [1 ]
Barbeau, Michel [2 ]
机构：
[1] Quantropi Inc, 1545 Carling Ave,Suite 620, Ottawa, ON K1Z 8P9, Canada
[2] Carleton Univ, Sch Comp Sci, 1125 Colonel By Dr, Ottawa, ON K1S 5B6, Canada
来源：
EURASIP JOURNAL ON INFORMATION SECURITY | 2024年 / 2024卷 / 01期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Post-quantum cryptography; Public-key cryptography; PQC; Key encapsulation mechanism; KEM; Multivariate polynomials; PQC performance;
D O I：
10.1186/s13635-024-00170-7
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A novel quantum-safe key encapsulation algorithm, called Multivariate Polynomial Public Key (MPPK), was recently proposed by Kuang, Perepechaenko, and Barbeau. Security of the MPPK key encapsulation mechanism does not rely on the prime factorization or discrete logarithm problems. It builds upon the NP-completeness of the modular Diophantine equation problem, for which there are no known efficient classical or quantum algorithms. Hence, it is resistant to known quantum computing attacks. The private key of MPPK comprises a pair of multivariate polynomials. In a companion paper, we analyzed the performance of MPPK when these polynomials are quadratic. The analysis highlighted the MPPK high decapsulation time. We found that, while maintaining the security strength, the polynomials can be linear. Considerable performance gains are obtained for the decapsulation process. In this article, we benchmark the linear case and compare the results with the previous quadratic case.
引用
收藏
页数：13
相关论文
共 21 条
[1]  
Avanzi, 2017, NIST PQC ROUND, V2, P1
[2]  
Bernstein D. J., 2009, Post-quantum cryptography, DOI [10.1007/978-3-540-88702-7_1, DOI 10.1007/978-3-540-88702-7_1, DOI 10.1007/978-3-540-88702-7]
[3]  
Ding J., 2006, IACR CRYPTOL EPRINT, P38
[4]  
Ding J., 2009, Multivariate public key cryptography, DOI [DOI 10.1007/978-3-540-88702-7_6, 10.1007/978-3-540-88702-7_6]
[5]  
Ding JT, 2004, LECT NOTES COMPUT SC, V2947, P305
[6]  
Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
[7]   Quantum mechanics helps in searching for a needle in a haystack [J].
Grover, LK .
PHYSICAL REVIEW LETTERS, 1997, 79 (02) :325-328
[8]  
H. Team, 2023, HQC specification
[9]  
Hoffstein J., 1998, Algorithmic Number Theory. Third International Symposium, ANTS-III. Proceedings, P267, DOI 10.1007/BFb0054868
[10]   Benchmark Performance of the Multivariate Polynomial Public Key Encapsulation Mechanism [J].
Kuang, Randy ;
Perepechaenko, Maria ;
Toth, Ryan ;
Barbeau, Michel .
RISKS AND SECURITY OF INTERNET AND SYSTEMS, CRISIS 2022, 2023, 13857 :239-255
123