{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T05:22:21Z","timestamp":1740374541621,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540206804"},{"type":"electronic","value":"9783540245971"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-24597-1_37","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T07:39:20Z","timestamp":1280389160000},"page":"434-442","source":"Crossref","is-referenced-by-count":5,"title":["Moderately Hard Functions: From Complexity to Spam Fighting"],"prefix":"10.1007","author":[{"given":"Moni","family":"Naor","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"37_CR1","unstructured":"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)"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating Hard Instances of Lattice Problems. In: 28th Annual Symposium on Theory Of Computing (STOC), pp. 99\u2013108 (1996)","DOI":"10.1145\/237814.237838"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Determinism versus Non-Determinism for Linear Time RAMs. In: STOC 1999, pp. 632\u2013641 (1999)","DOI":"10.1145\/301250.301424"},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: A Non-linear Time Lower Bound for Boolean Branching Programs. In: FOCS 1999, pp. 60\u201370 (1999)","DOI":"10.1109\/SFFCS.1999.814578"},{"key":"37_CR5","unstructured":"Back, A.: Hashcash - A Denial of Servic Counter-Measure, available at http:\/\/www.cypherspace.org\/hashcash\/hashcash.pdf"},{"key":"37_CR6","doi-asserted-by":"crossref","unstructured":"Beame, P., Saks, M.E., Sun, X., Vee, E.: Super-linear time-space tradeoff lower bounds for randomized computation. In: FOCS 2000, pp. 169\u2013179 (2000)","DOI":"10.1109\/SFCS.2000.892078"},{"key":"37_CR7","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldwasser, S.: Verifiable Partial Key Escrow. In: Proc. of 4th ACM Symp. on Computer and Communications Security, pp. 78\u201391 (1997)","DOI":"10.1145\/266420.266439"},{"key":"37_CR8","unstructured":"Bellare, M., Goldwasser, S.: Encapsulated key escrow. MIT Laboratory for Computer Science Technical Report 688 (April 1996)"},{"key":"37_CR9","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1109\/18.50372","volume":"36\/1","author":"M. Ben-Or","year":"1990","unstructured":"Ben-Or, M., Goldreich, O., Micali, S., Rivest, R.L.: A Fair Protocol for Signing Contracts. IEEE Transactions on Information Theory\u00a036\/1, 40\u201346 (1990)","journal-title":"IEEE Transactions on Information Theory"},{"key":"37_CR10","doi-asserted-by":"crossref","unstructured":"Blum, M.: How to Exchange (Secret) Keys. In: Proc. 15th ACM Symp. on Theory of Computing, pp. 440\u2013447 (1983), ACM TOCS 1(2), 175\u2013193 (1983)","DOI":"10.1145\/800061.808775"},{"issue":"2","key":"37_CR11","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0215025","volume":"15","author":"L. Blum","year":"1986","unstructured":"Blum, L., Blum, M., Shub, M.: A Simple Unpredictable Pseudo-Random Number Generator. SIAM J. Comput.\u00a015(2), 364\u2013383 (1986)","journal-title":"SIAM J. Comput."},{"key":"37_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/3-540-44598-6_15","volume-title":"Advances in Cryptology - CRYPTO 2000","author":"D. Boneh","year":"2000","unstructured":"Boneh, D., Naor, M.: Timed Commitments. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol.\u00a01880, pp. 236\u2013254. Springer, Heidelberg (2000)"},{"key":"37_CR13","doi-asserted-by":"crossref","unstructured":"Cai, J.Y., Lipton, R.J., Sedgwick, R., Yao, A.C.: Towards uncheatable benchmarks, Structures in Complexity. In: Proc. Structures in Complexity, pp. 2\u201311 (1993)","DOI":"10.1109\/SCT.1993.336546"},{"key":"37_CR14","doi-asserted-by":"crossref","unstructured":"Canetti, R., Goldreich, O., Goldwasser, S., Micali, S.: Resettable Zero-Knowledge, ECCC Report TR99-042 (October 27, 1999), Proc. of 32nd ACM Symp. on Theory of Computing, pp. 235\u2013244 (2000)","DOI":"10.1145\/335305.335334"},{"key":"37_CR15","unstructured":"Canetti, R., Kilian, J., Petrank, E., Rosen, A.: Concurrent Zero-Knowledge Requires \u03a9\u0303(log n) Rounds. In: Proc. of the 33rd ACM Symposium on the Theory of Computing, pp. 570\u2013579 (2001), Full version: Electronic Colloquium on Computational Complexity, Report TR01-050, vol. 8 (2001), Available: www.eccc.uni-trier.de\/eccc\/"},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"Cleve, R.: Limits on the Security of Coin Flips when Half the Processors Are Faulty. In: Proc. of 18th ACM Symp. on Theory of Computing, pp. 364\u2013369 (1986)","DOI":"10.1145\/12130.12168"},{"key":"37_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1007\/0-387-34805-0_50","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"R. Cleve","year":"1990","unstructured":"Cleve, R.: Controlled gradual disclosure schemes for random bits and their applications. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435, pp. 573\u2013588. Springer, Heidelberg (1990)"},{"key":"37_CR18","unstructured":"Cleve, R., Impagliazzo, R.: Martingales, collective coin flipping and discrete control processes (1993) (manuscript), Available: http:\/\/www.cpsc.ucalgary.ca\/~cleve\/papers.html"},{"key":"37_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1007\/3-540-45539-6_30","volume-title":"Advances in Cryptology - EUROCRYPT 2000","author":"I. Damg\u00e5rd","year":"2000","unstructured":"Damg\u00e5rd, I.: Concurrent Zero-Knowledge in the auxiliary string model. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol.\u00a01807, pp. 418\u2013430. Springer, Heidelberg (2000)"},{"issue":"4","key":"37_CR20","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF00191356","volume":"8","author":"I. Damg\u00e5rd","year":"1995","unstructured":"Damg\u00e5rd, I.: Practical and Provably Secure Release of a Secret and Exchange of Signatures. J. of Cryptology\u00a08(4), 201\u2013222 (1995)","journal-title":"J. of Cryptology"},{"key":"37_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/3-540-45748-8_24","volume-title":"Peer-to-Peer Systems","author":"J. Douceur","year":"2002","unstructured":"Douceur, J.: The Sybil Attack. In: Druschel, P., Kaashoek, M.F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol.\u00a02429, p. 251. Springer, Heidelberg (2002)"},{"issue":"2","key":"37_CR22","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1137\/S0097539795291562","volume":"30","author":"D. Dolev","year":"2000","unstructured":"Dolev, D., Dwork, C., Naor, M.: Non-malleable Cryptography. Siam J. on Computing\u00a030(2), 391\u2013437 (2000)","journal-title":"Siam J. on Computing"},{"key":"37_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/978-3-540-45146-4_25","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"C. Dwork","year":"2003","unstructured":"Dwork, C., Goldberg, A., Naor, M.: On Memory-Bound Functions for Fighting Spam. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol.\u00a02729, pp. 426\u2013444. Springer, Heidelberg (2003)"},{"key":"37_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/3-540-48071-4_10","volume-title":"Advances in Cryptology - CRYPTO \u201992","author":"C. Dwork","year":"1993","unstructured":"Dwork, C., Naor, M.: Pricing via Processing -or- Combatting Junk Mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol.\u00a0740, pp. 139\u2013147. Springer, Heidelberg (1993)"},{"key":"#cr-split#-37_CR25.1","doi-asserted-by":"crossref","unstructured":"Dwork, C., Naor, M.: Zaps and their applications. In: Proc. 41st IEEE Symp. on Foundations of Computer Science, pp. 283???293 (2000);","DOI":"10.1109\/SFCS.2000.892117"},{"key":"#cr-split#-37_CR25.2","unstructured":"Also: Electronic Colloquium on Computational Complexity (ECCC)(001) (2002)"},{"key":"37_CR26","doi-asserted-by":"crossref","unstructured":"Dwork, C., Naor, M., Sahai, A.: Concurrent Zero-Knowledge. In: Proc. of the 30th ACM Symposium on the Theory of Computing, pp. 409\u2013418 (1998)","DOI":"10.1145\/276698.276853"},{"key":"37_CR27","doi-asserted-by":"crossref","unstructured":"Dwork, C., Stockmeyer, L.: 2-Round Zero-Knowledge and Proof Auditors. In: Proc. of the 34th ACM Symposium on Theory of Computing, pp. 322\u2013331 (2002)","DOI":"10.1145\/509907.509958"},{"issue":"6","key":"37_CR28","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1145\/3812.3818","volume":"28","author":"S. Even","year":"1985","unstructured":"Even, S., Goldreich, O., Lempel, A.: A Randomized Protocol for Signing Contracts. CACM\u00a028(6), 637\u2013647 (1985)","journal-title":"CACM"},{"issue":"5","key":"37_CR29","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0222061","volume":"22","author":"J. Feigenbaum","year":"1993","unstructured":"Feigenbaum, J., Fortnow, L.: Random-Self-Reducibility of Complete Sets. SIAM J. Comput.\u00a022(5), 994\u20131005 (1993)","journal-title":"SIAM J. Comput."},{"key":"37_CR30","doi-asserted-by":"crossref","unstructured":"Franklin, M., Malkhi, D.: Auditable metering with lightweight security. Journal of Computer Security\u00a06(4) (1998)","DOI":"10.3233\/JCS-1998-6402"},{"key":"37_CR31","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundation of Cryptography \u2013 Basic Tools","author":"O. Goldreich","year":"2001","unstructured":"Goldreich, O.: Foundation of Cryptography \u2013 Basic Tools. Cambridge University Press, Cambridge (2001)"},{"issue":"1","key":"37_CR32","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1137\/S0097539791220688","volume":"25","author":"O. Goldreich","year":"1996","unstructured":"Goldreich, O., Krawczyk, H.: On the Composition of Zero Knowledge Proof Systems. SIAM J. on Computing\u00a025(1), 169\u2013192 (1996)","journal-title":"SIAM J. on Computing"},{"key":"37_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/BFb0055485","volume-title":"Financial Cryptography","author":"D. Goldschlag","year":"1998","unstructured":"Goldschlag, D., Stubblebine, S.: Publicly Verifiable Lotteries: Applications of Delaying Functions. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol.\u00a01465, pp. 214\u2013226. Springer, Heidelberg (1998)"},{"key":"37_CR34","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1109\/SFCS.1997.646120","volume-title":"Proceedings of 38th Annual Symposium on Foundations of Computer Science","author":"S. Goldwasser","year":"1997","unstructured":"Goldwasser, S.: New directions in cryptography: Twenty some years later. In: Proceedings of 38th Annual Symposium on Foundations of Computer Science, pp. 314\u2013324. IEEE, Los Alamitos (1997)"},{"key":"37_CR35","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: STOC 1989, pp. 44\u201361(1989)","DOI":"10.1145\/73007.73012"},{"key":"37_CR36","unstructured":"Juels, A., Brainard, J.: Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks"},{"key":"37_CR37","doi-asserted-by":"crossref","unstructured":"Kilian, J., Petrank, E., Rackoff, C.: Lower Bounds for Zero Knowledge on the Internet. In: IEEE 38th Symp. on Foundations of Computer Science, pp. 484\u2013492 (1998)","DOI":"10.1109\/SFCS.1998.743499"},{"key":"37_CR38","doi-asserted-by":"crossref","unstructured":"Luby, M., Micali, S., Rackoff, C.: How to Simultaneously Exchange a Secret Bit by Flipping a Symmetrically-Biased Coin. In: Proc. IEEE Symp. Foundations of Computer Science, pp. 11\u201321 (1983)","DOI":"10.1109\/SFCS.1983.25"},{"key":"37_CR39","doi-asserted-by":"publisher","DOI":"10.1201\/9781439821916","volume-title":"Handbook of Applied Cryptography","author":"A. Menezes","year":"1996","unstructured":"Menezes, A., van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)"},{"key":"37_CR40","doi-asserted-by":"crossref","unstructured":"Naor, M., Pinkas, B., Sumner, R.: Privacy Preserving Auctions and Mechanism Design. In: Proc. of the 1st ACM conference on E-Commerce, November 1999, pp. 129\u2013139 (1999)","DOI":"10.1145\/336992.337028"},{"key":"37_CR41","unstructured":"Rivest, R.: Description of the LCS35 Time Capsule Crypto-Puzzle (April 4, 1999), available: http:\/\/www.lcs.mit.edu\/research\/demos\/cryptopuzzle0499"},{"key":"37_CR42","unstructured":"Rivest, R., Shamir, A., Wagner, D.: Time lock puzzles and timed release cryptography, Technical report, MIT\/LCS\/TR-684"},{"key":"37_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/3-540-44598-6_28","volume-title":"Advances in Cryptology - CRYPTO 2000","author":"A. Rosen","year":"2000","unstructured":"Rosen, A.: A note on the round-complexity of concurrent zero-knowledge. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol.\u00a01880, pp. 451\u2013468. Springer, Heidelberg (2000)"},{"key":"37_CR44","unstructured":"Rosenthal, D.H.S., Roussopoulos, M., Maniatis, P., Baker, M.: Economic Measures to Resist Attacks on a Peer-to-Peer Network. In: Proceedings of the Workshop on Economics of Peer-to-Peer Systems (June 2003)"},{"key":"37_CR45","doi-asserted-by":"crossref","unstructured":"Syverson, P.: Weakly Secret Bit Commitment: Applications to Lotteries and Fair Exchange. In: Proceedings of the 1998 IEEE Computer Security Foundations Workshop (CSFW11) (June 1998)","DOI":"10.21236\/ADA464109"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24597-1_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T15:21:31Z","timestamp":1740324091000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24597-1_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540206804","9783540245971"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24597-1_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}