{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T14:09:16Z","timestamp":1771942156476,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T00:00:00Z","timestamp":1720483200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T00:00:00Z","timestamp":1720483200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["EURASIP J. on Info. Security"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1186\/s13635-024-00170-7","type":"journal-article","created":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T12:06:41Z","timestamp":1720526801000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Performance comparison of quantum-safe multivariate polynomial public key encapsulation algorithm"],"prefix":"10.1186","volume":"2024","author":[{"given":"Randy","family":"Kuang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Perepechaenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan","family":"Toth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3531-4926","authenticated-orcid":false,"given":"Michel","family":"Barbeau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,9]]},"reference":[{"key":"170_CR1","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/s11128-022-03712-5","volume":"21","author":"R Kuang","year":"2022","unstructured":"R. Kuang, M. Perepechaenko, M. Barbeau, A new post-quantum multivariate polynomial public key encapsulation algorithm. Quantum Inf. Process. 21, 360 (2022)","journal-title":"Quantum Inf. Process."},{"key":"170_CR2","doi-asserted-by":"crossref","unstructured":"R. Kuang, M. Perepechaenko, R. Toth, M. Barbeau, in Risks and Security of Internet and Systems. ed. by S. Kallel, M. Jmaiel, M. Zulkernine, A. Hadj Kacem, F. Cuppens, N. Cuppens, Benchmark performance of the multivariate polynomial public key encapsulation mechanism (Springer Nature Switzerland, Cham, 2023), pp.239\u2013255","DOI":"10.1007\/978-3-031-31108-6_18"},{"key":"170_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88702-7","volume-title":"Post-quantum cryptography","author":"D Bernstein","year":"2009","unstructured":"D. Bernstein, J. Buchmann, E. Dahmen, Post-Quantum Cryptography (Springer, Berlin, 2009)"},{"issue":"2","key":"170_CR4","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1137\/S0036144598347011","volume":"41","author":"PW Shor","year":"1999","unstructured":"P.W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303\u2013332 (1999)","journal-title":"SIAM Rev."},{"issue":"2","key":"170_CR5","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","volume":"79","author":"LK Grover","year":"1997","unstructured":"L.K. Grover, Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2), 325 (1997)","journal-title":"Phys. Rev. Lett."},{"key":"170_CR6","unstructured":"Dustin Moody. Status update on the 3rd Round (NIST). https:\/\/csrc.nist.gov\/CSRC\/media\/Presentations\/status-update-on-the-3rd-round\/images-media\/session-1-moody-nist-round-3-update.pdf. Accessed 23 May 2022"},{"key":"170_CR7","unstructured":"NIST. Status report on the third round of the nist post-quantum cryptography standardization process. 2022. https:\/\/csrc.nist.gov\/publications\/detail\/nistir\/8413\/final. Accessed 4 July 2024."},{"key":"170_CR8","first-page":"114","volume":"44","author":"RJ McEliece","year":"1978","unstructured":"R.J. McEliece, A Public-Key Cryptosystem Based On Algebraic Coding Theory. Deep Space Netw. Prog. Rep. 44, 114\u2013116 (1978)","journal-title":"Deep Space Netw. Prog. Rep."},{"key":"170_CR9","first-page":"4","volume":"2","author":"R Avanzi","year":"2017","unstructured":"R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J.M. Schanck, P. Schwabe, G. Seiler, D. Stehl\u00e9, Crystals-kyber algorithm specifications and supporting documentation. NIST PQC Round. 2, 4 (2017)","journal-title":"NIST PQC Round."},{"key":"170_CR10","doi-asserted-by":"crossref","unstructured":"J. Hoffstein, J. Pipher, J.H. Silverman, in Algorithmic Number Theory. ed. by J.P. Buhler, NTRU: a ring-based public key cryptosystem (Springer, Berlin Heidelberg, Berlin, Heidelberg, 1998), pp.267\u2013288","DOI":"10.1007\/BFb0054868"},{"key":"170_CR11","unstructured":"I.F. Vercauteren. SABER: Mod-LWR based KEM (Round 3 Submission) (2017). https:\/\/www.esat.kuleuven.be\/cosic\/pqcrypto\/saber\/files\/saberspecround3.pdf. Accessed 21 June 2022"},{"key":"170_CR12","unstructured":"R. Misoczki. BIKE - BIt flipping key encapsulation (2021). https:\/\/bikesuite.org\/. Accessed 4 July 2024"},{"key":"170_CR13","unstructured":"H. Team. HQC specification (2023). https:\/\/pqc-hqc.org\/documentation.html. Accessed 34 July 2024"},{"key":"170_CR14","unstructured":"T. Matsumoto, H. Imai, in Advances, in Cryptology - EUROCRYPT \u201988. ed. by D. Barstow, W. Brauer, P. Brinch Hansen, D. Gries, D. Luckham, C. Moler, A. Pnueli, G. Seegm\u00fcller, J. Stoer, N. Wirth, C.G. G\u00fcnther, Public quadratic polynomial-tuples for efficient signature-verification and message-encryption (Springer, Berlin Heidelberg, Berlin, Heidelberg, 1988), pp.419\u2013453"},{"key":"170_CR15","doi-asserted-by":"crossref","unstructured":"J.\u00a0Ding, in Public Key Cryptography \u2013 PKC 2004, ed. by F.\u00a0Bao, R.\u00a0Deng, J.\u00a0Zhou, A new variant of the Matsumoto-Imai cryptosystem through perturbation (Springer Berlin Heidelberg, Berlin, Heidelberg, 2004), pp. 305\u2013318","DOI":"10.1007\/978-3-540-24632-9_22"},{"key":"170_CR16","first-page":"38","volume":"2006","author":"J Ding","year":"2006","unstructured":"J. Ding, J. Gower, D. Schmidt, Zhuang-zi: a new algorithm for solving multivariate polynomial equations over a finite field. IACR Cryptol. ePrint Arch. 2006, 38 (2006)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"170_CR17","first-page":"193","volume-title":"Multivariate public key cryptography","author":"J Ding","year":"2009","unstructured":"J. Ding, B.Y. Yang, Multivariate Public Key Cryptography (Springer, Berlin Heidelberg, Berlin, Heidelberg, 2009), pp.193\u2013241"},{"key":"170_CR18","doi-asserted-by":"crossref","unstructured":"J. Patarin, in Advances, in Cryptology - EUROCRYPT \u201996. ed. by U. Maurer, Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms (Springer, Berlin Heidelberg, Berlin, Heidelberg, 1996), pp. 33\u201348","DOI":"10.1007\/3-540-68339-9_4"},{"key":"170_CR19","doi-asserted-by":"crossref","unstructured":"C. Tao, A. Diene, S. Tang, J. Ding, in Post-Quantum Cryptography. ed. by P. Gaborit, Simple matrix scheme for encryption (Springer, Berlin Heidelberg, Berlin, Heidelberg, 2013), pp.231\u2013242","DOI":"10.1007\/978-3-642-38616-9_16"},{"key":"170_CR20","volume-title":"Computers and intractability: a guide to the theory of Np-completeness","author":"MR Garey","year":"1990","unstructured":"M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman and Co., USA, 1990)"},{"key":"170_CR21","unstructured":"VAMPIRE. eBACS: ECRYPT benchmarking of cryptographic systems \u2013 SUPERCOP. https:\/\/bench.cr.yp.to\/supercop.html. Accessed 4 July 2024"}],"container-title":["EURASIP Journal on Information Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13635-024-00170-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13635-024-00170-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13635-024-00170-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T12:13:44Z","timestamp":1720527224000},"score":1,"resource":{"primary":{"URL":"https:\/\/jis-eurasipjournals.springeropen.com\/articles\/10.1186\/s13635-024-00170-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,9]]},"references-count":21,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["170"],"URL":"https:\/\/doi.org\/10.1186\/s13635-024-00170-7","relation":{},"ISSN":["2510-523X"],"issn-type":[{"value":"2510-523X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,9]]},"assertion":[{"value":"28 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 July 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"23"}}