4 papers
Cryptographic Conditions for Efficient Testing of Distributions and Quantum States
Bruno Cavalar, Eli Goldin, Matthew Gray +3
One of the most fundamental problems in distribution testing is the identity testing problem: given samples , the goal is to determine whether the samples are drawn…
A Meta-Complexity Characterization of Minimal Quantum Cryptography
Bruno Cavalar, Boyang Chen, Andrea Coladangelo +4
We give a meta-complexity characterization of EFI pairs, which are considered the "minimal" primitive in quantum cryptography (and are equivalent to quantum commitments). More prec…
On the Computational Hardness of Quantum One-Wayness
Bruno Cavalar, Eli Goldin, Matthew Gray +3
There is a large body of work studying what forms of computational hardness are needed to realize classical cryptography. In particular, one-way functions and pseudorandom generato…
A Meta-Complexity Characterization of Quantum Cryptography
Bruno P. Cavalar, Eli Goldin, Matthew Gray +1
We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribu…