Fulltext

A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem

Yusof SN 1 , Kamel Ariffin MR 1 , Yip SC 2 , Lau TSC 3 , Mahad Z 1 , Chin JJ 4 Show all authors , Ting CY 3

Affiliations 

  • 1 Institute for Mathematical Research, Universiti Putra Malaysia, 43400 UPM Serdang, Selangor, Malaysia
  • 2 Faculty of Engineering, Multimedia University, Cyberjaya 63100, Selangor, Malaysia
  • 3 Faculty of Computing and Informatics, Multimedia University, Cyberjaya 63100, Selangor, Malaysia
  • 4 School of Engineering, Computing and Mathematics (Faculty of Science and Engineering), University of Plymouth, Drake Circus, Plymouth PL 48AA, UK
Heliyon, 2024 Feb 29;10(4):e25470.
PMID: 38370193 DOI: 10.1016/j.heliyon.2024.e25470

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.

* Title and MeSH Headings from MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine.

Similar publications