A generic construction of useful client puzzles

ABSTRACT

Denial of Service (DoS) attacks are serious threats for network societies. For dealing with DoS attacks, Jakobsson and Juels first proposed the notion of useful client puzzles (UCPs) which simultaneously decrease servers' burden and increase clients'. In ACM CCS'04, Diament, Lee, Keromytis, and Yung introduced the decryption-based UCPs. In this paper, we give a general framework for constructing such UCPs which is based on identity-based cryptography along with well-analyzed symmetric key authenticated encryption techniques (without random oracles). By using this framework, we can flexibly construct various UCPs according to different types of system requirements. We also give some instantiations: the first is a UCP based on the Boneh-Boyen Identity based encryption scheme, with provable security in the standard model. Another one is a UCP based on the Boneh-Gentry-Hamburg identity-based encryption scheme, which doesn't require pairings.

REFERENCES

• 1: Mihir Bellare , Chanathip Namprempre, Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.531-545, December 03-07, 2000
• 2: K. Bentahar, P. Farshim, J. Malone-Lee, and N. Smart. Generic Constructions of Identity-Based and Certificateless KEMs. Eprint Archive Report, Available at http://eprint.iacr.org/058, 2005.
• 3: K. Bentahar , P. Farshim , J. Malone-Lee , N. P. Smart, Generic Constructions of Identity-Based and Certificateless KEMs, Journal of Cryptology, v.21 n.2, p.178-199, February 2008 [doi>10.1007/s00145-007-9000-z]
• 4: D. Boneh and X. Boyen. Efficient Selective-ID Identity Based Encryption without Random Oracles. In EUROCRYPT'04, volume 3027 of LNCS, pages 223--238. Springer, 2004.
• 5: 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
• 6: Dan Boneh , Craig Gentry , Michael Hamburg, Space-Efficient Identity Based EncryptionWithout Pairings, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.647-657, October 21-23, 2007 [doi>10.1109/FOCS.2007.64]
• 7: R. Canetti, O. Goldreich, and S. Halevi. The Random Oracle Methodology, Revisited. In STOC'98, pages 557--594. ACM, 1998. Full availabe at http://eprint.iacr.org/1998/011.pdf.
• 8: Clifford Cocks, An Identity Based Encryption Scheme Based on Quadratic Residues, Proceedings of the 8th IMA International Conference on Cryptography and Coding, p.360-363, December 17-19, 2001
• 9: Drew Dean , Adam Stubblefield, Using client puzzles to protect TLS, Proceedings of the 10th conference on USENIX Security Symposium, p.1-1, August 13-17, 2001, Washington, D.C.
• 10: Theodore Diament , Homin K. Lee , Angelos D. Keromytis , Moti Yung, The dual receiver cryptosystem and its applications, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030128]
• 11: J. Garay and M. Jakobsson. Timed Release of Standard Digital Signatures. In Timed Release of Standard Digital Signatures, volume 2357 of Lecture Notes in Computer Science, pages 168--182. Springer, 2002.
• 12: O. Goldreich. Modern Cryptgraphy. Springer, 1999.
• 13: 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
• 14: A. Juels and J. Brainard. Client Puzzles: A Cryptographic Countermeature against Connectin Depletion Attacks. In SNDSS, pages 151--165, 1999.
• 15: E. Kiltz and Y. Vahlis. Cca2 secure ibe: Standard model efficiency through authenticated symmetric encryption. In CT-RSA'08, volume 4964 of LNCS, pages 221--238. springer, 2008.
• 16: H. K. Lee, T. Diament, A. D. Keromytis, and M. Yung. Useful Puzzles and the Dual Receiver Cryptosystem. 2007. Full version of {10}, manuscript available from the authors.
• 17: 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
• 18: 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]
• 19: 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
• 20: R. L. Rivest , A. Shamir , D. A. Wagner, Time-lock Puzzles and Timed-release Crypto, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 21: P. Rogaway and T. Shrimpton. Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Key-Wrap Problem. In Eurocrypt'06, volume 4004 of Lecture Notes in Computer Science, pages 373--390. Springer, 2006.
• 22: Adi Shamir, Identity-based cryptosystems and signature schemes, Proceedings of CRYPTO 84 on Advances in cryptology, p.47-53, August 1985, Santa Barbara, California, United States
• 23: V. Shoup. ISO 18033-2: An Emerging Standard for Public-Key Encryption (committee draft). Available at http://shoup.net/iso/, June 2001.
• 24: V. Shoup. Sequences of Games: a Tool for Taming Complexity in Security Proofs. Manuscript, 2004.
• 25: B. Waters. Efficient Identity-Based Encryption Without Random Oracles. In EUROCRYPT'05, volume 3494 of LNCS, pages 114--127. Springer, 2005.
• 26: 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

General Terms:
Security

Keywords:
identity based KEM, security notions, useful client puzzle