Cryptology ePrint Archive: Report 2003/036
Cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem
Abstract: We describe a cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem. Given the public-key and a ciphertext, we recover the corresponding plaintext in polynomial time. Therefore, the scheme is not one-way. Our technique is a variant of the Berlekamp-Welsh algorithm.
Category / Keywords: public-key cryptography / Error-correcting codes.
Date: received 21 Feb 2003, last revised 5 Mar 2003
Contact author: coron at clipper ens fr
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Note: The attack is now proven (in the previous version, the attack was heuristic).
Version: 20030306:075436 (All versions of this report)
Short URL: ia.cr/2003/036
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]