@conference {634708,
	title = {Inaccessible entropy},
	booktitle = {Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC {\textquoteleft}09)},
	year = {2009},
	pages = {611-620},
	publisher = {ACM},
	organization = {ACM},
	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\){\textquoteright}th round of a protocol\&nbsp;\((\mathsf{A,B})\)\&nbsp;has\&nbsp;accessible entropy\&nbsp;at most\&nbsp;\(k\), if no polynomial-time strategy\&nbsp;\(\mathsf{A}^*\)\&nbsp;can generate messages for\&nbsp;\(\mathsf{A}\) such that the entropy of its message in the\&nbsp;\(i\){\textquoteright}th round has entropy greater than\&nbsp;\(k\)\&nbsp;when conditioned both on prior messages of the protocol and on prior coin tosses of\&nbsp;\(\mathsf{A}^*\). We say that the protocol has\&nbsp;inaccessible entropy\&nbsp;if the total accessible entropy (summed over the rounds) is noticeably smaller than the real entropy of\&nbsp;\(\mathsf{A}\){\textquoteright}s messages, conditioned only on prior messages (but not the coin tosses of \(\mathsf{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).
		
	

},
	url = {https://dl.acm.org/citation.cfm?id=1536497},
	author = {Iftach Haitner and Omer Reingold and Salil Vadhan and Hoeteck Wee}
}
