Page 68 - programme book

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

Siti Nabilah Yusof 1, a) , Muhammad Rezal Kamel Ariffin 1, 2, b) Hailiza Kamarulhaili 3, c) and
Nur Raidah Salim 1, d)

1 Institute for Mathematical Research, Universiti Putra Malaysia,
43400 UPM Serdang, Selangor, Malaysia.
2 Department of Mathematics, Faculty of Science, Universiti Putra Malaysia,
43400 UPM Serdang, Selangor, Malaysia.
3 School of Mathematical Sciences, Universiti Sains Malaysia, 11800 USM, Penang, Malaysia

a) sitinabilahyusof@gmail.com
b) Corresponding author: rezal@upm.edu.my
c) hailiza@usm.my
d) nurraidah@upm.edu.my

Abstract. 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 univariate PRP which was published at Eurocrypt 2003 and has been broken in 2004. In 2013, a
bivariate PRP was proposed. The design is a modified version of Augot and Finiasz. Our strategized
method via modified Berlekamp-Welch Algorithm and Coron strategies, has allowed us to obtain
certain secret parameters of the bivariate PRP. This finding has resulted in us to conclude that the
bivariate PRP is not secure against indistinguishable chosen plaintext attack (IND-CPA).

Keywords: Polynomial Reconstruction Problem, post-quantum cryptography, univariate polynomial,
bivariate polynomial, chosen plaintext attack

66