Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice | Designs, Codes and Cryptography Skip to main content
Springer Nature Link
Log in

Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

In Eurocrypt 2004 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 (PR). 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Augot D, Finiasz M (2003) A public key encryption scheme based on the polynomial reconstruction problem. In:Biham E(ed) Advances in Cryptology—EUROCRYPT 2003, international conference on the theory and applications of cryptographic techniques, Warsaw, Poland,Proceedings. Lecture notes in computer science, vol 2656. Springer, Heildelberg, pp 229–240

  2. Augot D, Finiasz M, Loidreau P (2003) Using the trace operator to repair the polynomial reconstruction based cryptosystem presented at Eurocrypt 2003. Cryptology ePrint Archive. Report 2003/209. http://eprint.iacr.org/

  3. Berlekamp ER, Welch L (1986) Error correction of algebraic block codes. US Patent 4,633,470

  4. Chvátal V (1979). The tail of the hypergeometric distribution. Discrete Math 25: 285–287

    Article  MATH  MathSciNet  Google Scholar 

  5. Coron J-S (2003) Cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem, Cryptology ePrint Archive, Report 2003/036. http://eprint.iacr.org/

  6. Coron J-S (2003) Cryptanalysis of the repaired public-key encryption scheme based on the polynomial reconstruction problem, Cryptology ePrint Archive, Report 2003/219. http://eprint.iacr.org/

  7. Coron J-S (2004) Cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem. In: Bao F, Deng RH, Zhou J (eds) Public Key Cryptography—PKC 2004, 7th international workshop on theory and practice in public key cryptography, Singapore Lecture notes in computer science, vol 2947., pp 14–27. Springer, Heidelberg

  8. Guruswami V, Sudan M (1998) Improved decoding of Reed-Solomon and algebraic-geometric codes. In: Proceedings of the 39th annual symposium on foundations of computer science, Palo Alto, California, November 8–11, IEEE Computer Society, pp 28–39

  9. Kiayias A, Yung M (2002) Cryptographic hardness based on the decoding of Reed-Solomon codes. In: Proceedings of ICALP 2002. Lecture notes in computer science, vol 2380. Malaga, Spain, July 8–13, pp 232–243

  10. Kiayias A, Yung M (2004) Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice. In: Proceedings of Advances in Cryptology ASIACRYPT 2004, the 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5–9, Lecture Notes in Computer Science, vol 3329, pp 401–416

  11. McEliece RJ (1978). A public key cryptosystem based on algebraic coding theory. Jet Propulsion Lab, DSN Progress Report 42(44): 114–116

    Google Scholar 

  12. McEliece RJ (2003) The Guruswami-Sudan decoding algorithm for Reed-Solomon codes, IPN Progress Report 42–153 http://ipnpr.jpl.nasa.gov/tmo/progress_report/42-153/153F.pdf

  13. Schwartz JT (1980). Fast probabilistic algorithms for verifications of polynomial identities. JACM 27(4): 701–717

    Article  MATH  Google Scholar 

  14. Sudan M (1997). Decoding of Reed Solomon codes beyond the error-correction bound. J Complex 13(1): 180–193

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science and Eng. Dept., University of Connecticut, Storrs, CT, USA

    Aggelos Kiayias

  2. Computer Science Dept., Columbia University, New york, USA

    Moti Yung

Authors
  1. Aggelos Kiayias
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Moti Yung
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Aggelos Kiayias.

Additional information

Communicated by P. Wild.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kiayias, A., Yung, M. Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice. Des Codes Crypt 43, 61–78 (2007). https://doi.org/10.1007/s10623-007-9055-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-007-9055-8

Keywords

AMS Classification