research-article

Inaccessible entropy

Authors:

Iftach Haitner,

Hoeteck WeeAuthors Info & Claims

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

Pages 611 - 620

https://doi.org/10.1145/1536414.1536497

Published: 31 May 2009 Publication History

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]

AIELLO, W., AND HASTAD, J . Statistical zero-knowledge languages can be recognized in two rounds. JCSS 42, 3 (1991), 327--345.

Digital Library

[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]

FEIGE, U., AND SHAMIR, A. Witness indistinguishable and witness hiding protocols. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC) (1990), ACM Press, pp. 416--426.

Digital Library

[6]

GOLDREICH, O. Concurrent zero-knowledge with timing, revisited. In STOC (2002), pp. 332--340.

Digital Library

[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.

Digital Library

[8]

GOLDREICH, O., AND KRAWCZYK, H. On the composition of zero-knowledge proof systems. SIAM J. Comput. 25, 1 (1996), 169--192. Preliminary version in ICALP'90.

Digital Library

[9]

GOLDREICH, O., MICALI, S., AND WIGDERSON, A. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM 38, 1 (1991), 691--729. Preliminary version in FOCS'86.

Digital Library

[10]

GOLDREICH, O., AND VADHAN, S. P. Comparing entropies in statistical zero knowledge with applications to the structure of szk. In IEEE Conference on Computational Complexity (1999), pp. 54--.

Digital Library

[11]

GOLDWASSER, S., AND MICALI, S. Probabilistic encryption. Journal of Computer and System Sciences 28, 2 (1984), 270--299.

[12]

HAITNER, I., HOCH, J. J., REINGOLD, O., AND SEGEV, G. Finding collisions in interactive protocols -- A tight lower bound on the round complexity of statistically-hiding commitments. In Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS) (2007).

Digital Library

[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).

Digital Library

[14]

HAITNER, I., NGUYEN, M., ONG, S. J., REINGOLD, O., AND VADHAN, S. Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM Journal on Computing (2009). To appear. Preliminary versions in FOCS '06 and STOC '07.

Digital Library

[15]

HAITNER, I., AND REINGOLD, O. A new interactive hashing theorem. In Proceedings of the 18th Annual IEEE Conference on Computational Complexity (2007). Full version on authors' homepage.

Digital Library

[16]

HASTAD, J., IMPAGLIAZZO, R., LEVIN, L. A., AND LUBY, M. A pseudorandom generator from any one-way function. SIAM Journal on Computing 28, 4 (1999), 1364--1396. Preliminary versions in STOC'89 and STOC'90.

Digital Library

[17]

NAOR, M. Bit commitment using pseudorandomness. Journal of Cryptology 4, 2 (1991), 151--158. Preliminary version in CRYPTO'89.

Digital Library

[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.

Digital Library

[19]

NAOR, M., AND YUNG, M. Universal one-way hash functions and their cryptographic applications. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC) (1989), ACM Press, pp. 33--43.

Digital Library

[20]

NGUYEN, M., AND VADHAN, S. Zero knowledge with efficient provers. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC) (2006), ACM Press, pp. 287--295.

Digital Library

[21]

NISAN, N., AND ZUCKERMAN, D. Randomness is linear in space. Journal of Computer and System Sciences 52, 1 (1996), 43--52.

Digital Library

[22]

ONG, S. J., AND VADHAN, S. Zero knowledge and soundness are symmetric. In Advances in Cryptology -- EUROCRYPT 2007 (2007), pp. 187--209.

Digital Library

[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]

PETRANK, E., AND TARDOS, G. On the knowledge complexity of np. In FOCS (1996), pp. 494--503.

Digital Library

[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]

ROMPEL, J. One-way functions are necessary and sufficient for secure signatures. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC) (1990), pp. 387--394.

Digital Library

[27]

SHANNON, C. Communication theory of secrecy systems. Bell System Technical Journal 28, 4 (1949), 656--715.

[28]

YAO, A. C. Theory and applications of trapdoor functions. In FOCS (1982) pp. 80--91.

Cited By

Mazor NZhang J(2024)Simple Constructions from (Almost) Regular One-Way FunctionsJournal of Cryptology10.1007/s00145-024-09507-437:3Online publication date: 30-May-2024
https://doi.org/10.1007/s00145-024-09507-4
Mazor NPass R(2023)Counting Unpredictable Bits: A Simple PRG from One-Way FunctionsTheory of Cryptography10.1007/978-3-031-48615-9_7(191-218)Online publication date: 27-Nov-2023
https://doi.org/10.1007/978-3-031-48615-9_7
Mao XMazor NZhang J(2023)Non-adaptive Universal One-Way Hash Functions from Arbitrary One-Way FunctionsAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30634-1_17(502-531)Online publication date: 15-Apr-2023
https://doi.org/10.1007/978-3-031-30634-1_17
Show More Cited By

Index Terms

Inaccessible entropy
1. Theory of computation

Recommendations

Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function

We give a construction of statistically hiding commitment schemes (those in which the hiding property holds against even computationally unbounded adversaries) under the minimal complexity assumption that one-way functions exist. Consequently, one-way ...
Verifiable Oblivious Transfer Protocol

The Oblivious Transfer (OT), introduced by Rabin in 1981, has become an important and fundamental cryptography technique. An OT protocol should have two important characteristics: the sender's privacy and the chooser's privacy. The sender is a party who ...
On the Power of Secure Two-Party Computation
Proceedings, Part II, of the 36th Annual International Cryptology Conference on Advances in Cryptology --- CRYPTO 2016 - Volume 9815

Ishai, Kushilevitz, Ostrovsky and Sahai STOC 2007, SIAM JoC 2009 introduced the powerful "MPC-in-the-head" technique that provided a general transformation of information-theoretic MPC protocols secure against passive adversaries to a ZK proof in a "...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

May 2009

750 pages

ISBN:9781605585062

DOI:10.1145/1536414

Program Chair:
Michael Mitzenmacher
Harvard University

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '09

Sponsor:

STOC '09: Symposium on Theory of Computing

May 31 - June 2, 2009

MD, Bethesda, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
337
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mazor NZhang J(2024)Simple Constructions from (Almost) Regular One-Way FunctionsJournal of Cryptology10.1007/s00145-024-09507-437:3Online publication date: 30-May-2024
https://doi.org/10.1007/s00145-024-09507-4
Mazor NPass R(2023)Counting Unpredictable Bits: A Simple PRG from One-Way FunctionsTheory of Cryptography10.1007/978-3-031-48615-9_7(191-218)Online publication date: 27-Nov-2023
https://doi.org/10.1007/978-3-031-48615-9_7
Mao XMazor NZhang J(2023)Non-adaptive Universal One-Way Hash Functions from Arbitrary One-Way FunctionsAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30634-1_17(502-531)Online publication date: 15-Apr-2023
https://doi.org/10.1007/978-3-031-30634-1_17
Mazor NZhang J(2021)Simple Constructions from (Almost) Regular One-Way FunctionsTheory of Cryptography10.1007/978-3-030-90453-1_16(457-485)Online publication date: 4-Nov-2021
https://doi.org/10.1007/978-3-030-90453-1_16
Fuller BMeng XReyzin L(2020)Computational Fuzzy ExtractorsInformation and Computation10.1016/j.ic.2020.104602(104602)Online publication date: Jul-2020
https://doi.org/10.1016/j.ic.2020.104602
Vadhan S(2019)Computational entropyProviding Sound Foundations for Cryptography10.1145/3335741.3335767(693-726)Online publication date: 4-Oct-2019
https://dl.acm.org/doi/10.1145/3335741.3335767
Agrawal RChen YHorel TVadhan S(2019)Unifying Computational Entropies via Kullback–Leibler DivergenceAdvances in Cryptology – CRYPTO 201910.1007/978-3-030-26951-7_28(831-858)Online publication date: 1-Aug-2019
https://doi.org/10.1007/978-3-030-26951-7_28
Bitansky NHaitner IKomargodski IYogev E(2019)Distributional Collision Resistance Beyond One-Way FunctionsAdvances in Cryptology – EUROCRYPT 201910.1007/978-3-030-17659-4_23(667-695)Online publication date: 24-Apr-2019
https://doi.org/10.1007/978-3-030-17659-4_23
Chen YGöös MVadhan SZhang JServedio R(2018)A tight lower bound for entropy flatteningProceedings of the 33rd Computational Complexity Conference10.5555/3235586.3235609(1-28)Online publication date: 22-Jun-2018
https://dl.acm.org/doi/10.5555/3235586.3235609
Bitansky NKalai YPaneth ODiakonikolas IKempe DHenzinger M(2018)Multi-collision resistance: a paradigm for keyless hash functionsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188870(671-684)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188870
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents