Skip to Main content Skip to Navigation
Conference papers

A Public Key Encryption Scheme Based on the Polynomial Reconstruction Problem

Daniel Augot 1 Matthieu Finiasz 1 
1 CODES - Coding and cryptography
Inria Paris-Rocquencourt
Abstract : The Polynomial Reconstruction problem (PR) has been introduced in 1999 as a new hard problem. Several cryptographic primitives established on this problem have been constructed, for instance Naor and Pinkas have proposed a protocol for oblivious polynomial evaluation. Then it has been studied from the point of view of robustness, and several important properties have been discovered and proved by Kiayias and Yung. Furthermore the same authors constructed a symmetric cipher based on the PR problem. In the present paper, we use the published security results and construct a new public key encryption scheme based on the hardness of the problem of Polynomial Reconstruction. The scheme presented is the first public key encryption scheme based on this Polynomial Reconstruction problem. We also present some attacks, discuss their performances and state the size of the parameters required to reach the desired security level. In conclusion, this leads to a cryptosystem where the cost of encryption and decryption per bit is low, and where the public key is kept relatively small.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Daniel Augot Connect in order to contact the contributor
Submitted on : Tuesday, August 10, 2010 - 4:11:40 PM
Last modification on : Thursday, February 3, 2022 - 11:14:34 AM
Long-term archiving on: : Friday, November 12, 2010 - 11:44:53 AM


Files produced by the author(s)




Daniel Augot, Matthieu Finiasz. A Public Key Encryption Scheme Based on the Polynomial Reconstruction Problem. EUROCRYPT 2003, May 2003, Warsaw, Poland. pp.229-249, ⟨10.1007/3-540-39200-9_14⟩. ⟨inria-00509191⟩



Record views


Files downloads