You are looking at a specific version 20031013:191821 of this paper. See the latest version.

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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.