Cryptology ePrint Archive: Report 2003/219
Cryptanalysis of the Repaired Public-key Encryption Scheme Based on the Polynomial Reconstruction Problem
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.
Category / Keywords: public-key cryptography / Cryptanalysis, Augot and Finiasz cryptosystem.
Date: received 10 Oct 2003, last revised 13 Oct 2003
Contact author: coron at clipper ens fr
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20031013:191821 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]