Abstract
We describe a cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem, published at Eurocrypt 2003 by Augot and Finiasz. Given the public-key and a ciphertext, we recover the corresponding plaintext in polynomial time. Our technique is a variant of the Berlekamp-Welsh algorithm. We also describe a cryptanalysis of the reparation published by the authors on the IACR eprint archive, using a variant of the previous attack. Both attacks are practical as given the public-key and a ciphertext, one recovers the plaintext in a few minutes on a single PC.
Chapter PDF
Similar content being viewed by others
Keywords
References
Augot, D., Finiasz, M.: A Public Key encryption scheme based on the Polynomial Reconstruction problem. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 229–240. Springer, Heidelberg (2003)
Augot, D., Finiasz, M., Loidreau, P.: Using the Trace Operator to repair the Polynomial Reconstruction based Cryptosystem. Presented at Eurocrypt 2003, Cryptology ePrint Archive, Report 2003/209 (September 30, 2003), http://eprint.iacr.org/
Berlekamp, E.R., Welch, L.R.: Error correction for algebraic block codes. US Patent 4 633 470 (1986)
Bleichenbacher, D., Kiayias, A., Yung, M.: Decoding of Interleaved Reed Solomon Codes over Noisy Data. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 97–108. Springer, Heidelberg (2003)
Coron, J.S.: Cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem. Cryptology ePrint Archive, Report 2003/036 (March 5, 2003), http://eprint.iacr.org/
Gemmell, P., Sudan, M.: Highly resilient correctors for multivariate polynomials. Information Processing Letters 43(4), 169–174 (1992)
Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and Algebraic- Geometric codes. IEEE Transactions on Information Theory 45, 1757–1767 (1999)
Kiayias, A., Yung, M.: Cryptographic hardness based on the decoding of Reed- Solomon codes with applications. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 232–243. Springer, Heidelberg (2002)
Kiayias, A., Yung, M.: Cryptanalysis of the polynomial reconstruction based public-key cryptosystem of Eurocrypt 2003 in the optimal parameter setting (2003) available at, http://www.cse.uconn.edu/~akiayias/
Naor, M., Pinkas, B.: Oblivious transfer and polynomial evaluation. In: STOC 1999, pp. 245–254. ACM, New York (1999)
Reed, I.S., Solomon, G.: Polynomial codes over certain finite fields. J. SIAM 8, 300–304 (1960)
Shoup, V.: NTL: A Library for doing Number Theory (version 5.3.1), publicly available at, www.shoup.net
Shoup, V.: A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. In: Proc. 1991 International Symposium on Symbolic and Algebraic Computation, pp. 14–21 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Coron, JS. (2004). Cryptanalysis of a Public-Key Encryption Scheme Based on the Polynomial Reconstruction Problem. In: Bao, F., Deng, R., Zhou, J. (eds) Public Key Cryptography – PKC 2004. PKC 2004. Lecture Notes in Computer Science, vol 2947. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24632-9_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-24632-9_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21018-4
Online ISBN: 978-3-540-24632-9
eBook Packages: Springer Book Archive