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

Aggelos Kiayias, Moti Yung

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2004
Subtitle of host publication10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings
Place of Publication978-3-540-23975-8
PublisherSpringer Berlin Heidelberg
Number of pages16
ISBN (Electronic)978-3-540-30539-2
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'Cryptanalyzing the Polynomial-Reconstruction Based Public-Key System Under Optimal Parameter Choice'. Together they form a unique fingerprint.

Cite this