Abstract
In this paper, we propose a new public key cryptosystem based on a probably subexponential time problem over a modular matrix ring. Our new cryptosystem is similar to GGH(O. Goldreich, S. Goldwasser, and S. Halevi) cryptosystem but the attack which breaks the GGH system is not applicable to ours. The security of the new construction is based on the computational difficulty of integer factorizations.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ajtai, M., Dwork, C.: A Public-key Cryptosystem with Worst-case/Average-case Equivalence. In: Proc. of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 284–293 (1997)
Goldreich, O., Goldwasser, S., Halevi, S.: Public-key Cryptosystems from Lattice Reduction Problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112–131. Springer, Heidelberg (1997)
Nguyen, P.: Cryptanalysis for the Goldreich-Goldwasser-Halevi Cryptosystem form Crypto 1997. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 288–304. Springer, Heidelberg (1999)
van Emde Boas, P.: Another NP-complete Problem and the Complexity of Computing Short Vectors in a Lattice. Technical Report 81-04, Mathematische Instituut, University of Amsterdam (1981)
Dinur, I., Kindler, G., Safra, S.: Approximating-CVP to within Almost-Polynomial Factors is NP-hard, Electronic Colloquium on Computational Complexity, Report No. 48 (1998)
Micciancio, D.: On the hardness of the Shortest Vector Problem, Ph. D. Dissertation, Massachusetts Institute of Technology (September 1998)
Schnorr, C.P.: A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithm. Theoretical Computer Science 53, 201–224 (1987)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yoo, H., Hong, S., Lee, S., Lim, J., Yi, O., Sung, M. (2000). A Proposal of a New Public Key Cryptosystem Using Matrices over a Ring. In: Dawson, E.P., Clark, A., Boyd, C. (eds) Information Security and Privacy. ACISP 2000. Lecture Notes in Computer Science, vol 1841. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10718964_4
Download citation
DOI: https://doi.org/10.1007/10718964_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67742-0
Online ISBN: 978-3-540-45030-6
eBook Packages: Springer Book Archive