Inaccessible entropy

ABSTRACT

We put forth a new computational notion of entropy, which measures the (in)feasibility of sampling high entropy strings that are consistent with a given protocol. Specifically, we say that the i'th round of a protocol (A,B) has *accessible entropy* at most k, if no polynomial-time strategy A* can generate messages for A such that the entropy of its message in the i'th round has entropy greater than k when conditioned both on prior messages of the protocol and on prior coin tosses of A*. We say that the protocol has *inaccessible entropy* if the total accessible entropy (summed over the rounds) is noticeably smaller than the real entropy of A's messages, conditioned only on prior messages (but not the coin tosses of A). As applications of this notion, we -- Give a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions. -- Prove that constant-round statistically hiding commitments are necessary for constructing constant-round zero-knowledge proof systems for NP that remain secure under parallel composition (assuming the existence of one-way functions).

REFERENCES

• 1: William Aiello , Johan Hastad, Statistical zero-knowledge languages can be recognized in two rounds, Journal of Computer and System Sciences, v.42 n.3, p.327-345, June 1991 [doi>10.1016/0022-0000(91)90006-Q]
• 2: BARAK, B. , SHALTIEL, R., AND WIGDERSON, A. Computational analogues of entropy. In RANDOM-APPROX (2003).
• 3: BLUM, M., AND MICALI, S. How to generate cryptographically strong sequences of pseudo random bits. pp. 112--117.
• 4: DING, Y. Z., HARNIK, D. , ROSEN, A., AND SHALTIEL, R. Constant-round oblivious transfer in the bounded storage model. In Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004 (2004), pp. 446--472.
• 5: U. Feige , A. Shamir, Witness indistinguishable and witness hiding protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.416-426, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100272]
• 6: Oded Goldreich, Concurrent zero-knowledge with timing, revisited, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509959]
• 7: GOLDREICH, O., AND KAHAN, A. How to construct constant-round zero-knowledge proof systems for NP. Journal of Cryptology 9, 3 (1996), 167--190.
• 8: Oded Goldreich , Hugo Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM Journal on Computing, v.25 n.1, p.169-192, Feb. 1996 [doi>10.1137/S0097539791220688]
• 9: Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
• 10: Oded Goldreich , Salil Vadhan, Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK, Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, p.54, May 04-06, 1999
• 11: GOLDWASSER , S. , AND MICALI , S. Probabilistic encryption. Journal of Computer and System Sciences 28, 2 (1984), 270--299.
• 12: Iftach Haitner , Jonathan J. Hoch , Omer Reingold , Gil Segev, Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.669-679, October 21-23, 2007 [doi>10.1109/FOCS.2007.27]
• 13: HAITNER, I., HORVITZ, O., KATZ, J., KOO, C., MORSELLI, R., AND SHALTIEL, R. Reducing complexity assumptions for statistically-hiding commitment. In Advances in Cryptology -- EUROCRYPT 2005 (2005).
• 14: Minh-Huyen Nguyen , Shien Jin Ong , Salil Vadhan, Statistical Zero-Knowledge Arguments for NP from Any One-Way Function, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.3-14, October 21-24, 2006 [doi>10.1109/FOCS.2006.71]
• 15: Iftach Haitner , Omer Reingold, A New Interactive Hashing Theorem, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.319-332, June 13-March 16, 2007 [doi>10.1109/CCC.2007.3]
• 16: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 17: Moni Naor, Bit Commitment Using Pseudo-Randomness, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.128-136, August 20-24, 1989
• 18: NAOR, M., OSTROVSKY, R., VENKATESAN, R., AND YUNG, M. Perfect zero-knowledge arguments for NP using any one-way permutation. Journal of Cryptology 11, 2 (1998), 87--108. Preliminary version in CRYPTO'92.
• 19: M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
• 20: Minh-Huyen Nguyen , Salil Vadhan, Zero knowledge with efficient provers, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132559]
• 21: Noam Nisan , David Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, v.52 n.1, p.43-52, Feb. 1996 [doi>10.1006/jcss.1996.0004]
• 22: Shien Jin Ong , Salil Vadhan, Zero Knowledge and Soundness Are Symmetric, Proceedings of the 26th annual international conference on Advances in Cryptology, p.187-209, May 20-24, 2007, Barcelona, Spain [doi>10.1007/978-3-540-72540-4_11]
• 23: OSTROVSKY, R., AND WIGDERSON, A. One-way functions are essential for non-trivial zero-knowledge. In Proceedings of the 2nd Israel Symposium on Theory of Computing Systems (1993), IEEE Computer Society, pp. 3--17.
• 24: E. Petrank , G. Tardos, On the knowledge complexity of N P, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.494, October 14-16, 1996
• 25: RENNER , R., AND WOLF, S. Smooth Renyi entropy and applications. In IEEE International Symposium on Information Theory - ISIT 2004 (June 2004), IEEE, p. 233.
• 26: J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.387-394, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100269]
• 27: SHANNON, C. Communication theory of secrecy systems. Bell System Technical Journal 28, 4 (1949), 656--715.
• 28: Andrew C. Yao, Theory and application of trapdoor functions, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, p.80-91, November 03-05, 1982

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Security, Theory

Keywords:
commitment schemes, computational complexity, cryptography, interactive hashing, one-way functions, zero knowledge