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

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

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

5 Downloads (Pure)

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.

Original language	English
Article number	e25470
Journal	Heliyon
Volume	10
Issue number	4
DOIs	https://doi.org/10.1016/j.heliyon.2024.e25470
Publication status	Published - 9 Feb 2024

ASJC Scopus subject areas

Multidisciplinary

Keywords

Bivariate polynomial
Decryption failure
Polynomial reconstruction problem
Post-quantum cryptography
Univariate polynomial

Access to Document

10.1016/j.heliyon.2024.e25470

camera ready heliyonAccepted author manuscript, 228 KB

Cite this

@article{188abaf418844d8db6e39aab26805e75,

title = "A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem",

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",

author = "Yusof, {Siti Nabilah} and {Kamel Ariffin}, {Muhammad Rezal} and Yip, {Sook Chin} and Lau, {Terry Shue Chien} and Zahari Mahad and Chin, {Ji Jian} and Ting, {Choo Yee}",

note = "Publisher Copyright: {\textcopyright} 2024 The Author(s)",

year = "2024",

month = feb,

day = "9",

doi = "10.1016/j.heliyon.2024.e25470",

language = "English",

volume = "10",

journal = "Heliyon",

issn = "2405-8440",

publisher = "Elsevier Ltd.",

number = "4",

}

TY - JOUR

T1 - A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem

AU - Yusof, Siti Nabilah

AU - Kamel Ariffin, Muhammad Rezal

AU - Yip, Sook Chin

AU - Lau, Terry Shue Chien

AU - Mahad, Zahari

AU - Chin, Ji Jian

AU - Ting, Choo Yee

PY - 2024/2/9

Y1 - 2024/2/9

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

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

KW - Bivariate polynomial

KW - Decryption failure

KW - Polynomial reconstruction problem

KW - Post-quantum cryptography

KW - Univariate polynomial

UR - http://www.scopus.com/inward/record.url?scp=85185153195&partnerID=8YFLogxK

UR - https://pearl.plymouth.ac.uk/context/secam-research/article/2900/viewcontent/camera_ready_heliyon.pdf

U2 - 10.1016/j.heliyon.2024.e25470

DO - 10.1016/j.heliyon.2024.e25470

M3 - Article

AN - SCOPUS:85185153195

SN - 2405-8440

VL - 10

JO - Heliyon

JF - Heliyon

IS - 4

M1 - e25470

ER -

A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this