Abstract
We investigate a new notion of security for “cryptographic functions” that we term seed incompressibility (SI). We argue that this notion captures some of the intuition for the alleged security of constructions in the random-oracle model, and indeed we show that seed incompressibility suffices for some applications of the random oracle methodology. Very roughly, a function family f s (·) with |s| = n is seed incompressible if given (say) n/2 bits of advice (that can depend on the seed s) and an oracle access to f s (·), an adversary cannot “break f s (·)” any better than given only oracle access to f s (·) and no advice.
The strength of this notion depends on what we mean by “breaking f s (·)”. We first show that for any family f s there exists an adversary that can distinguish f s (·) from a random function using n/2 bits of advice, so seed incompressible pseudo-random functions do not exist. Then we consider the weaker notion of seed-incompressible correlation intractability. We show that although the negative results can be partially extended also to this weaker notion, they cannot rule it out altogether. More importantly, the settings that we cannot rule out still suffice for many applications. In particular, we show that they suffice for constructing collision-resistant hash functions and for removing interaction from Σ-protocols (3-round honest verifier zero-knowledge protocols).
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
Barak, B., Lindell, Y., Vadhan, S.: Lower Bounds for Non-Black-Box Zero-Knowledge. The Journal of Computer and System Sciences 72(2), 321–391 (2006) (JCSS FOCS 2003 Special Issue)
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: 1st Conference on Computer and Communications Security, pp. 62–73. ACM, New York (1993)
Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995)
Canetti, R.: Towards realizing random oracles: Hash functions that hide all partial information. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 455–469. Springer, Heidelberg (1997)
Canetti, R., Dodis, Y., Halevi, S., Kushilevitz, E., Sahai, A.: Exposure-Resilient Functions and All-or-Nothing Transforms. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 453–469. Springer, Heidelberg (2000)
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. Journal of the ACM 51(4), 209–218 (2004) Preliminary version in STOC 1998, pp. 209–218.
Canetti, R., Micciancio, D., Reingold, O.: Perfectly one-way probabilistic hashing. In: Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, Dallas, TX, May 1998, pp. 131–140. ACM Press, New York (1998)
Cash, D., Ding, Y.Z., Dodis, Y., Lee, W., Lipton, R.J., Walfish, S.: Intrusion-Resilient Key Exchange in the Bounded Retrieval Model. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 479–498. Springer, Heidelberg (2007)
Coron, J., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damgrd Revisited: How to Construct a Hash Function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430–448. Springer, Heidelberg (2005)
Damgard, I.: On Σ-Protocols. Lecture notes for Cryptologic Protocol Theory course, Aarhus University (2005), http://www.daimi.au.dk/%7Eivan/Sigma.pdf
DiCrescenzo, G., Lipton, R.J., Walfish, S.: Perfectly Secure Password Protocols in the Bounded Retrieval Model. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 225–244. Springer, Heidelberg (2006)
Dierks, T., Allen, C.: RFC2246:The TLS Protocol. RFC 2246, The Internet Society, Network Working Group (1999)
Dziembowski, S.: Intrusion-Resilience Via the Bounded-Storage Model. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 207–224. Springer, Heidelberg (2006)
Fiat, A., Shamir, A.: How to prove yourself. practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–189. Springer, Heidelberg (1987)
Goldreich, O.: Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Algorithms and Combinatorics, vol. 17. Springer, Heidelberg (1998)
Goldwasser, S., Kalai, Y.T.: On the (In)security of the Fiat-Shamir Paradigm. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), pp. 102–115. IEEE Computer Society Press, Los Alamitos (2003)
Harnik, D., Naor, M.: On the Compressibility of NP Instances and Cryptographic Applications. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 719–728. IEEE Computer Society Press, Los Alamitos (2006)
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 44–61. ACM Press, New York (1989)
Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, May 1992, pp. 723–732. ACM Press, New York (1992)
Micali, S.: CS proofs. In: 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), pp. 436–453. IEEE Computer Society Press, Los Alamitos (1994)
Micali, S.: Computationally Sound Proofs. SIAM Journal on Computing 30(4), 1253–1298 (2000)
Naor, M., Nissim, K.: Computationally sound proofs: Reducing the number of random oracle calls (manuscript, 1999)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Halevi, S., Myers, S., Rackoff, C. (2008). On Seed-Incompressible Functions. In: Canetti, R. (eds) Theory of Cryptography. TCC 2008. Lecture Notes in Computer Science, vol 4948. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78524-8_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-78524-8_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78523-1
Online ISBN: 978-3-540-78524-8
eBook Packages: Computer ScienceComputer Science (R0)