Authors:
(1) Randy Kuang, Quantropi Inc., Ottawa, K1Z 8P9, Canada ([email protected]);
(2) Maria Perepechaenko, Quantropi Inc., Ottawa, K1Z 8P9, Canada;
(3) Mahmoud Sayed, Systems and Computer Engineering, Carleton University, Ottawa, K1S 5B6, Canada;
(4) Dafu Lou, Quantropi Inc., Ottawa, K1Z 8P9, Canada.
Table of Links
-
Brief of Homomorphic Polynomial Public Key Cryptography and 4.1 DPPK
-
Conclusion, References, Acknowledgements, and Author contributions statement
ABSTRACT
In their 2022 study, Kuang et al. introduced the Multivariable Polynomial Public Key (MPPK) cryptography, a quantum-safe public key cryptosystem leveraging the mutual inversion relationship between multiplication and division. MPPK employs multiplication for key pair construction and division for decryption, generating public multivariate polynomials. Kuang and Perepechaenko expanded the cryptosystem into the Homomorphic Polynomial Public Key (HPPK), transforming product polynomials over large hidden rings using homomorphic encryption through modular multiplications. Initially designed for key encapsulation mechanism (KEM), HPPK ensures security through homomorphic encryption of public polynomials over concealed rings. This paper extends its application to a digital signature scheme. The framework of HPPK KEM can not be directly applied to the digital signatures dues to the different nature of verification procedure compared to decryption procedure. Thus, in order to use the core ideas of the HPPK KEM scheme in the framework of digital signatures, the authors introduce an extension of the Barrett reduction algorithm. This extension transforms modular multiplications over hidden rings into divisions in the verification equation, conducted over a prime field. The extended algorithm non-linearly embeds the signature into public polynomial coefficients, employing the floor function of big integer divisions. This innovative approach overcomes vulnerabilities associated with linear relationships of earlier MPPK DS schemes. The security analysis reveals exponential complexity for both private key recovery and forged signature attacks, taking into account that the bit length of the rings is twice that of the prime field size. The effectiveness of the proposed Homomorphic Polynomial Public Key Digital Signature (HPPK DS) scheme is illustrated through a practical toy example, showcasing its intricate functionality and enhanced security features.
1 Introduction
2 Contribution
3 Related Work
Initially, the Merkle-Hellman knapsack cryptosystem was believed to be secure, being based on the knapsack problem, considered NP-complete. However, its vulnerability was demonstrated by Shamir in 1982[12]. This vulnerability primarily stems from its super-increasing sequence of the private key and the binary vector space. Nguyen and Stern illustrated successful attacks on both Merkle-Hellman knapsack cryptosystem and its variant Qu-Vanstone scheme, using orthogonal lattice-reduction techniques in 1997[13].
In the realm of Post-Quantum Cryptography (PQC), the field of digital signatures is currently undergoing extensive exploration and development. This is in response to the potential threats posed by quantum computers to traditional cryptographic algorithms. The National Institute of Standards and Technology (NIST) initiated the standardization process for Post-Quantum Cryptography (PQC) in 2017[15], initially considering 69 candidates. The first round concluded in 2019, narrowing down the field to 26 candidates entering the second round[16].
Among these candidates, only four Key Encapsulation Mechanism (KEM) options progressed to the third round: code-based Classic McEliece[17], lattice-based CRYSTALS-KYBER[18], NTRU[19], and SABER[20]. Additionally, three digital signature candidates advanced to the third round: lattice-based CRYSTALS-DILITHIUM[21] and FALCON[22], along with multivariate Rainbow[23], as shown in NIST status report in 2021[24]. In a subsequent update, NIST declared Kyber as the sole KEM candidate for standardization[25]. For digital signatures, NIST identified CRYSTALS-Dilithium, FALCON, and SPHINCS+[26] as the three standardized algorithms.
In early 2022, vulnerabilities in the NIST round 3 finalists came to light. Damien Robert initiated this revelation by reporting an attack on Supersingular Isogeny Diffie–Hellman (SIDH) in polynomial time[27, 28]. Subsequently, Castryck and Decru presented a more efficient key recovery attack on SIDH[29], achieving key recovery for NIST security level V in under 2 hours using a laptop.
In a separate development, a novel cryptoanalysis was introduced by Emily Wenger et al. in 2022[30]. This approach utilizes Machine Learning (ML) for the secret recovery of lattice-based schemes. Wenger’s team demonstrated that their attack could fully recover secrets for small-to-midsize Learning With Errors (LWE) instances with sparse binary secrets, up to lattice dimensions of n = 128 with SALSA[30] , n = 350 with PICANTE[31], and n = 512 with VERDE[32]. The potential scalability of this attack to real-world LWE-based cryptosystems is being explored. The team is actively working on enhancing the attack’s capability to target larger parameter sets, although the timeframe and resources required for this advancement remain uncertain. Their latest publishing not only improves the secret recovery methods of SALSA but also introduce a novel cross-attention recovery mechanism[32]. Their innovative attack has ushered in a new era of cryptoanalysis, particularly when integrating ML with quantum computing.
Sharp et al. recently achieved significant breakthroughs in integer factorization, as detailed in their report[33]. Their research focuses on breaking a 300-bit RSA public key using the MemComputing technique in simulation mode. MemComputing, a novel computing paradigm characterized by time non-locality, represents a noteworthy departure from traditional computing methods. In contrast to quantum computing, which relies on physical quantum processing units and exponential quantum resources for substantial computational acceleration, MemComputing demonstrates the ability to achieve large prime factorizations with polynomial computing resources. This holds true even when using classical computing systems, although further acceleration can be attained through ASIC implementation. Notably, Zhang and Ventra have recently proposed a digital implementation of MemComputing[34]. The implications of this technological advancement suggest that classical cryptography may become vulnerable sooner than anticipated, potentially outpacing the threat posed by quantum computers.
This paper is