Authors:
(1) Randy Kuang, Quantropi Inc., Ottawa, K1Z 8P9, Canada (randy.kuang@quantropi.com);
(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. Authors: Authors: (1) Randy Kuang, Quantropi Inc., Ottawa, K1Z 8P9, Canada (randy.kuang@quantropi.com); (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 Abstract and 1. Introduction Abstract and 1. Introduction Contribution


Related Work


Brief of Homomorphic Polynomial Public Key Cryptography and 4.1 DPPK
4.2 MPPK Key Encapsulation Mechanism
4.3 HPPK KEM
4.4 MPPK DS


HPPK Digital Signature Scheme
5.1 HPPK DS Algorithm
5.2 Signing
5.3 Verify
5.4 A Variant of the Barrett Reduction Algorithm
5.5 A Toy Example


HPPK DS Security Analysis


Conclusion, References, Acknowledgements, and Author contributions statement Contribution Contribution Contribution Related Work Related Work Related Work Brief of Homomorphic Polynomial Public Key Cryptography and 4.1 DPPK
4.2 MPPK Key Encapsulation Mechanism
4.3 HPPK KEM
4.4 MPPK DS Brief of Homomorphic Polynomial Public Key Cryptography and 4.1 DPPK Brief of Homomorphic Polynomial Public Key Cryptography and 4.1 DPPK 4.2 MPPK Key Encapsulation Mechanism 4.2 MPPK Key Encapsulation Mechanism 4.3 HPPK KEM 4.3 HPPK KEM 4.4 MPPK DS 4.4 MPPK DS HPPK Digital Signature Scheme
5.1 HPPK DS Algorithm
5.2 Signing
5.3 Verify
5.4 A Variant of the Barrett Reduction Algorithm
5.5 A Toy Example HPPK Digital Signature Scheme HPPK Digital Signature Scheme 5.1 HPPK DS Algorithm 5.1 HPPK DS Algorithm 5.2 Signing 5.2 Signing 5.3 Verify 5.3 Verify 5.4 A Variant of the Barrett Reduction Algorithm 5.4 A Variant of the Barrett Reduction Algorithm 5.5 A Toy Example 5.5 A Toy Example HPPK DS Security Analysis HPPK DS Security Analysis HPPK DS Security Analysis Conclusion, References, Acknowledgements, and Author contributions statement Conclusion, References, Acknowledgements, and Author contributions statement 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 available on arxiv under ATTRIBUTION-NONCOMMERCIAL-SHAREALIKE 4.0 INTERNATIONAL license. This paper is available on arxiv under ATTRIBUTION-NONCOMMERCIAL-SHAREALIKE 4.0 INTERNATIONAL license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

A Beginner’s Guide to the HPPK Digital Signature Scheme

What You Should Know About the Next Generation of Encryption

EScholar Technologies

Too Long; Didn't Read

CTA: Download the FREE AI Productivity Shift report

The Barrett Algorithm Reimagined for Post-Quantum Signatures

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

How HPPK DS Balances Security and Efficiency Across NIST Levels

What You Should Know About the Next Generation of Encryption

A Beginner’s Guide to the HPPK Digital Signature Scheme

How HPPK DS Balances Security and Efficiency Across NIST Levels

Exploring Decentralization With Homomorphic Encryption

How HPPK DS Balances Security and Efficiency Across NIST Levels

What You Should Know About the Next Generation of Encryption

A Beginner’s Guide to the HPPK Digital Signature Scheme

How HPPK DS Balances Security and Efficiency Across NIST Levels

Exploring Decentralization With Homomorphic Encryption

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps