Cryptology ePrint Archive: Report 2003/036

Cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem

Jean-Sebastien Coron

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