International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Cryptanalysis of the Repaired Public-key Encryption Scheme Based on the Polynomial Reconstruction Problem

Authors:
Jean-S├ębastien Coron
Download:
URL: http://eprint.iacr.org/2003/219
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2003-11932,
  title={Cryptanalysis of the Repaired Public-key Encryption Scheme Based on the Polynomial Reconstruction Problem},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Cryptanalysis, Augot and Finiasz cryptosystem.},
  url={http://eprint.iacr.org/2003/219},
  note={ coron@clipper.ens.fr 12338 received 10 Oct 2003, last revised 13 Oct 2003},
  author={Jean-S├ębastien Coron},
  year=2003
}