Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInaccessible Entropy I: Inaccessible Entropy Generators and Statistically Hiding Commitments from One-Way Functions
46
0
0.0
(
0
)
Added by
Iftach Haitner
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We put forth a new computational notion of entropy, measuring the (in)feasibility of sampling high-entropy strings that are consistent with a given generator. Specifically, the ith output block of a generator G has accessible entropy at most k if the following holds: when conditioning on its prior coin tosses, no polynomial-time strategy $widetilde{G}$ can generate valid output for Gs ith output block with entropy greater than k. A generator has inaccessible entropy if the total accessible entropy (summed over the blocks) is noticeably smaller than the real entropy of Gs output. As an application of the above notion, we improve upon the result of Haitner, Nguyen, Ong, Reingold, and Vadhan [Sicomp 09], presenting a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions.
rate research
Read More
This paper uses a variant of the notion of emph{inaccessible entropy} (Haitner, Reingold, Vadhan and Wee, STOC 2009), to give an alternative construction and proof for the fundamental result, first proved by Rompel (STOC 1990), that emph{Universal One-Way Hash Functions (UOWHFs)} can be based on any one-way functions. We observe that a small tweak of any one-way function $f$ is already a weak form of a UOWHF: consider the function $F(x,i)$ that returns the $i$-bit-long prefix of $f(x)$. If $F$ were a UOWHF then given a random $x$ and $i$ it would be hard to come up with $x eq x$ such that $F(x,i)=F(x,i)$. While this may not be the case, we show (rather easily) that it is hard to sample $x$ with almost full entropy among all the possible such values of $x$. The rest of our construction simply amplifies and exploits this basic property.Combined with other recent work, the construction of three fundamental cryptographic primitives (Pseudorandom Generators, Statistically Hiding Commitments and UOWHFs) out of one-way functions is now to a large extent unified. In particular, all three constructions rely on and manipulate computational notions of entropy in similar ways. Pseudorandom Generators rely on the well-established notion of pseudoentropy, whereas Statistically Hiding Commitments and UOWHFs rely on the newer notion of inaccessible entropy.
We study the round and communication complexities of various cryptographic protocols. We give tight lower bounds on the round and communication complexities of any fully black-box reduction of a statistically hiding commitment scheme from one-way permutations, and from trapdoor permutations. As a corollary, we derive similar tight lower bounds for several other cryptographic protocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to Simon (EUROCRYPT 98) to the setting of interactive protocols and the reconstruction paradigm of Gennaro and Trevisan (FOCS 00).
In this paper we aim to compare Kurepa trees and Aronszajn trees. Moreover, we analyze the affect of large cardinal assumptions on this comparison. Using the the method of walks on ordinals, we will show it is consistent with ZFC that there is a Kurepa tree and every Kurepa tree contains a Souslin subtree, if there is an inaccessible cardinal. This is stronger than Komjaths theorem that asserts the same consistency from two inaccessible cardinals. We will show that our large cardinal assumption is optimal, i.e. if every Kurepa tree has an Aronszajn subtree then $omega_2$ is inaccessible in the constructible universe textsc{L}. Moreover, we prove it is consistent with ZFC that there is a Kurepa tree $T$ such that if $U subset T$ is a Kurepa tree with the inherited order from $T$, then $U$ has an Aronszajn subtree. This theorem uses no large cardinal assumption. Our last theorem immediately implies the following: assume $textrm{MA}_{omega_2}$ holds and $omega_2$ is not a Mahlo cardinal in $textsc{L}$. Then there is a Kurepa tree with the property that every Kurepa subset has an Aronszajn subtree. Our work entails proving a new lemma about Todorcevics $rho$ function which might be useful in other contexts.
For holographic CFT states near the vacuum, entanglement entropies for spatial subsystems can be expressed perturbatively as an expansion in the one-point functions of local operators dual to light bulk fields. Using the connection between quantum Fisher information for CFT states and canonical energy for the dual spacetimes, we describe a general formula for this expansion up to second-order in the one-point functions, for an arbitrary ball-shaped region, extending the first-order result given by the entanglement first law. For two-dimensional CFTs, we use this to derive a completely explicit formula for the second-order contribution to the entanglement entropy from the stress tensor. We show that this stress tensor formula can be reproduced by a direct CFT calculation for states related to the vacuum by a local conformal transformation. This result can also be reproduced via the perturbative solution to a non-linear scalar wave equation on an auxiliary de Sitter spacetime, extending the first-order result in arXiv/1509.00113.
The closure of the set of entropy functions associated with n discrete variables, Gammar*n, is a convex cone in (2n-1)- dimensional space, but its full characterization remains an open problem. In this paper, we map Gammar*n to an n-dimensional region Phi*n by averaging the joint entropies with the same number of variables, and show that the simpler Phi*n can be characterized solely by the Shannon-type information inequalities
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
