Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Pebbling and Proofs of Work

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 3621))

Included in the following conference series:

Abstract

We investigate methods for providing easy-to-check proofs of computational effort. Originally intended for discouraging spam, the concept has wide applicability as a method for controlling denial of service attacks. Dwork, Goldberg, and Naor proposed a specific memory-bound function for this purpose and proved an asymptotically tight amortized lower bound on the number of memory accesses any polynomial time bounded adversary must make. Their function requires a large random table which, crucially, cannot be compressed.

We answer an open question of Dwork et al. by designing a compact representation for the table. The paradox, compressing an incompressible table, is resolved by embedding a time/space tradeoff into the process for constructing the table from its representation.

Similar content being viewed by others

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.

References

  1. Abadi, M., Burrows, M., Manasse, M., Wobber, T.: Moderately hard, memory-bound functions. In: Proc. 10th NDSS (2003)

    Google Scholar 

  2. Ajtai, M.: Determinism versus non-determinism for linear time RAMs. In: Proc. 31st STOC, pp. 632–641 (1999)

    Google Scholar 

  3. Ajtai, M.: A non-linear time lower bound for boolean branching programs. In: Proc. 40th FOCS, pp. 60–70 (1999)

    Google Scholar 

  4. Alon, N., Capalbo, M.: Smaller explicit superconcentrators. Internet Mathematics 1(2), 151–163 (2003)

    Article MathSciNet  Google Scholar 

  5. Alon, N., Chung, F.: Explicit constructions of linear-sized tolerant networks. Discrete Math 72, 15–20 (1988)

    Article MATH MathSciNet  Google Scholar 

  6. Back, A.: Hashcash – a denial of servic counter-measure. Available at,http://www.cypherspace.org/hashcash/hashcash.pdf

  7. Beame, P., Saks, M.E., Sun, X., Vee, E.: Super-linear time-space tradeoff lower bounds for randomized computation. In: Proc. 41st FOCS, pp. 169–179 (2000)

    Google Scholar 

  8. Borodin, A., Cook, S.: A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput. 11(2), 287–297 (1982)

    Article MATH MathSciNet  Google Scholar 

  9. Cook, S.: An observation on time-storage trade off. JCSS 9(3), 308–316 (1974)

    MATH  Google Scholar 

  10. Dolev, D., Dwork, C., Pippenger, N., Wigderson, A.: Superconcentrators, generalizers, and generalized connectors with limited depth. In: Proc. 15th STOC, pp. 42–51 (1983)

    Google Scholar 

  11. Dwork, C., Goldberg, A.V., Naor, M.: On memory-bound functions for fighting spam. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 426–444. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  12. Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139–147. Springer, Heidelberg (1993)

    Google Scholar 

  13. Lengauer, T., Tarjan, R.E.: Asymptotically tight bounds on time-space trade-offs in a pebble game. JACM 29(4), 1087–1130 (1982)

    Article MATH MathSciNet  Google Scholar 

  14. Paul, W., Tarjan, R.E., Celoni, J.R.: Space bounds for a game on graphs. In: Proc. 8th STOC, pp. 149–160 (1976)

    Google Scholar 

  15. Pippenger, N.: Superconcentrators. SIAM J. Comput. 6(2), 298–304 (1977)

    Article MATH MathSciNet  Google Scholar 

  16. Tompa, M.: Time-space tradeoffs for computing functions, using connectivity properties of their circuits. JCSS 20(2), 118–132 (1980)

    MATH MathSciNet  Google Scholar 

  17. Upfal, E.: Tolerating linear number of faults in networks of bounded degree. In: Proc. 11th PODC, pp. 83–89 (1992)

    Google Scholar 

  18. Valiant, L.G.: On non-linear lower bounds in computational complexity. In: Proc. 7th STOC, pp. 45–53 (1975)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Microsoft Research, Silicon Valley Campus

    Cynthia Dwork

  2. Weizmann Institute of Science,  

    Moni Naor

  3. University of California, Berkeley

    Hoeteck Wee

Authors
  1. Cynthia Dwork

    You can also search for this author inPubMed Google Scholar

  2. Moni Naor

    You can also search for this author inPubMed Google Scholar

  3. Hoeteck Wee

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. New York University,  

    Victor Shoup

Rights and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Dwork, C., Naor, M., Wee, H. (2005). Pebbling and Proofs of Work. In: Shoup, V. (eds) Advances in Cryptology – CRYPTO 2005. CRYPTO 2005. Lecture Notes in Computer Science, vol 3621. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11535218_3

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp