The dual receiver cryptosystem and its applications

ABSTRACT

We put forth the notion of a dual receiver cryptosystem and implement it based on bilinear pairings over certain elliptic curve groups. The cryptosystem is simple and efficient yet powerful, as it solves two problems of practical importance whose solutions have proven to be elusive before:(1) A provably secure "combined" public-key cryptosystem (with a single secret key per user in space-limited environment) where the key is used for both decryption and signing and where encryption can be escrowed and recovered, while the signature capability never leaves its owner. This is an open problem proposed by the work of Haber and Pinkas. (2) A puzzle is a method for rate-limiting remote users by forcing them to solve a computational task (the puzzle). Puzzles have been based on cryptographic challenges in the past, but the successful design of embedding a useful cryptographic task inside a puzzle, originally posed by Dwork and Naor, remained an open problem till today. We model and present "useful security puzzles" applicable in two scenarios: a secure fileserver, and an online transaction server (such as a webserver).

REFERENCES

• 1: M. Abadi, M. Burrow, M. Manasse, and T. Wobber. Moderately Hard, Memory-bound Functions. In Proceedings of the ISOC Symposium on Network and Distributed Systems Security (SNDSS), February 2003.
• 2: William Aiello , Steven M. Bellovin , Matt Blaze , John Ioannidis , Omer Reingold , Ran Canetti , Angelos D. Keromytis, Efficient, DoS-resistant, secure key exchange for internet protocols, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586118]
• 3: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 4: Tuomas Aura , Pekka Nikander, Stateless connections, Proceedings of the First International Conference on Information and Communication Security, p.87-97, November 11-14, 1997
• 5: A. Back. Hashcash - A Denial of Service Counter-Measure. http://www.cypherspace.org/hashcash/hashcash.pdf, August 2002.
• 6: Dan Boneh , Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.213-229, August 19-23, 2001
• 7: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 8: Dan Boneh , Moni Naor, Timed Commitments, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.236-254, August 20-24, 2000
• 9: D. Dean and A. Stubblefield. Using Client Puzzles to Protect TLS. In Proceedings of the 10th USENIX UNIX Security Symposium, August 2001.
• 10: W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Trans. on Information Theory, IT-22(6):644--654, Nov. 1976.
• 11: Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
• 12: Pierre-Alain Fouque , David Pointcheval, Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.351-368, December 09-13, 2001
• 13: Yair Frankel , Moti Yung, Escrow Encryption Systems Visited: Attacks, Analysis and Designs, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.222-235, August 27-31, 1995
• 14: G. Frey, M. Müller, and H.-G. R. uck. The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems. IEEE Transactions on Information Theory, 45(5):1717--1719, 1999.
• 15: Steven D. Galbraith , Keith Harrison , David Soldera, Implementing the Tate Pairing, Proceedings of the 5th International Symposium on Algorithmic Number Theory, p.324-337, July 07-12, 2002
• 16: J. A. Garay and M. Jakobsson. Timed Release of Standard Digital Signatures. In Proceedings of the 6th Conference on Financial Cryptography, pages 168--182, February 2002.
• 17: Craig Gentry , Alice Silverberg, Hierarchical ID-Based Cryptography, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.548-566, December 01-05, 2002
• 18: V. D. Gligor. Guaranteeing Access in Spite of Distributed Service-Flooding Attacks. In Proceedings of the Security Protocols Workshop, April 2003.
• 19: S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270--299, Apr. 1984.
• 20: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 21: Stuart Haber , Benny Pinkas, Securely combining public-key cryptosystems, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502013]
• 22: D. Harkins and D. Carrel. The Internet Key Exchange (IKE). Request for Comments (Proposed Standard) 2409, Internet Engineering Task Force, Nov. 1998.
• 23: L. Heberlein and M. Bishop. Attack Class: Address Spoofing. In Proceedings of the 19th National Information Systems Security Conference, pages 371--377, October 1996.
• 24: Shouichi Hirose , Kanta Matsuura, Enhancing the Resistence of a Provably Secure Key Agreement Protocol to a Denial-of-Service Attack, Proceedings of the Second International Conference on Information and Communication Security, p.169-182, November 09-11, 1999
• 25: K. Houle, G. Weaver, N. Long, and R. Thomas. Trends in Denial of Service Attack Technology. http://www.cert.org/archive/pdf/DoS_trends.pdf, October 2001.
• 26: Markus Jakobsson , Ari Juels, Proofs of Work and Bread Pudding Protocols, Proceedings of the IFIP TC6/TC11 Joint Working Conference on Secure Information Networks: Communications and Multimedia Security, p.258-272, September 20-21, 1999
• 27: P. Janson , G. Tsudik , M. Yung, Scalability and Flexibility in Authentication Services: The KryptoKnight Approach, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.725, April 09-11, 1997
• 28: Antoine Joux, A One Round Protocol for Tripartite Diffie-Hellman, Proceedings of the 4th International Symposium on Algorithmic Number Theory, p.385-394, July 02-07, 2000
• 29: Antoine Joux, The Weil and Tate Pairings as Building Blocks for Public Key Cryptosystems, Proceedings of the 5th International Symposium on Algorithmic Number Theory, p.20-32, July 07-12, 2002
• 30: A. Joux and K. Nguyen. Separating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups. Manuscript. Available from eprint.iacr.org, 2001.
• 31: A. Juels and J. Brainard. Client puzzles: A cryptographic countermeasure against connection depletion attacks. In Proceedings of the ISOC Symposium on Network and Distributed Systems Security (SNDSS), pages 151--165, February 1999.
• 32: P. Karn and W. Simpson. Photuris: Session-key management protocol. Request for Comments (Experimental) 2522, Internet Engineering Task Force, Mar. 1999.
• 33: C. Kaufman, R. Perlman, and M. Speciner. Network Security, 2nd Edition. Prentice Hall, 2002.
• 34: Angelos D. Keromytis , Vishal Misra , Dan Rubenstein, SOS: secure overlay services, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 35: Jussipekka Leiwo , Tuomas Aura , Pekka Nikander, Towards Network Denial of Service Resistant Protocols, Proceedings of the IFIP TC11 Fifteenth Annual Working Conference on Information Security for Global Information Infrastructures, p.301-310, August 22-24, 2000
• 36: Jonathan Lemon, Resisting SYN Flood DoS Attacks with a SYN Cache, Proceedings of the BSDCon 2002, p.89-97, February 11-14, 2002
• 37: M. Naor , M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.427-437, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100273]
• 38: Tatsuaki Okamoto , David Pointcheval, REACT: Rapid Enhanced-Security Asymmetric Cryptosystem Transform, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.159-175, April 08-12, 2001
• 39: Rolf Oppliger, Protecting Key Exchange and Management Protocols Against Resource Clogging Attacks, Proceedings of the IFIP TC6/TC11 Joint Working Conference on Secure Information Networks: Communications and Multimedia Security, p.163-175, September 20-21, 1999
• 40: B. Pinkas. Personal communication.
• 41: Charles Rackoff , Daniel R. Simon, Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.433-444, August 11-15, 1991
• 42: R. Rivest and A. Shamir. PayWord and MicroMint. CryptoBytes, 2(1):7--11, 1996.
• 43: R. L. Rivest , A. Shamir , D. A. Wagner, Time-lock Puzzles and Timed-release Crypto, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 44: Karl Rubin , Alice Silverberg, Supersingular Abelian Varieties in Cryptology, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.336-353, August 18-22, 2002
• 45: Christoph L. Schuba , Ivan V. Krsul , Markus G. Kuhn , Eugene H. spafford , Aurobindo Sundaram , Diego Zamboni, Analysis of a Denial of Service Attack on TCP, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.208, May 04-07, 1997
• 46: Eric R. Verheul, Evidence that XTR Is More Secure than Supersingular Elliptic Curve Cryptosystems, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.195-210, May 06-10, 2001
• 47: XiaoFeng Wang , Michael K. Reiter, Defending Against Denial-of-Service Attacks with Puzzle Auctions, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.78, May 11-14, 2003
• 48: Anthony D. Wood , John A. Stankovic, Denial of Service in Sensor Networks, Computer, v.35 n.10, p.54-62, October 2002 [doi>10.1109/MC.2002.1039518]
• 49: A. Yaar, A. Perrig, and D. Song. SIFF: A Stateless Internet Flow Filter to Mitigate DDoS Flooding Attacks. In Proceedings of the IEEE Security and Privacy Symposium, May 2004.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Access controls

General Terms:
Design, Security, Theory

Keywords:
digital signature, elliptic curves, key escrow, pairing-based cryptography, public key, puzzles, useful secure computation