Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInaccessible Entropy II: IE Functions and Universal One-Way Hashing
63
0
0.0
(
0
)
Added by
Iftach Haitner
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
We report the characterization of a universal set of logic gates for one-way quantum computing using a four-photon `star cluster state generated by fusing photons from two independent photonic crystal fibre sources. We obtain a fidelity for the cluster state of 0.66 +/- 0.01 with respect to the ideal case. We perform quantum process tomography to completely characterize a controlled-NOT, Hadamard and T gate all on the same compact entangled resource. Together, these operations make up a universal set of gates such that arbitrary quantum logic can be efficiently constructed from combinations of them. We find process fidelities with respect to the ideal cases of 0.64 +/- 0.01 for the CNOT, 0.67 +/- 0.03 for the Hadamard and 0.76 +/- 0.04 for the T gate. The characterisation of these gates enables the simulation of larger protocols and algorithms. As a basic example, we simulate a Swap gate consisting of three concatenated CNOT gates. Our work provides some pragmatic insights into the prospects for building up to a fully scalable and fault-tolerant one-way quantum computer with photons in realistic conditions.
We present fast strongly universal string hashing families: they can process data at a rate of 0.2 CPU cycle per byte. Maybe surprisingly, we find that these families---though they require a large buffer of random numbers---are often faster than popular hash functions with weaker theoretical guarantees. Moreover, conventional wisdom is that hash functions with fewer multiplications are faster. Yet we find that they may fail to be faster due to operation pipelining. We present experimental results on several processors including low-powered processors. Our tests include hash functions designed for processors with the Carry-Less Multiplication (CLMUL) instruction set. We also prove, using accessible proofs, the strong universality of our families.
A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to average-case reductions. However, for many other classes such as NP, the evidence so far is typically negative, in the sense that the existence of such reductions would cause collapses of the polynomial hierarchy(PH). Basing cryptographic primitives, e.g., the average-case hardness of inverting one-way permutations, on NP-completeness is a particularly intriguing instance. As there is evidence showing that classical reductions from NP-hard problems to breaking these primitives result in PH collapses, it seems unlikely to base cryptographic primitives on NP-hard problems. Nevertheless, these results do not rule out the possibilities of the existence of quantum reductions. In this work, we initiate a study of the quantum analogues of these questions. Aside from formalizing basic notions of quantum reductions and demonstrating powers of quantum reductions by examples of separations, our main result shows that if NP-complete problems reduce to inverting one-way permutations using certain types of quantum reductions, then coNP $subseteq$ QIP(2).
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
