Abstract
We introduce a new type of cryptographic primitives which enforce high communication or storage complexity. To evaluate these primitives on a random input, one has to engage in a protocol of high communication complexity, or one has to use a lot of storage. Therefore, the ability to compute these primitives constitutes a certain “proof of work,” since the computing party is forced to contribute a lot of its communication or storage resources to this task. Such primitives can be used in applications which deal with non-malicious but selfishly resource-maximizing parties. For example, they can be useful in constructing peer-to-peer systems which are robust against so called “free riders.” In this paper we define two such primitives, a communication-enforcing signature and a storage-enforcing commitment scheme, and we give constructions for both.
Supported By Stanford Graduate Fellowship.
Supported by NSF contract #CCR-9732754.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. Adar and B. Huberman, “Free Riding on Gnutella,” First Monday, 5(10), 2000
M. Bellare and O. Goldreich, “On defining proofs of knowledge,” Proc. of CRYPTO’92, pp. 390–420, 1992.
M. Bellare, J. Killian, and P. Rogaway, “The security of the cipher block chaining message authentication code,” Proc. of CRYPTO’94, pp. 341–358. http://www.cs.ucdavis.edu/~rogaway, 1994.
M. Bellare and P. Rogaway, “Random oracles are practical: a paradigm for designing efficient protocols,” Proc. of ACM CCS’93, pp. 62–73, 1993.
M. Ben-Or, “Probabilistic algorithms in finite fields,” Proc. of FOCS’81, pp. 394–398, 1981.
M. Blum, “Coin nipping by telephone,” Proc. of CRYPT0’81, pp. 11–15, 1981.
D. Boneh and M. Franklin, “Identity based encryption from the Weil pairing,” Proc. of CRYPTO’01, pp. 213–229, 2001.
M. Burmester, Y. Desmedt, and J. Seberry, “Equitable key escrow with limited time span (or, How to enforce time expiration cryptographically),” Proc. of Asiacrypt’98, pp. 380–391, 1998.
C. Cachin, J. Camenish, J. Kilian, and J. Muller, “One-round secure computation and secure autonomous mobile agents,” Proc. of ICALP’00, pp. 512–523, 2001.
R. Canetti, O. Goldreich, and S. Halevi, “The random oracle methodology revisited,” Proc. of STOC’98, pp. 209–218, 1998.
D. Chaum and T. Pedersen, “Wallet databases with observers,” Proc. of CRYPTO’92, pp. 89–105, 1992.
C. Dwork, J. Lotspiech, and M. Naor, “Digital signets: self-enforcing protection of digital content,” Poc. of STOC’96, pp. 489–498, 1996.
A. Fiat and A. Shamir, “How to prove yourself: practical solutions to identification and signature problems,” Proc. of CRYPTO’86, pp. 186–194, 1987.
O. Goldreich, “Secure multi-party computation,” On-line manuscript, http://www.wisdom.weizmann.ac.il/~oded, 1998.
O. Goldreich, S. Micali, and A. Wigderson, “How to play any mental game or A completeness theorem for protocols with honest majority,” Proc. of STOC’87, pp. 218–229, 1987. (See also [Gol98]).
S. Goldwasser, S. Micali, and R. Rivest, “A digital signature scheme secure against adaptive chosen-message attacks,” SIAM J. on Computing, 17(2), pp. 281–308, 1988.
A. Joux and K. Nguyen, “Separating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups,” Cryptology ePrint Archive, Report 2001/003, available form http://eprint.iacr.org/, 2001.
E. Kaltofen and A. Lobo, “On rank properties of Toeplitz matrices over finite fields,” Proc. of ISSAC’96, pp. 241–249, 1996.
D. Knuth, The Art of Computer Programming, v. 2, Seminumerical Algorithms, 2nd Ed., Addison-Wesley, 1975.
H. Krawczyk, “LFSR-based hashing and authentication,” In Proc. of CRYPTO’94, pp. 129–139, 1994.
Y. Mansour, N. Nisan, and P. Tiwari, “The computational complexity of universal hash functions,” Theoretical Computer Science, v. 107(1), pp. 121–133, 1993.
K. Mehlhorn and E. Schmidt, “Las Vegas is better than determinism in VLSI and distributed computing,” Proc. of STOC’82, pp. 330–337, 1982.
N. Nisan and A. Wigderson, “On rank vs. communication complexity,” Proc. of FOCS’94, pp. 841–836, 1994.
T. Pedersen, “Non-interactive and information-theoretic secure verifiable secret sharing,” Proc. of CRYPTO’91, pp. 129–140, 1991.
R. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Comm. of ACM, 21, pp. 120–126, 1977.
A. Sadeghi and M. Steiner, “Assumptions related to discrete logarithms: why subtleties make a real difference,” Proc. of EUROCRYPT’01, pp. 244–261, 2001.
T. Sander, private communications, 2001.
S. Saroiu, P. Gummadi, and S. Gribble, “A measurement study of peer-to-peer file sharing systems,” Proc. of Multimedia Computing and Networking 2002, January, 2002.
C. Schnorr, “Security of DL-encryption and signatures against generic attacks—A survey,” Proc. of PKC&CNTC’2000, 2000.
J. Schwartz, “Probabilistic algorithms for verification of polynomial identities,” J. of ACM, v. 27, pp. 701–717, 1980.
V. Shoup, “Lower bounds for discrete logarithms and related problems,” Proc. of Eurocrypt’97, pp. 256–266, 1997.
A.-C. Yao, “Protocols for secure computations,” Proc. of FOCS’82, pp. 160–164, 1982.
A.-C. Yao, “Lower bounds by probabilistic arguments,” Proc. of FOCS’83, pp. 420–428, 1983.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 IFCA/Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Golle, P., Jarecki, S., Mironov, I. (2003). Cryptographic Primitives Enforcing Communication and Storage Complexity. In: Blaze, M. (eds) Financial Cryptography. FC 2002. Lecture Notes in Computer Science, vol 2357. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36504-4_9
Download citation
DOI: https://doi.org/10.1007/3-540-36504-4_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00646-6
Online ISBN: 978-3-540-36504-4
eBook Packages: Springer Book Archive