A new quantum-safe multivariate polynomial public key digital signature algorithm
Abstract We propose a new quantum-safe digital signature algorithm called Multivariate Polynomial Public Key Digital Signature (MPPK/DS). The core of the algorithm is based on the modular arithmetic property that for a given element g, greater than equal to two, in a prime Galois field GF(p) and two...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2022-08-01
|
| Series: | Scientific Reports |
| Online Access: | https://doi.org/10.1038/s41598-022-15843-x |
| _version_ | 1798038057786540032 |
|---|---|
| author | Randy Kuang Maria Perepechaenko Michel Barbeau |
| author_facet | Randy Kuang Maria Perepechaenko Michel Barbeau |
| author_sort | Randy Kuang |
| collection | DOAJ |
| description | Abstract We propose a new quantum-safe digital signature algorithm called Multivariate Polynomial Public Key Digital Signature (MPPK/DS). The core of the algorithm is based on the modular arithmetic property that for a given element g, greater than equal to two, in a prime Galois field GF(p) and two multivariate polynomials P and Q, if P is equal to Q modulo p-1, then g to the power of P is equal to g to the power of Q modulo p. MPPK/DS is designed to withstand the key-only, chosen-message, and known-message attacks. Most importantly, making secret the element g disfavors quantum computers’ capability to solve the discrete logarithm problem. The security of the MPPK/DS algorithm stems from choosing a prime p associated with the field GF(p), such that p is a sum of a product of an odd prime number q multiplied with a power x of two and one. Given such a choice of a prime, choosing even coefficients of the publicly available polynomials makes it hard to find any private information modulo p-1. Moreover, it makes it exponentially hard to lift the solutions found modulo q to the ring of integers modulo p-1 by properly arranging x and q. However, finding private information modulo the components q and power x of two is an NP-hard problem since it involves solving multivariate equations over the chosen finite field. The time complexity of searching a private key from a public key or signatures is exponential over GF(p). The time complexity of perpetrating a spoofing attack is also exponential for a field GF(p). MPPK/DS can achieve all three NIST security levels with optimized choices of multivariate polynomials and the generalized safe prime p. |
| first_indexed | 2024-04-11T21:35:02Z |
| format | Article |
| id | doaj.art-96f998a229f246baa2a8e0b64fe5cce6 |
| institution | Directory Open Access Journal |
| issn | 2045-2322 |
| language | English |
| last_indexed | 2024-04-11T21:35:02Z |
| publishDate | 2022-08-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Scientific Reports |
| spelling | doaj.art-96f998a229f246baa2a8e0b64fe5cce62022-12-22T04:01:47ZengNature PortfolioScientific Reports2045-23222022-08-0112112110.1038/s41598-022-15843-xA new quantum-safe multivariate polynomial public key digital signature algorithmRandy Kuang0Maria Perepechaenko1Michel Barbeau2Quantropi Inc.Quantropi Inc.School of Computer Science, Carleton UniversityAbstract We propose a new quantum-safe digital signature algorithm called Multivariate Polynomial Public Key Digital Signature (MPPK/DS). The core of the algorithm is based on the modular arithmetic property that for a given element g, greater than equal to two, in a prime Galois field GF(p) and two multivariate polynomials P and Q, if P is equal to Q modulo p-1, then g to the power of P is equal to g to the power of Q modulo p. MPPK/DS is designed to withstand the key-only, chosen-message, and known-message attacks. Most importantly, making secret the element g disfavors quantum computers’ capability to solve the discrete logarithm problem. The security of the MPPK/DS algorithm stems from choosing a prime p associated with the field GF(p), such that p is a sum of a product of an odd prime number q multiplied with a power x of two and one. Given such a choice of a prime, choosing even coefficients of the publicly available polynomials makes it hard to find any private information modulo p-1. Moreover, it makes it exponentially hard to lift the solutions found modulo q to the ring of integers modulo p-1 by properly arranging x and q. However, finding private information modulo the components q and power x of two is an NP-hard problem since it involves solving multivariate equations over the chosen finite field. The time complexity of searching a private key from a public key or signatures is exponential over GF(p). The time complexity of perpetrating a spoofing attack is also exponential for a field GF(p). MPPK/DS can achieve all three NIST security levels with optimized choices of multivariate polynomials and the generalized safe prime p.https://doi.org/10.1038/s41598-022-15843-x |
| spellingShingle | Randy Kuang Maria Perepechaenko Michel Barbeau A new quantum-safe multivariate polynomial public key digital signature algorithm Scientific Reports |
| title | A new quantum-safe multivariate polynomial public key digital signature algorithm |
| title_full | A new quantum-safe multivariate polynomial public key digital signature algorithm |
| title_fullStr | A new quantum-safe multivariate polynomial public key digital signature algorithm |
| title_full_unstemmed | A new quantum-safe multivariate polynomial public key digital signature algorithm |
| title_short | A new quantum-safe multivariate polynomial public key digital signature algorithm |
| title_sort | new quantum safe multivariate polynomial public key digital signature algorithm |
| url | https://doi.org/10.1038/s41598-022-15843-x |
| work_keys_str_mv | AT randykuang anewquantumsafemultivariatepolynomialpublickeydigitalsignaturealgorithm AT mariaperepechaenko anewquantumsafemultivariatepolynomialpublickeydigitalsignaturealgorithm AT michelbarbeau anewquantumsafemultivariatepolynomialpublickeydigitalsignaturealgorithm AT randykuang newquantumsafemultivariatepolynomialpublickeydigitalsignaturealgorithm AT mariaperepechaenko newquantumsafemultivariatepolynomialpublickeydigitalsignaturealgorithm AT michelbarbeau newquantumsafemultivariatepolynomialpublickeydigitalsignaturealgorithm |