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.
Type de document :
Communication dans un congrès
Biham, Eli. EUROCRYPT 2003, May 2003, Warsaw, Poland. Srpinger, 2656, pp.229-249, 2003, Lecture Notes in Computer Science. 〈http://www.springerlink.de/content/k61v1wgre681gky9/〉. 〈10.1007/3-540-39200-9_14〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00509191
Contributeur : Daniel Augot <>
Soumis le : mardi 10 août 2010 - 16:11:40
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : vendredi 12 novembre 2010 - 11:44:53

Fichiers

Augot.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Daniel Augot, Matthieu Finiasz. A Public Key Encryption Scheme Based on the Polynomial Reconstruction Problem. Biham, Eli. EUROCRYPT 2003, May 2003, Warsaw, Poland. Srpinger, 2656, pp.229-249, 2003, Lecture Notes in Computer Science. 〈http://www.springerlink.de/content/k61v1wgre681gky9/〉. 〈10.1007/3-540-39200-9_14〉. 〈inria-00509191〉

Partager

Métriques

Consultations de la notice

193

Téléchargements de fichiers

276