A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem
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...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-02-01
|
| Series: | Heliyon |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2405844024015019 |
| _version_ | 1827322285781942272 |
|---|---|
| author | Siti Nabilah Yusof Muhammad Rezal Kamel Ariffin Sook-Chin Yip Terry Shue Chien Lau Zahari Mahad Ji-Jian Chin Choo-Yee Ting |
| author_facet | Siti Nabilah Yusof Muhammad Rezal Kamel Ariffin Sook-Chin Yip Terry Shue Chien Lau Zahari Mahad Ji-Jian Chin Choo-Yee Ting |
| author_sort | Siti Nabilah Yusof |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-08T03:30:03Z |
| format | Article |
| id | doaj.art-23b139b89183424daf571094d07fe185 |
| institution | Directory Open Access Journal |
| issn | 2405-8440 |
| language | English |
| last_indexed | 2024-04-25T01:22:11Z |
| publishDate | 2024-02-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Heliyon |
| spelling | doaj.art-23b139b89183424daf571094d07fe1852024-03-09T09:25:26ZengElsevierHeliyon2405-84402024-02-01104e25470A failure in decryption process for bivariate polynomial reconstruction problem cryptosystemSiti Nabilah Yusof0Muhammad Rezal Kamel Ariffin1Sook-Chin Yip2Terry Shue Chien Lau3Zahari Mahad4Ji-Jian Chin5Choo-Yee Ting6Institute for Mathematical Research, Universiti Putra Malaysia, 43400 UPM Serdang, Selangor, MalaysiaInstitute for Mathematical Research, Universiti Putra Malaysia, 43400 UPM Serdang, Selangor, Malaysia; Department of Mathematics and Statistics, Faculty of Science, Universiti Putra Malaysia, Selangor, Malaysia; Corresponding author at: Institute for Mathematical Research, Universiti Putra Malaysia, 43400 UPM Serdang, Selangor, Malaysia.Faculty of Engineering, Multimedia University, Cyberjaya 63100, Selangor, Malaysia; Corresponding author.Faculty of Computing and Informatics, Multimedia University, Cyberjaya 63100, Selangor, MalaysiaInstitute for Mathematical Research, Universiti Putra Malaysia, 43400 UPM Serdang, Selangor, MalaysiaSchool of Engineering, Computing and Mathematics (Faculty of Science and Engineering), University of Plymouth, Drake Circus, Plymouth PL 48AA, UKFaculty of Computing and Informatics, Multimedia University, Cyberjaya 63100, Selangor, MalaysiaIn 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.http://www.sciencedirect.com/science/article/pii/S2405844024015019Polynomial reconstruction problemPost-quantum cryptographyDecryption failureUnivariate polynomialBivariate polynomial |
| spellingShingle | Siti Nabilah Yusof Muhammad Rezal Kamel Ariffin Sook-Chin Yip Terry Shue Chien Lau Zahari Mahad Ji-Jian Chin Choo-Yee Ting A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem Heliyon Polynomial reconstruction problem Post-quantum cryptography Decryption failure Univariate polynomial Bivariate polynomial |
| title | A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem |
| title_full | A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem |
| title_fullStr | A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem |
| title_full_unstemmed | A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem |
| title_short | A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem |
| title_sort | failure in decryption process for bivariate polynomial reconstruction problem cryptosystem |
| topic | Polynomial reconstruction problem Post-quantum cryptography Decryption failure Univariate polynomial Bivariate polynomial |
| url | http://www.sciencedirect.com/science/article/pii/S2405844024015019 |
| work_keys_str_mv | AT sitinabilahyusof afailureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem AT muhammadrezalkamelariffin afailureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem AT sookchinyip afailureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem AT terryshuechienlau afailureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem AT zaharimahad afailureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem AT jijianchin afailureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem AT chooyeeting afailureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem AT sitinabilahyusof failureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem AT muhammadrezalkamelariffin failureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem AT sookchinyip failureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem AT terryshuechienlau failureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem AT zaharimahad failureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem AT jijianchin failureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem AT chooyeeting failureindecryptionprocessforbivariatepolynomialreconstructionproblemcryptosystem |