Abstract
The Polynomial Reconstruction problem (PR) has been introduced in 1999 as a new hard problem. Several cryptographic primitives established on this problem have been constructed, for instance Naor and Pinkas have proposed a protocol for oblivious polynomial evaluation. Then it has been studied from the point of view of robustness, and several important properties have been discovered and proved by Kiayias and Yung. Furthermore the same authors constructed a symmetric cipher based on the PR problem. In the present paper, we use the published security results and construct a new public key encryption scheme based on the hardness of the problem of Polynomial Reconstruction. The scheme presented is the first public key encryption scheme based on this Polynomial Reconstruction problem. We also present some attacks, discuss their performances and state the size of the parameters required to reach the desired security level. In conclusion, this leads to a cryptosystem where the cost of encryption and decryption per bit is low, and where the public key is kept relatively small.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
A. Canteaut and F. Chabaud. A new algorithm for finding minimum-weight words in a linear code: application to primitive narrow-sense BCH codes of length 511. IEEE Transactions on Information Theory, 44(1):367–378, January 1998.
O. Goldreich, R. Rubinfeld, and M. Sudan. Learning polynomials with queries: the highly noisy case. SIAM J. of Discrete Math, 13(4):535–570, 2000.
S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270–299, April 1984.
L. Granboulan. Short signature in the random oracle model. In Y. Zheng, editor, Advances in Cryptology, Asiacrypt 2002, volume 2501 of Lecture Notes in Computer Science, pages 364–378, 2002.
V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon and Algebraic-Geometric codes. IEEE Transactions on Information Theory, 45:1757–1767, 1999.
A. Kiayias and M. Yung. Cryptographic hardness based on the decoding of Reed-Solomon codes with applications. Technical report, Electronic Colloquium on Computational Complexity, http://eccc.uni-trier.de/eccc/, 2002.
A. Kiayias and M. Yung. Cryptographic hardness based on the decoding of Reed-Solomon codes with applications. In Springer-Verlag, editor, ICALP 2002, number 2380 in LNCS, pages 232–243, 2002.
F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes. North-Holland, 1977.
R. J. McEliece. A public-key cryptosystem based on algebraic coding theory. Technical report, Jet Prop. Lab., 1978.
M. Naor and B. Pinkas. Oblivious transfer and polynomnial evaluation. In ACM, editor, STOC 99, pages 245–254, 1999.
J. Patarin. Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of symmetric algorithms. In Advances in Cryptology, Eurocrypt’96, volume 1070 of Lecture Notes in Computer Science, pages 33–48, 1996.
I. S. Reed and G. Solomon. Polynomial codes over certain finite fields. J. SIAM, 8:300–304, 1960.
L. R. Welch and E. R. Berlekamp. Error correction for algebraic block codes. US Patent 4 633 470, 1986.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 International Association for Cryptologic Research
About this paper
Cite this paper
Augot, D., Finiasz, M. (2003). A Public Key Encryption Scheme Based on the Polynomial Reconstruction Problem. In: Biham, E. (eds) Advances in Cryptology — EUROCRYPT 2003. EUROCRYPT 2003. Lecture Notes in Computer Science, vol 2656. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-39200-9_14
Download citation
DOI: https://doi.org/10.1007/3-540-39200-9_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-14039-9
Online ISBN: 978-3-540-39200-2
eBook Packages: Springer Book Archive