5 papers
Multi-Prover Interactive Proof Systems with Leakage
Vahid R. Asadi, Atsuya Hasegawa, François Le Gall
It is known that there exist multi-prover interactive protocols ( protocols) for the complexity class , succinct protocols for $\mathsf{…
Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
Vahid R. Asadi, Richard Cleve
The Tree Evaluation Problem () is a computational problem originally proposed as a candidate to prove a separation between complexity classes and $\…
Conditional disclosure of secrets with quantum resources
Vahid R. Asadi, Kohdai Kuroiwa, Debbie Leung +3
The conditional disclosure of secrets (CDS) primitive is among the simplest cryptographic settings in which to study the relationship between communication, randomness, and securit…
Rank lower bounds on non-local quantum computation
Vahid R. Asadi, Eric Culf, Alex May
A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single simultaneous round of communication and shared entanglement. We study two c…
Linear gate bounds against natural functions for position-verification
Vahid Asadi, Richard Cleve, Eric Culf +1
A quantum position-verification scheme attempts to verify the spatial location of a prover. The prover is issued a challenge with quantum and classical inputs and must respond with…