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

https://hal.inria.fr/inria-00509191
Contributor : Daniel Augot <>
Submitted on : Tuesday, August 10, 2010 - 4:11:40 PM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on: : Friday, November 12, 2010 - 11:44:53 AM

Files

Augot.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

245

Files downloads

417