Abstract
Three new trapdoor one-way functions are proposed that are based on elliptic curves over the ring Zn. The first class of functions is a naive construction, which can be used only in a digital signature scheme, and not in a public-key cryptosystem. The second, preferred class of function, does not suffer from this problem and can be used for the same applications as the RSA trapdoor one-way function, including zero-knowledge identification protocols. The third class of functions has similar properties to the Rabin trapdoor one-way functions. Although the security of these proposed schemes is based on the difficulty of factoring n, like the RSA and Rabin schemes, these schemes seem to be more secure than those schemes from the viewpoint of attacks without factoring such as low multiplier attacks. The new schemes are somewhat less efficient than the RSA and Rabin schemes.
Supported by Omnisec AG, Switzerland
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
L. Adleman, K. Manders, and G. Miller, “On taking roots in finite fields”, 20th FOCS, Vol. 20, 1977, pp.175–178 (1977).
D. Chaum, “Blind signatures for untraceable payments”, Proc. of Crypto’82, pp.199–203 (1982).
W. Diffie and M.E. Hellman, “New directions in cryptography, IEEE Transactions on Information Theory,” Vol. 22, No. 6, pp. 644–654 (1976).
T. El-Gamal, “A public key cryptosystem and a signature scheme based on the discrete logarithm”, IEEE Transactions on Information Theory, Vol. 31, No. 4, pp. 469–472 (1985).
S. Goldwasser and J. Kilian, “Almost all primes can be quickly certified”, Proc. of the 18th Annual ACM Symposium on the Theory of Computing, pp. 316–329 (1986).
J. Hastad, “On using RSA with low exponent in a public key network”, Proc. of Crypto’85, pp.403–408 (1985).
W. Jonge and D. Chaum, “ Attacks on some RSA signatures”, Proc. of Crypto’85, pp.18–27 (1985).
B.S. Kaliski, “A pseudo-random bit generator based on elliptic logarithms”, Proc. of Crypto’86, pp. 84–103 (1987).
N. Koblitz, A Course in Number Theory and Cryptography, Berlin: Springer-Verlag, (1987).
K. Koyama, “A Master Key for the RSA public-key cryptosystem”, I.E.C.E. Trans.(D), J-65,2, pp.163–170 (1982).
E. Kranakis, Primality and Cryptography, Stuttgart: Teubner, and New York: John Wiley & Sons, (1986).
A.K. Lenstra, H.W. Lenstra, M.S. Manasse and J.M. Pollard, “The number field sieve”, Proc. of STOC’90, pp.564–572 (1990).
A.K. Lenstra and M.S. Manasse, “Factoring with two large primes”, Proc. of EUROCRYPT’90, pp.72–82 (1991)
H.W. Lenstra, “Factoring integers with elliptic curves”, Annals of Mathematics, Vol. 126, pp. 649–673 (1987).
U.M. Maurer, “Fast generation of RSA-moduli with almost maximal diversity”, Proc. of EUROCRYPT’89, pp. 636–647 (1990).
U.M. Maurer and Y. Yacobi, “Non-interactive public-key cryptography”, to appear in Proc. Eurocrypt’ 91.
J.L. Massey, “Cryptography — fundamentals and applications (Copies of transparencies)”, Advanced Technology Seminars, Zurich, Switzerland, (1988).
G.L. Miller, “Riemann’s hypothesis and tests for primality”, J. Comput. System Sci. Vol.13, pp.300–317, (1976).
A.J. Menezes, T. Okamoto, S.A. Vanstone, “Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field”, Proc. of STOC’91, pp.80–89 (1991).
M.O. Rabin, “Probabilistic algorithm for testing primality”, Journal on Number Theory, Vol. 12, pp. 128–138 (1980).
R.L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems”, Communications of the ACM, Vol. 21, No. 2, pp. 120–126 (1978).
R. Schoof, “Elliptic curves over finite fields and the computation of square roots mod p”, Mathematics of Computation, Vol. 44, No. 170, pp. 483–494 (1985).
J.H. Silverman, The Arithmetic of Elliptic Curves, Springer-Verlag, (1986).
G. Simmons and M. Norris, “Preliminary comments on the M.I.T. public key cryptosystem”, Cryptologia, Vol. 1, No. 4, pp. 406–414 (1977).
J. Stein, “Computational problems associated with Racah algebra”, J. Comp. Phys., Vol. 1, pp. 397–405 (1961).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Koyama, K., Maurer, U.M., Okamoto, T., Vanstone, S.A. (1992). New Public-Key Schemes Based on Elliptic Curves over the Ring Zn . In: Feigenbaum, J. (eds) Advances in Cryptology — CRYPTO ’91. CRYPTO 1991. Lecture Notes in Computer Science, vol 576. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46766-1_20
Download citation
DOI: https://doi.org/10.1007/3-540-46766-1_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55188-1
Online ISBN: 978-3-540-46766-3
eBook Packages: Springer Book Archive