Abstract
This paper proposes a novel public-key cryptosystem, which is practical, provably secure and has some other interesting properties as follows:
-
1.
Its trapdoor technique is essentially different from any other previous schemes including RSA-Rabin and Diffie-Hellman.
-
2.
It is a probabilistic encryption scheme.
-
3.
It can be proven to be as secure as the intractability of factoring n = p2q (in the sense of the security of the whole plaintext) against passive adversaries.
-
4.
It is semantically secure under the p-subgroup assumption, which is comparable to the quadratic residue and higher degree residue assumptions.
-
5.
Under the most practical environment, the encryption and decryption speeds of our scheme are comparable to (around twice slower than) those of elliptic curve cryptosystems.
-
6.
It has a homomorphic property: E(m0, r0)E(m1, r1) mod n = E(@#@ m0 + m1, r2), where E(m, r) means a ciphertext of plaintext m as randomized by r and m0+ m1 < p.
-
7.
Anyone can change a ciphertext, C = E(m, r), into another ciphertext, C′ = Chr' mod n, while preserving plaintext of C (i.e., C′ = E(m,r″)), and the relationship between C and C′ can be concealed.
Chapter PDF
Similar content being viewed by others
References
Adleman, L.M. and McCurley, K.S.: Open Problems in Number Theoretic Complexity,II (open problems: C7, O7a and O7b), Proc. of ANTS-I, LNCS 877, Springer-Verlag, pp.291–322 (1995).
Ajtai, M. and Dwork, C.: A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence, Proc. of STOC'97, pp. 284–293 (1997).
Alexi, W., Chor, B.Z., Goldreich, O. and Schnorr, C.P.: RSA and Rabin Functions: Certain Parts Are as Hard as the Whole, SIAM Journal of Computing, 17, 2, pp.449–457(1988).
Bellare, M. and Rogaway, P.: Optimal Asymmetric Encryption, Proc. of Eurocrypt'94, LNCS 950, Springer-Verlag pp.92–111 (1995).
Blum, M. and Goldwasser, S.: An efficient probabilistic public-key encryption scheme which hides all partial information, Proc. of Crypto'84, LNCS 196, Springer-Verlag, pp.289–299 (1985).
Chao, J., Matsuda, N. and Tsujii, S.: Efficient construction of secure hyperelliptic discrete logarithm problems, Proc. of ICICS'97, LNCS 1334, Springer-Verlag, pp.292–301 (1997).
Chor, B. and Rivest, R.L.: A knapsack type public key cryptosystem based on arithmetic in finite fields, Proc. of Crypto'84, LNCS 196, Springer-Verlag, pp.54–65 (1985).
Cohen, J. and Fischer.: A Robust and Verifiable Cryptographically Secure Election Scheme, FOCS, pp.372–382 (1985).
Dolev, D., Dwork, C. and Naor, M.: Non-Malleable Cryptography, Proc. of STOC, pp.542–552 (1991).
Demytko, N.: A New Elliptic Curve Based Analogue of RSA, Proc. of Eurocrypt'93, LNCS 765, Springer-Verlag, pp.40–49 (1994).
Diffie, W. and Hellman, M.: New Directions in Cryptography, IEEE Trans. on Information Theory, IT-22, 6, pp.644–654 (1976).
ElGamal, T.: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. on Information Theory, IT-31, 4, pp.469–472 (1985).
Goldwasser, S. and Bellare, M: Lecture Notes on Cryptography, http://wwwcse.ucsd.edu/users/mihir/ (1997).
Goldwasser, S. and Micali, S.: Probabilistic Encryption, JCSS, 28, 2, pp.270–299 (1984).
Hastad, J., Schrift, A.W. and Shamir, A.: The Discrete Logarithm Modulo a Composite Hides O(n) Bits, J. of Computer and System Sciences, 47, pp.376–404 (1993).
Knuth, D.E.: The Art of Computer Programming, Addison-Wesley Publishing Co.,(1981).
Koblitz, N.: Elliptic Curve Cryptosystems, Math. Comp., 48, 177, pp.203–209 (1987).
Koyama, K., Maurer, U. M., Okamoto, T. and Vanstone, S. A.,: New Public-key Schemes based on Elliptic Curves over the Ring Zn, Proc. of Crypto'91, LNCS 576, Springer-Verlag, pp.252–266 (1992).
Kurosawa, K., Ito, T. and Takeuchi, M.: Public Key Cryptosystem using a Reciprocal Number with the same Intractability as Factoring a Large Number, Cryptologia, 12, 4, pp.225–233 (1988).
Loxton, J.H., Khoo, D.S.P., Bird, G.J. and Seberry, J.: A Cubic RSA Code Equivalent to Factorization, Journal of Cryptology, 5, 2, pp.139–150 (1992).
Matsumoto, T. and Imai, H.: Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption, Proc. of Eurocrypt'88, LNCS 330, Springer-Verlag, pp.419–453 (1988).
McEliece, R.J.: A Public-Key Cryptosystem Based on Algebraic Coding Theory, DSN progress report 42-44, Jet Propulsion Laboratories, Pasadena (1978).
Merkle, R.C. and Hellman, M.E.: Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. on Inform. Theory, 24, pp.525–530 (1978).
Micali, S., Rackoff, C. and Sloan, B.: The notion of security for probabilistic cryptosystems, SIAM Journal on Computing, 17, 2, pp.412–426 (1988).
Miller, V.S.: Use of Elliptic Curves in Cryptography, Proc. of Crypto'85, LNCS 218, Springer-Verlag, pp.417–426 (1985).
Naccache, D. and Stern, J.: A New Public-Key Cryptosystem, Proc. of Eurocrypt'97, LNCS 1233, Springer-Verlag, pp.27–436 (1997).
Okamoto, T. and Uchiyama, S.: Individual Bit Security of a New Public-Key Cryptosystem, Manuscript (1998).
Patarin, J. and Goubin, L.: Trapdoor one-way permutations and multivariate polynomials, Proc. of ICICS'97, LNCS 1334, Springer-Verlag, pp.356–368 (1997).
Patarin, J. and Goubin, L.: Asymmetric cryptography with S-Boxes, Proc. of ICICS'97, LNCS 1334, Springer-Verlag, pp.369–380 (1997).
Peralta, R.: Bleichenbacher's improvement for factoring numbers of the form N = PQ2 (private communication) (1997).
Peralta, R. and Okamoto, E.: Faster Factoring of Integers of a Special Form, IEICE Trans. Fundamentals, E79-A, 4, pp.489–493 (1996).
Pointcheval, D. and Stern, J.: Security Proofs for Signature Schemes, Proc. of Eurocrypt'96, LNCS 1070, Springer-Verlag, pp.387–398 (1996).
Pollard, J.L.: Manuscript (1997).
Rabin, M.O.: Digital Signatures and Public-Key Encryptions as Intractable as Factorization, MIT, Technical Report, MIT/LCS/TR-212 (1979).
Rivest, R., Shamir, A. and Adleman, L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, Vol.21, No.2, pp.120–126 (1978).
Smith, P. and Lennon, M.: LUC: A New Public Key System, Proc. of IFIP/SEC'93, pp. 103–117, North-Holland (1993).
Tsiounis, Y. and Yung, M.: On the Security of ElGamal-based encryption, to appear in Proc. of PKC'98, LNCS, Springer-Verlag.
Williams, H.C.: A Modification of the RSA Public Key Encryption Procedure, IEEE Trans. on Inform. Theory, IT-26, 6, pp.726–729 (1980).
Williams, H.C.: Some Public-Key Crypto-Functions as Intractable as Factorization, Proc. of Crypto'84, LNCS 196, Springer-Verlag, pp.66–70 (1985).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Okamoto, T., Uchiyama, S. (1998). A new public-key cryptosystem as secure as factoring. In: Nyberg, K. (eds) Advances in Cryptology — EUROCRYPT'98. EUROCRYPT 1998. Lecture Notes in Computer Science, vol 1403. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054135
Download citation
DOI: https://doi.org/10.1007/BFb0054135
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64518-4
Online ISBN: 978-3-540-69795-4
eBook Packages: Springer Book Archive
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.