Abstract
In 1992, Dwork and Naor proposed that e-mail messages be accompanied by easy-to-check proofs of computational effort in order to discourage junk e-mail, now known as spam. They proposed specific CPU-bound functions for this purpose. Burrows suggested that, since memory access speeds vary across machines much less than do CPU speeds, memory-bound functions may behave more equitably than CPU-bound functions; this approach was first explored by Abadi, Burrows, Manasse, and Wobber [3].
We further investigate this intriguing proposal. Specifically, we
1) Provide a formal model of computation and a statement of the problem;
2) Provide an abstract function and prove an asymptotically tight amortized lower bound on the number of memory accesses required to compute an acceptable proof of effort; specifically, we prove that, on average, the sender of a message must perform many unrelated accesses to memory, while the receiver, in order to verify the work, has to perform significantly fewer accesses;
3) Propose a concrete instantiation of our abstract function, inspired by the RC4 stream cipher;
4) Describe techniques to permit the receiver to verify the computation with no memory accesses;
5) Give experimental results showing that our concrete memory-bound function is only about four times slower on a 233 MHz settop box than on a 3.06 GHz workstation, and that speedup of the function is limited even if an adversary knows the access sequence and uses optimal off-line cache replacement.
Chapter PDF
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
Abadi, M., Burrows, M. (multiple) private communication(s)
Abadi, M.: private communication
Abadi, M., Burrows, M., Manasse, M., Wobber, T.: Moderately Hard, Memory-Bound Functions. In: Proceedings of the 10th Annual Network and Distributed System Security Symposium (February 2003)
Ajtai, M.: Determinism versus Non-Determinism for Linear Time RAMs, In: STOC 1999, pp. 632–641 (1999)
Ajtai, M.: A Non-linear Time Lower Bound for Boolean Branching Programs. In: FOCS 1999, pp. 60–70 (1999)
Alon, N., Spencer, J.: The Probabilistic Method. Wiley & Sons, New-York (1992)
Beame, P., Saks, M.E., Sun, X., Vee, E.: Super-linear time-space tradeoff lower bounds for randomized computation. In: FOCS 2000, pp. 169–179 (2000)
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001)
Diffie, W., Hellman, M.E.: Exhaustive cryptanalysis of the NBS Data Encryption Standard. Computer 10, 74–84 (1977)
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)
Dwork, C., Naor, M.: An Efficient Existentially Unforgeable Signature Scheme and Its Applications. Journal of Cryptology 11(3), 187–208 (1998)
Fiat, A.: Batch RSA. Journal of Cryptology 10(2), 75–88 (1997)
Fiat, A., Naor, M.: Rigorous Time/Space Tradeoffs for Inverting Functions. In: STOC 1991, pp. 534–541 (1991)
Fiat, A., Shamir, A.: How to Prove Yourself. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 641–654. Springer, Heidelberg (1985)
Fluhrer, S., Mantin, I., Shamir, A.: Attacks on RC4 and WEP. In: Cryptobytes 2002 (2002)
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996), Also available: http://www.cacr.math.uwaterloo.ca/hac/
Back, A.: Hashcash - A Denial of Servic Counter-Measure, available at http://www.cypherspace.org/hashcash/hashcash.pdf
Bellare, M., Garay, J.A., Rabin, T.: Fast Batch Verification for Modular Exponentiation and Digital Signatures. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 236–250. Springer, Heidelberg (1998)
Bellare, M., Garay, J.A., Rabin, T.: Batch Verification with Applications to Cryptography and Checking, In: LATIN 1998, pp. 170–191 (1998)
Hellman, M.: A Cryptanalytic Time Memory Trade-Off. IEEE Trans. Infor. Theory 26, 401–406 (1980)
Luby, M., Rackoff, C.: How to Construct Pseudorandom Permutations and Pseudorandom Functions. SIAM J. Computing 17(2), 373–386 (1988)
Mantin, I.: Analysis of the Stream Cipher RC4, Master’s Thesis, Weizmann Institute of Science (2001), Available http://www.wisdom.weizmann.ac.il/~itsik/RC4/rc4.html
Mironov, I.: (Not So) Random Shuffles of RC4, In: Proc. of CRYPTO 2002 (2002)
Naor, M., Yung, M.: Universal One-Way Hash Functions and their Cryptographic Applications, In: STOC 1989, pp. 33–43 (1989)
Oechslin, P.: Making a faster Cryptanalytic Time-Memory Trade-Off, these proceedings
van Oorschot, P.C., Wiener, M.J.: Parallel Collision Search with Cryptanalytic Applications. Journal of Cryptology 12(1), 1–28 (1999)
Schroeppel, R., Shamir, A.: A T = O(2(n/2)), S = O(2(n/4)) Algorithm for Certain NP-Complete Problems. SIAM J. Comput. 10(3), 456–464 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dwork, C., Goldberg, A., Naor, M. (2003). On Memory-Bound Functions for Fighting Spam. In: Boneh, D. (eds) Advances in Cryptology - CRYPTO 2003. CRYPTO 2003. Lecture Notes in Computer Science, vol 2729. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45146-4_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-45146-4_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40674-7
Online ISBN: 978-3-540-45146-4
eBook Packages: Springer Book Archive