Advertisement

An Efficient Two-Party Public Key Cryptosystem Secure against Adaptive Chosen Ciphertext Attack

  • Philip Mac Kenzie
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)

Abstract

We propose an efficient two-party public key cryptosystem that is secure against adaptive chosen ciphertext attack, based on the hardness of Decision Diffie-Hellman (DDH). Specifically, we show that the two parties together can decrypt ciphertexts, but neither can alone. Our system is based on the Cramer-Shoupcryp tosystem. Previous results on efficient threshold cryptosystems secure against adaptive chosen ciphertext attack required either (1) a strict majority of uncorrupted decryption servers, and thus do not apply to the two-party scenario, or (2) the random oracle assumption, and thus were not proven secure in the “standard” model.

Keywords

Encryption Scheme Random Oracle Test Oracle Decryption Oracle Threshold Cryptography 
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

  1. [1]
    M. Abe. Robust distributed multiplication without interaction. In CRYPTO’ 99 (LNCS 1666), pages 130–147, 1999. 48Google Scholar
  2. [2]
    N. Asokan, M. Schunter, and M. Waidner. Optimistic protocols for fair exchange. In 3rd ACM Conference on Computer and Communications Security, pages 6–17, 1996. 47Google Scholar
  3. [3]
    D. Boneh. The decision Diffie-Hellman problem. In Proceedings of the Third Algorithmic Number Theory Symposium (LNCS1423), pp. 48–63, 1998. 57CrossRefGoogle Scholar
  4. [4]
    D. Boneh and M. Franklin. Efficient generation of shared RSA keys. In CRYPTO’ 97 (LNCS 1294), pages 425–439, 1997. 49Google Scholar
  5. [5]
    N. Barić and B. Pfitzmann. Collision-free accumulators and fail-stopsign ature schemes without trees. In EUROCRYPT’ 97 (LNCS 1233), pages 480–494, 1997. 48Google Scholar
  6. [6]
    M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway. Relations among notions of security for public-key encryption schemes. In CRYPTO’ 98 (LNCS 1462), pp. 26–45, 1998. 57Google Scholar
  7. [7]
    C. Boyd. Digital multisignatures. In H.J. Beker and F.C. Piper, editors, Cryptography and Coding, pages 241–246. Clarendon Press, 1986. 48Google Scholar
  8. [8]
    M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In 1st ACM Conference on Computer and Communications Security, pages 62–73, November 1993. 49Google Scholar
  9. [9]
    J. Camenisch and M. Stadler. Proof systems for general statements about discrete logarithms. Technical Report TR 260, Department of Computer Science, ETH Zurich, March 1997. 56Google Scholar
  10. [10]
    R. Canetti and S. Goldwasser. An efficient threshold public key cryptosystem secure against adaptive chosen ciphertext attack. In EUROCRYPT’ 99 (LNCS 1592), pages 90–106, 1999. 48, 50, 56Google Scholar
  11. [11]
    R. Canetti, O. Goldreich, and S. Halevi. Random oracle methodology, revisited. In 30th ACM Symposium on Theory of Computing, pages 209–218, 1998. 49Google Scholar
  12. [12]
    M. Cerecedo, T. Matsumoto, H. Imai. Efficient and secure multiparty generation of digital signatures based on discrete logarithms. IEICE Trans. Fundamentals of Electronics Communications and Computer Sciences, E76A(4):532–545, April 1993. 48, 49Google Scholar
  13. [13]
    R. Cramer. Modular Design of Secure yet Practical Cryptographic Protocols. Ph.D. Thesis. CWI and University of Amsterdam, 1997. 51Google Scholar
  14. [14]
    R. Cramer, I. Damg∢rd, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In CRYPTO’ 94 (LNCS 839), pages 174–187, 1994. 51, 52Google Scholar
  15. [15]
    R. Cramer and V. Shoup. A practical public-key cryptosystem provably secure against adaptive chosen ciphertext attack. In CRYPTO’ 98 (LNCS 1462), pages 13–25, 1998. 47, 50Google Scholar
  16. [16]
    R. Cramer and V. Shoup. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In EUROCRYPT 2002 (LNCS 2332), pages 45–64, 2002. 50CrossRefGoogle Scholar
  17. [17]
    R.A. Croft and S.P. Harris. Public-key cryptography and reusable shared secrets. In H. Baker and F. Piper, editors, Cryptography and Coding, pages 189–201, 1989. 48Google Scholar
  18. [18]
    I. Damg∢rd. Efficient concurrent zero-knowledge in the auxiliary string model. In EUROCRYPT 2000 (LNCS 1807), pages 418–430, 2000. 56CrossRefGoogle Scholar
  19. [19]
    Y. Desmedt. Society and group oriented cryptography: a new concept. In CRYPTO’ 87 (LNCS 293), pages 120–127, 1987. 48Google Scholar
  20. [20]
    Y. Desmedt and Y. Frankel. Threshold cryptosystems. In CRYPTO’ 89 (LNCS 435), pages 307–315, 1989. 48Google Scholar
  21. [21]
    T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31:469–472, 1985. 53CrossRefzbMATHGoogle Scholar
  22. [22]
    U. Feige and A. Shamir. Witness indistinguishable and witness hiding protocols. In 22nd ACM Symposium on Theory of Computing, pp. 416–426, 1990. 52Google Scholar
  23. [23]
    P. Fouque and D. Pointcheval. Threshold Cryptosystems secure against Chosen-Ciphertext Attack. In ASIACRYPT’ 01 (LNCS 2248), pages 351–368, 2001. 48Google Scholar
  24. [24]
    Y. Frankel. A practical protocol for large group oriented networks. In EUROCRYPT’ 89(LNCS 434), pages 56–61, 1989. 48Google Scholar
  25. [25]
    Y. Frankel, P. Mac Kenzie, and M. Yung. Robust efficient distributed RSA-key generation. In 30th ACM Symposium on Theory of Computing, pages 663–672, 1998. 49Google Scholar
  26. [26]
    Y. Frankel, P. Mac Kenzie, and M. Yung. Adaptively-secure distributed threshold public key systems. In European Symposium on Algorithms (LNCS 1643), pages 4–27, 1999. 48Google Scholar
  27. [27]
    A. Fiat and A. Shamir. How to prove yourself: practical solutions to identification and signature problems. In CRYPTO’ 86 (LNCS 263), pages 186–194, 1987. 56Google Scholar
  28. [28]
    N. Gilboa. Two party RSA key generation. In CRYPTO’ 99 (LNCS 1666), pages 116–129, 1999. 49Google Scholar
  29. [29]
    R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust threshold DSS signatures. In EUROCRYPT’ 96 (LNCS 1070), pages 354–371, 1996. 48, 49Google Scholar
  30. [30]
    L. Harn. Grouporien ted (t, n) threshold digital signature scheme and digital multisignature. IEE Proc.-Comput. Digit. Tech. 141(5):307–313, 1994. 48zbMATHGoogle Scholar
  31. [31]
    A. Herzberg, M. Jakobsson, S. Jarecki, H. Krawczyk, and M. Yung. Proactive public-key and signature schemes. In 4th ACM Conference on Computer and Communications Security, pages 100–110, 1997. 48Google Scholar
  32. [32]
    T. Hwang. Cryptosystem for group oriented cryptography. In EUROCRYPT’ 90 (LNCS 473), pages 352–360, 1990. 48Google Scholar
  33. [33]
    S. Jarecki and A. Lysyanskaya. Adaptively secure threshold cryptography: Introducing concurrency, removing erasures. In EUROCRYPT 2000 (LNCS 1807), pages 221–242, 2000. 48, 56CrossRefGoogle Scholar
  34. [34]
    S. Langford. Threshold DSS signatures without a trusted party. In CRYPTO’ 95 (LNCS 963), pages 397–409, 1995. 48, 49Google Scholar
  35. [35]
    P. Mac Kenzie and M.K. Reiter. Networked cryptographic devices resilient to capture. DIMACS Technical Report 2001-19, May 2001. Extended abstract in 2001 IEEE Symposium on Security and Privacy, May 2001. 47, 48, 51, 52Google Scholar
  36. [36]
    P. Mac Kenzie and M.K. Reiter. Two-party generation of DSA signatures. In CRYPTO 2001 (LNCS 2139), pages 137–154, 2001. 48, 49, 56CrossRefGoogle Scholar
  37. [37]
    S. Micali. Fair public-key cryptosystems. In CRYPTO’ 92 (LNCS 740), pages 113–138, 1992. 47Google Scholar
  38. [38]
    P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT’ 99 (LNCS 1592), pages 223–238, 1999. 48Google Scholar
  39. [39]
    C. Park and K. Kurosawa. New ElGamal type threshold digital signature scheme. IEICE Trans. Fundamentals of Electronics Communications and Computer Sciences, E79A(1):86–93, January, 1996. 48Google Scholar
  40. [40]
    T. Pedersen. A threshold cryptosystem without a trusted party. In EUROCRYPT’ 91(LNCS 547), pages 522–526, 1991. 48Google Scholar
  41. [41]
    G. Poupard and J. Stern. Generation of shared RSA keys by two parties. In ASIACRYPT’ 98, LNCS 1514, pages 11–24, 1998. 49Google Scholar
  42. [42]
    V. Shoup and R. Gennaro. Securing threshold cryptosystems against chosen ciphertext attack. In EUROCRYPT’ 98, pp. 1–16, 1998. 48, 51, 57Google Scholar
  43. [43]
    A. Yao. Protocols for secure computation. In 23rd IEEE Symposium on Foundations of Computer Science, pages 160–164, 1982. 47Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Philip Mac Kenzie
    • 1
  1. 1.Bell LaboratoriesLucent TechnologiesMurray HillUSA

Personalised recommendations