A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem

Siti Nabilah Yusof; Muhammad Rezal Kamel Ariffin; Sook-Chin Yip; Terry Shue Chien Lau; Zahari Mahad; Ji-Jian Chin; Choo-Yee Ting

doi:10.1016/j.heliyon.2024.e25470

A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem

Heliyon. 2024 Feb 1;10(4):e25470. doi: 10.1016/j.heliyon.2024.e25470. eCollection 2024 Feb 29.

Authors

Siti Nabilah Yusof¹, Muhammad Rezal Kamel Ariffin^{1

2}, Sook-Chin Yip³, Terry Shue Chien Lau⁴, Zahari Mahad¹, Ji-Jian Chin⁵, Choo-Yee Ting⁴

Affiliations

¹ Institute for Mathematical Research, Universiti Putra Malaysia, 43400 UPM Serdang, Selangor, Malaysia.
² Department of Mathematics and Statistics, Faculty of Science, Universiti Putra Malaysia, Selangor, Malaysia.
³ Faculty of Engineering, Multimedia University, Cyberjaya 63100, Selangor, Malaysia.
⁴ Faculty of Computing and Informatics, Multimedia University, Cyberjaya 63100, Selangor, Malaysia.
⁵ School of Engineering, Computing and Mathematics (Faculty of Science and Engineering), University of Plymouth, Drake Circus, Plymouth PL 48AA, UK.

Abstract

In 1999, the Polynomial Reconstruction Problem (PRP) was put forward as a new hard mathematics problem. A univariate PRP scheme by Augot and Finiasz was introduced at Eurocrypt in 2003, and this cryptosystem was fully cryptanalyzed in 2004. In 2013, a bivariate PRP cryptosystem was developed, which is a modified version of Augot and Finiasz's original work. This study describes a decryption failure that can occur in both cryptosystems. We demonstrate that when the error has a weight greater than the number of monomials in a secret polynomial, p, decryption failure can occur. The result of this study also determines the upper bound that should be applied to avoid decryption failure.

Keywords: Bivariate polynomial; Decryption failure; Polynomial reconstruction problem; Post-quantum cryptography; Univariate polynomial.