An IND-CPA Analysis of a Cryptosystem Based on Bivariate Polynomial Reconstruction Problem

Siti Nabilah Yusof, Muhammad Rezal Kamel Ariffin*, Terry Shue Chien Lau, Nur Raidah Salim, Sook Chin Yip*, Timothy Tzen Vun Yap

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


The Polynomial Reconstruction Problem (PRP) was introduced in 1999 as a new hard problem in post-quantum cryptography. Augot and Finiasz were the first to design a cryptographic system based on a univariate PRP, which was published at Eurocrypt 2003 and was broken in 2004. In 2013, a bivariate PRP was proposed. The design is a modified version of Augot and Finiasz’s design. Our strategic method, comprising the modified Berlekamp–Welch algorithm and Coron strategies, allowed us to obtain certain secret parameters of the bivariate PRP. This finding resulted in us concluding that the bivariate PRP is not secure against Indistinguishable Chosen-Plaintext Attack (IND-CPA).

Original languageEnglish
Article number304
Issue number3
Publication statusPublished - 17 Mar 2023


  • Indistinguishable Chosen-Plaintext Attack
  • Polynomial Reconstruction Problem
  • post-quantum cryptography

ASJC Scopus subject areas

  • Analysis
  • Algebra and Number Theory
  • Mathematical Physics
  • Logic
  • Geometry and Topology

Cite this