International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Cryptanalyzing the Polynomial-Reconstruction based Public-Key System Under Optimal Parameter Choice

Authors:
Aggelos Kiayias
Moti Yung
Download:
URL: http://eprint.iacr.org/2004/217
Search ePrint
Search Google
Abstract: Recently, Augot and Finiasz presented a coding theoretic public key cryptosystem that suggests a new approach for designing such systems based on the Polynomial Reconstruction Problem. Their cryptosystem is an instantiation of this approach under a specific choice of parameters which, given the state of the art of coding theory, we show in this work to be sub-optimal. Coron showed how to attack the Augot and Finiasz cryptosystem. A question left open is whether the general approach suggested by the cryptosystem works or not. In this work, we show that the general approach (rather than only the instantiation) is broken as well. Our attack employs the recent powerful list-decoding mechanisms.
BibTeX
@misc{eprint-2004-12188,
  title={Cryptanalyzing the Polynomial-Reconstruction based Public-Key System Under Optimal Parameter Choice},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / cryptanalysis},
  url={http://eprint.iacr.org/2004/217},
  note={extended version of abstract that appears in Asiacrypt '04 aggelos@cse.uconn.edu 12662 received 31 Aug 2004},
  author={Aggelos Kiayias and Moti Yung},
  year=2004
}