skip to main content
10.1145/1533057.1533070acmconferencesArticle/Chapter ViewAbstractPublication Pagesasia-ccsConference Proceedingsconference-collections
research-article

A generic construction of useful client puzzles

Published: 10 March 2009 Publication History

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]
M. Bellare and C. Namprempre. Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm. In ASIACRYPT'00, volume 1976 of Lecture Notes in Computer Science, pages 531--545. Springer, 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, and N. Smart. Generic Constructions of Identity-Based and Certificateless KEMs. Journal of Cryptology, 21(2):178--199, 2008.
[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]
D. Boneh and M. Franklin. Identity-Based Encryption from the Weil Pairing. In CRYPTO'01, volume 2139 of LNCS, pages 213--229. Springer, 2001.
[6]
D. Boneh, C. Gentry, and M. Hamburg. Space-Efficient Identity Based EncryptionWithout Pairings. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 647--657. IEEE, 2007.
[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]
C. Cocks. An Identity Based Encryption Scheme Based on Quadratic Residues. In the 8th IMA international conference on cryptography and coding, volume 2260 of LNCS, pages 360--363. Springer, 2001.
[9]
D. Dean and A. Stubblefield. Using Client Puzzles to Protect TLS. In 10th USENIX UNIX Security Symposium, 2001.
[10]
T. Diament, H. K. Lee, A. Keromytis, and M. Yung. The Dual Receiver Cryptosystem and Its Applications. In ACM CCS'04, pages 330--343. ACM Press, 2004.
[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]
M. Jakobsson and A. Juels. Proofs of Work and Bread Pudding Protocols. In the IFIP TC6 and TC11 Joint Working Conference on Communications and Multimedia Security, 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]
J. Leiwo, P. Nikander, and T. Aura. Towards Network Denial of Service Reistant Protocols. In 15th International Information Security Conference (IFIP/SEC), 2000.
[18]
M. Naor and M. Yung. Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. In STOC'90, pages 427--437. ACM, 1990.
[19]
C. Rackoff and D. Simon. Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack. In CRYPTO'91, volume 576 of LNCS, pages 433--444. Springer, 1991.
[20]
R. Rivest, A. Shamir, and D. Wagner. Time-lock Puzzles and Time-release Crypto. Technical Report MIT/LCS/TR-684, MIT, 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]
A. Shamir. Identity-Based Cryptosystems and Signature Schemes. In CRYPTO'84, volume 196 of LNCS, pages 47--53. Springer, 1984.
[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]
A. D. Wood and J. A. Stankovic. Denial of Service in Sensor Networks. IEEE Computer, 35(10):54--62, 2002.

Cited By

View all

Index Terms

  1. A generic construction of useful client puzzles

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ASIACCS '09: Proceedings of the 4th International Symposium on Information, Computer, and Communications Security
    March 2009
    408 pages
    ISBN:9781605583945
    DOI:10.1145/1533057
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 10 March 2009

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. identity based KEM
    2. security notions
    3. useful client puzzle

    Qualifiers

    • Research-article

    Conference

    Asia CCS 09
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 418 of 2,322 submissions, 18%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 17 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)A Regulatable Mechanism for Transacting Data AssetsIEEE Internet of Things Journal10.1109/JIOT.2023.330603010:24(21615-21632)Online publication date: 15-Dec-2023
    • (2022)An Efficient Public-Key Dual-Receiver Encryption SchemeIEEE Access10.1109/ACCESS.2022.314472510(10799-10805)Online publication date: 2022
    • (2014)Practical Dual-Receiver EncryptionTopics in Cryptology – CT-RSA 201410.1007/978-3-319-04852-9_5(85-105)Online publication date: 2014
    • (2010)Game theoretic resistance to denial of service attacks using hidden difficulty puzzlesProceedings of the 6th international conference on Information Security Practice and Experience10.1007/978-3-642-12827-1_26(359-376)Online publication date: 12-May-2010

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media