A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem

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...

Full description

Bibliographic Details
Main Authors: Siti Nabilah Yusof, Muhammad Rezal Kamel Ariffin, Sook-Chin Yip, Terry Shue Chien Lau, Zahari Mahad, Ji-Jian Chin, Choo-Yee Ting
Format: Article
Language:English
Published: Elsevier 2024-02-01
Series:Heliyon
Subjects:
Polynomial reconstruction problem
Post-quantum cryptography
Decryption failure
Univariate polynomial
Bivariate polynomial
Online Access:http://www.sciencedirect.com/science/article/pii/S2405844024015019
Description
Summary: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.
ISSN:2405-8440

Similar Items