{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T18:43:37Z","timestamp":1769193817288,"version":"3.49.0"},"reference-count":25,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2023,3,17]],"date-time":"2023-03-17T00:00:00Z","timestamp":1679011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003093","name":"Ministry of Higher Education Malaysia","doi-asserted-by":"publisher","award":["FRGS\/1\/2019\/STG06\/UPM\/02\/8"],"award-info":[{"award-number":["FRGS\/1\/2019\/STG06\/UPM\/02\/8"]}],"id":[{"id":"10.13039\/501100003093","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003093","name":"Ministry of Higher Education Malaysia","doi-asserted-by":"publisher","award":["UPM\/INSPEM\/ 700-3\/1\/GERAN ANTARABANGSA\/6380071\u201310065"],"award-info":[{"award-number":["UPM\/INSPEM\/ 700-3\/1\/GERAN ANTARABANGSA\/6380071\u201310065"]}],"id":[{"id":"10.13039\/501100003093","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003093","name":"Ministry of Higher Education Malaysia","doi-asserted-by":"publisher","award":["MMUI\/220141"],"award-info":[{"award-number":["MMUI\/220141"]}],"id":[{"id":"10.13039\/501100003093","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Mediterranea Universiti of Reggio Calabria (UNIRC) Research","award":["FRGS\/1\/2019\/STG06\/UPM\/02\/8"],"award-info":[{"award-number":["FRGS\/1\/2019\/STG06\/UPM\/02\/8"]}]},{"name":"Mediterranea Universiti of Reggio Calabria (UNIRC) Research","award":["UPM\/INSPEM\/ 700-3\/1\/GERAN ANTARABANGSA\/6380071\u201310065"],"award-info":[{"award-number":["UPM\/INSPEM\/ 700-3\/1\/GERAN ANTARABANGSA\/6380071\u201310065"]}]},{"name":"Mediterranea Universiti of Reggio Calabria (UNIRC) Research","award":["MMUI\/220141"],"award-info":[{"award-number":["MMUI\/220141"]}]},{"name":"MMU Postdoc","award":["FRGS\/1\/2019\/STG06\/UPM\/02\/8"],"award-info":[{"award-number":["FRGS\/1\/2019\/STG06\/UPM\/02\/8"]}]},{"name":"MMU Postdoc","award":["UPM\/INSPEM\/ 700-3\/1\/GERAN ANTARABANGSA\/6380071\u201310065"],"award-info":[{"award-number":["UPM\/INSPEM\/ 700-3\/1\/GERAN ANTARABANGSA\/6380071\u201310065"]}]},{"name":"MMU Postdoc","award":["MMUI\/220141"],"award-info":[{"award-number":["MMUI\/220141"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Axioms"],"abstract":"<jats:p>The Polynomial Reconstruction Problem (PRP) was introduced in 1999 as a new hard problem in post-quantum cryptography. Augot and Finiasz were the first to design a cryptographic system based on a univariate PRP, which was published at Eurocrypt 2003 and was broken in 2004. In 2013, a bivariate PRP was proposed. The design is a modified version of Augot and Finiasz\u2019s design. Our strategic method, comprising the modified Berlekamp\u2013Welch algorithm and Coron strategies, allowed us to obtain certain secret parameters of the bivariate PRP. This finding resulted in us concluding that the bivariate PRP is not secure against Indistinguishable Chosen-Plaintext Attack (IND-CPA).<\/jats:p>","DOI":"10.3390\/axioms12030304","type":"journal-article","created":{"date-parts":[[2023,3,17]],"date-time":"2023-03-17T02:59:26Z","timestamp":1679021966000},"page":"304","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["An IND-CPA Analysis of a Cryptosystem Based on Bivariate Polynomial Reconstruction Problem"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-7564-9516","authenticated-orcid":false,"given":"Siti Nabilah","family":"Yusof","sequence":"first","affiliation":[{"name":"Institute for Mathematical Research (INSPEM), Universiti Putra Malaysia, Serdang 43400, Selangor, Malaysia"}]},{"given":"Muhammad Rezal","family":"Kamel Ariffin","sequence":"additional","affiliation":[{"name":"Institute for Mathematical Research (INSPEM), Universiti Putra Malaysia, Serdang 43400, Selangor, Malaysia"},{"name":"Department of Mathematics and Statistics, Faculty of Science, Universiti Putra Malaysia, Serdang 43400, Selangor, Malaysia"}]},{"given":"Terry Shue Chien","family":"Lau","sequence":"additional","affiliation":[{"name":"Faculty of Computing and Informatics, Multimedia University, Cyberjaya 63100, Selangor, Malaysia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7941-1878","authenticated-orcid":false,"given":"Nur Raidah","family":"Salim","sequence":"additional","affiliation":[{"name":"Institute for Mathematical Research (INSPEM), Universiti Putra Malaysia, Serdang 43400, Selangor, Malaysia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8575-4244","authenticated-orcid":false,"given":"Sook-Chin","family":"Yip","sequence":"additional","affiliation":[{"name":"Faculty of Engineering, Multimedia University, Cyberjaya 63100, Selangor, Malaysia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1277-1710","authenticated-orcid":false,"given":"Timothy Tzen Vun","family":"Yap","sequence":"additional","affiliation":[{"name":"Faculty of Computing and Informatics, Multimedia University, Cyberjaya 63100, Selangor, Malaysia"}]}],"member":"1968","published-online":{"date-parts":[[2023,3,17]]},"reference":[{"key":"ref_1","unstructured":"Brassard, G., Lutkenhaus, N., Mor, T., and Sanders, B.C. (2000, January 14\u201318). Security Aspects of Practical Quantum Cryptography. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Bruges, Belgium."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Cambou, B., Gowanlock, M., Yildiz, B., Ghanaimiandoab, D., Lee, K., Nelson, S., Philabaum, C., Stenberg, A., and Wright, J. (2021). Post Quantum Cryptographic Keys Generated with Physical Unclonable Functions. Appl. Sci., 11.","DOI":"10.20944\/preprints202102.0336.v1"},{"key":"ref_3","unstructured":"Shor, P.W. (1994, January 20\u201322). Algorithms for Quantum Computation: Discrete Logarithms and Factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Song, B., and Zhao, Y. (2017). Provably Secure Identity-Based Identification and Signature Schemes From Code Assumptions. PLoS ONE, 12.","DOI":"10.1371\/journal.pone.0182894"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"2107","DOI":"10.1038\/s41598-020-58928-1","article-title":"An approach to cryptography based on continuous-variable quantum neural network","volume":"10","author":"Shi","year":"2020","journal-title":"Sci. Rep."},{"key":"ref_6","unstructured":"Jordan, S. (2023, January 05). Quantum Algorithm Zoo. Available online: https:\/\/quantumalgorithmzoo.org\/."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1391","DOI":"10.1007\/s10623-017-0402-0","article-title":"Polynomial-Time Key Recovery Attack on the Faure\u2013Loidreau Scheme Based on Gabidulin Codes","volume":"86","author":"Gaborit","year":"2018","journal-title":"Des. Codes Cryptogr."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Imran, M., Abideen, Z.U., and Pagliarini, S. (2020). An Experimental Study of Building Blocks of Lattice-Based NIST Post-Quantum Cryptographic Algorithms. Electronics, 9.","DOI":"10.3390\/electronics9111953"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Naor, M., and Pinkas, B. (1999, January 1\u20134). Oblivious Transfer and Polynomial Evaluation. Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, Atlanta, GA, USA.","DOI":"10.1145\/301250.301312"},{"key":"ref_10","first-page":"978","article-title":"Directions in Polynomial Reconstruction Based Cryptography","volume":"87","author":"Kiayias","year":"2004","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1757","DOI":"10.1109\/18.782097","article-title":"Improved decoding of Reed-Solomon and Algebraic-Geometry Codes","volume":"45","author":"Guruswami","year":"1999","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Augot, D., and Finiasz, M. (2003, January 4\u20138). A Public Key Encryption Scheme Based on the Polynomial Reconstruction Problem. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland.","DOI":"10.1007\/3-540-39200-9_14"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Kiayias, A., and Yung, M. (2001, January 16\u201317). Polynomial Reconstruction Based Cryptography. Proceedings of the International Workshop on Selected Areas in Cryptography, Toronto, ON, Canada.","DOI":"10.1007\/3-540-45537-X_10"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Kiayias, A., and Yung, M. (2004, January 5\u20139). Cryptanalyzing the Polynomial-Reconstruction Based Public-Key System under Optimal Parameter Choice. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Jeju, Republic of Korea.","DOI":"10.1007\/978-3-540-30539-2_28"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Coron, J.S. (2004, January 1\u20134). Cryptanalysis of a Public-Key Encryption Scheme Based on the Polynomial Reconstruction Problem. Proceedings of the International Workshop on Theory and Practice in Public Key Cryptography, Singapore.","DOI":"10.1007\/978-3-540-24632-9_2"},{"key":"ref_16","first-page":"73","article-title":"Bivariate Polynomials Public Key Encryption Schemes","volume":"4","author":"Ajeena","year":"2013","journal-title":"Int. J. Cryptol. Res."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Lin, C.Y., and Wu, J.L. (2020). Cryptanalysis and Improvement of a Chaotic Map-Based Image Encryption System Using Both Plaintext Related Permutation and Diffusion. Entropy, 22.","DOI":"10.3390\/e22050589"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Kuwakado, H., and Morii, M. (2010, January 13\u201318). Quantum Distinguisher between the 3-Round Feistel Cipher and the Random Permutation. Proceedings of the IEEE International Symposium on Information Theory, Austin, TX, USA.","DOI":"10.1109\/ISIT.2010.5513654"},{"key":"ref_19","first-page":"31","article-title":"An Empirical Attack on a Polynomial Reconstruction Problem Potential Cryptosystem","volume":"11","author":"Yusof","year":"2021","journal-title":"Int. J. Cryptol. Res."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Bleichenbacher, D., and Nguyen, P.Q. (2000, January 14\u201318). Noisy Polynomial Interpolation and Noisy Chinese Remaindering. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Bruges, Belgium.","DOI":"10.1007\/3-540-45539-6_4"},{"key":"ref_21","unstructured":"Sadkhan, S.B., and Ruma, K.H. (2006, January 24\u201328). Evaluation of Polynomial Reconstruction Problem using Lagrange Interpolation Method. Proceedings of the 2006 2nd International Conference on Information and Communication Technologies, Damascus, Syria."},{"key":"ref_22","unstructured":"Augot, D., Finiasz, M., and Loidreau, P. (2003). Using the Trace Operator to Repair the Polynomial Reconstruction Based Cryptosystem Presented at Eurocrypt 2003. Int. Assoc. Cryptologic Res., 209."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"35","DOI":"10.23919\/JCC.2021.08.003","article-title":"Generative Trapdoors for Public Key Cryptography Based on Automatic Entropy Optimization","volume":"18","author":"Zhu","year":"2021","journal-title":"China Commun."},{"key":"ref_24","unstructured":"Carstens, T.V., Ebrahimi, E., Tabia, G.N., and Unruh, D. (2020). On Quantum Indistinguishability Under Chosen Plaintext Attack. Int. Assoc. Cryptologic Res., 596."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1049\/iet-ifs.2015.0500","article-title":"Public-Key Encryption Indistinguishable Under Plaintext-Checkable Attacks","volume":"10","author":"Abdalla","year":"2016","journal-title":"IET Inf. Secur."}],"container-title":["Axioms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2075-1680\/12\/3\/304\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:57:19Z","timestamp":1760122639000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2075-1680\/12\/3\/304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,17]]},"references-count":25,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["axioms12030304"],"URL":"https:\/\/doi.org\/10.3390\/axioms12030304","relation":{},"ISSN":["2075-1680"],"issn-type":[{"value":"2075-1680","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,17]]}}}