Paper 2003/219
Cryptanalysis of the Repaired Public-key Encryption Scheme Based on the Polynomial Reconstruction Problem
Jean-Sebastien Coron
Abstract
At Eurocrypt 2003, Augot and Finiasz proposed a new public-key encryption scheme based on the polynomial reconstruction problem. The scheme was subsequently broken by Coron, who showed that given the public-key and a ciphertext, one could recover the corresponding plaintext in polynomial time. Recently, Augot, Finiasz and Loidreau published on the IACR eprint archive a reparation of the cryptosystem. The reparation is based on the trace operator, and is resistant against the previous attack. However, we describe a new cryptanalysis of the repaired scheme. Given the public-key and a ciphertext, we can still recover the corresponding plaintext in polynomial time. Our technique is a variant of the Berlekamp-Welsh algorithm, and works very well in practice, as for the proposed parameters, we recover the plaintext in less than 8 minutes on a single PC.
Metadata
- Available format(s)
-
PDF
PS
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- CryptanalysisAugot and Finiasz cryptosystem.
- Contact author(s)
- coron @ clipper ens fr
- History
- 2003-10-13: revised
- 2003-10-10: received
- See all versions
- Short URL
- https://ia.cr/2003/219
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2003/219,
author = {Jean-Sebastien Coron},
title = {Cryptanalysis of the Repaired Public-key Encryption Scheme Based on the Polynomial Reconstruction Problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2003/219},
year = {2003},
url = {https://eprint.iacr.org/2003/219}
}
