Abstract
We present a lower bound on the round complexity of a natural class of black-box constructions of statistically hiding commitments from one-way permutations. This implies a \({\rm \Omega}(\frac{n}{\log n})\) lower bound on the round complexity of a computational form of interactive hashing, which has been used to construct statistically hiding commitments (and related primitives) from various classes of one-way functions, starting with the work of Naor, Ostrovsky, Venkatesan and Yung (J. Cryptology, 1998). Our lower bound matches the round complexity of the protocol studied by Naor et al.
Chapter PDF
Similar content being viewed by others
References
Aiello, W., Håstad, J.: Statistical zero-knowledge languages can be recognized in two rounds. JCSS 42(3), 327–345 (1991)
Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC0. In: Proc. 45th FOCS (2004)
Barak, B.: How to go beyond the black-box simulation barrier. In: Proc. 42nd FOCS (2001)
Brassard, G., Crépeau, C., Yung, M.: Constant-round perfect zero-knowledge computationally convincing protocols. Theoretical Computer Science 84(1), 23–52 (1991)
Boppana, R.B., Håstad, J., Zachos, S.: Does co-NP have short interactive proofs? IPL 25(2), 127–132 (1987)
Bellare, M., Jakobsson, M., Yung, M.: Round-Optimal zero-Knowledge arguments based on any one-Way function. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 280–305. Springer, Heidelberg (1997)
Cachin, C., Crépeau, C., Marcil, J.: Oblivious transfer with a memory-bounded receiver. In: Proc. 39th FOCS (1998)
Crépeau, C., Savvides, G.: Optimal reductions between oblivious transfers using interactive hashing. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 201–221. Springer, Heidelberg (2006)
Damgård, I.B.: Interactive hashing can simplify zero-Knowledge protocol design without computational assumptions. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 100–109. Springer, Heidelberg (1994)
Damgård, I.B., Goldreich, O., Okamoto, T., Wigderson, A.: Honest verifier vs dishonest verifier in public coin zero-Knowledge proofs. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 325–338. Springer, Heidelberg (1995)
Damgård, I., Goldreich, O., Wigderson, A.: Information theory versus complexity theory: Another test case. manuscript (1995)
Ding, Y.Z., Harnik, D., Rosen, A., Shaltiel, R.: Constant-Round oblivious transfer in the bounded storage model. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 446–472. Springer, Heidelberg (2004)
Damgård, I., Pedersen, T.P., Pfitzmann, B.: Statistical secrecy and multibit commitments. IEEE Transactions on Information Theory 4(3), 1143–1151 (1998)
Fortnow, L.: The complexity of perfect zero-knowledge. Advances in Computing Research 5, 429–442 (1989)
Fischlin, M.: On the impossibility of constructing non-interactive statistically-Secret protocols from any trapdoor one-way function. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, p. 79. Springer, Heidelberg (2002)
Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM Journal on Computing 35(1), 217–246 (2005)
Goldreich, O., Kahan, A.: How to construct constant-round zero-knowledge proof systems for NP. J. Cryptology 9(3), 167–190 (1996)
Goldreich, O., Krawczyk, H.: On the composition of zero-knowledge proof systems. SIAM Journal on Computing 25(1), 169–192 (1996)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(1), 186–208 (1989)
Goldreich, O., Sahai, A., Vadhan, S.: Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In: Proc. 30th STOC (1998)
Gennaro, R., Trevisan, L.: Lower bounds on efficiency of generic cryptographic constructions. In: Proc. 41st FOCS (2000)
Haitner, I., Horvitz, O., Katz, J., Koo, C.-Y., Morselli, R., Shaltiel, R.: Reducing complexity assumptions for statistically-Hiding commitment. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 58–77. Springer, Heidelberg (2005)
Horvitz, O., Katz, J.: Bounds on the efficiency of “Black-Box” commitment schemes. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 128–139. Springer, Heidelberg (2005)
Harnik, D., Naor, M.: On the compressibility of NP instances and cryptographic applications. In: Proc. 47th FOCS (2006)
Haitner, I., Reingold, O.: A new interactive hashing theorem. ECCC TR06-096 (2006)
Haitner, I., Reingold, O.: Statistically-hiding commitment from any one-way function. Cryptology ePrint Archive, Report 2006/436 (2006)
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proc. 21st STOC (1989)
Koshiba, T., Seri, Y.: Round-efficient one-way permutation based perfectly concealing bit commitment scheme. ECCC TR06-093 (2006)
Kim, J.H., Simon, D.R., Tetali, P.: Limits on the efficiency of one-way permutation-based hash functions. In: Proc. 40th FOCS (1999)
Lin, H., Trevisan, L., Wee, H.M.: On hardness amplification of one-way functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 34–49. Springer, Heidelberg (2005)
Nguyen, M.-H., Ong, S.J., Vadhan, S.: Statistical zero-knowledge arguments for NP from any one-way function. In: Proc. 47th FOCS (2006)
Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP using any one-way permutation. J. Cryptology 11(2), 87–108 (1998)
Nguyen, M.-H., Vadhan, S.: Zero knowledge with efficient provers. In: Proc. 38th STOC (2006)
Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: Proc. 20th STOC (1989)
Ostrovsky, R., Venkatesan, R., Yung, M.: Fair games against an all-powerful adversary. In: AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science (1993)
Ostrovsky, R., Wigderson, A.: One-way fuctions are essential for non-trivial zero-knowledge. In: ISTCS (1993)
Rudich, S.: The use of interaction in public cryptosystems. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 242–251. Springer, Heidelberg (1992)
Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004)
Simon, D.R.: Findings collisions on a one-Way street: Can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334–345. Springer, Heidelberg (1998)
Trevisan, L.: Extractors and pseudorandom generators. JACM 48(4), 860–879 (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Wee, H. (2007). One-Way Permutations, Interactive Hashing and Statistically Hiding Commitments. In: Vadhan, S.P. (eds) Theory of Cryptography. TCC 2007. Lecture Notes in Computer Science, vol 4392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70936-7_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-70936-7_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70935-0
Online ISBN: 978-3-540-70936-7
eBook Packages: Computer ScienceComputer Science (R0)