Paper 2004/217

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

Aggelos Kiayias and Moti Yung

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.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. extended version of abstract that appears in Asiacrypt '04
Keywords
cryptanalysis
Contact author(s)
aggelos @ cse uconn edu
History
2004-09-01: received
Short URL
https://ia.cr/2004/217
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/217,
      author = {Aggelos Kiayias and Moti Yung},
      title = {Cryptanalyzing the Polynomial-Reconstruction based Public-Key System Under Optimal Parameter Choice},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/217},
      year = {2004},
      url = {https://eprint.iacr.org/2004/217}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.