Vahid Reza Asadi

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 classes of NLQC, f-routing and f-BB84. These are well studied in the context of position-verification, where they are leading candidates for feasible and secure verification schemes. Both settings require an honest prover implement only O(1) quantum operations. We prove that a dishonest prover must use linear quantum resources to attack the same scheme. First, we give the first non-trivial lower bounds on entanglement in both settings, but are restricted to lower bounding protocols with perfect correctness. Our bound can be stated in terms of the quantum non-deterministic communication complexity of f. For the equality, non-equality, and greater-than functions we obtain linear lower bounds on entanglement for f-routing and f-BB84 in the perfect setting. In a second result, which applies in the robust setting, we give a new lower bound on the number of quantum gates and measurements needed to attack these verification schemes. We lower bound the gates plus measurements linearly in the simultaneous message passing cost of the function f. This leads to a linear bound against the inner product function. This gives a clear separation between the difficulty of implementing these tasks in the honest and dishonest settings, and does so in a noise robust and loss tolerant setting.

The conditional disclosure of secrets (CDS) primitive is among the simplest cryptographic settings in which to study the relationship between communication, randomness, and security. CDS involves two parties, Alice and Bob, who do not communicate but who wish to reveal a secret $z$ to a referee if and only if a Boolean function $f$ has $f(x,y)=1$. Alice knows $x,z$, Bob knows $y$, and the referee knows $x,y$. Recently, a quantum analogue of this primitive called CDQS was defined and related to $f$-routing, a task studied in the context of quantum position-verification. CDQS has the same inputs, outputs, and communication pattern as CDS but allows the use of shared entanglement and quantum messages. We initiate the systematic study of CDQS, with the aim of better understanding the relationship between privacy and quantum resources in the information theoretic setting. Following the classical literature on CDS for guidance, we establish closure under negation, an amplification property, and prove a number of lower bounds on CDQS based on communication complexity.

The conditional disclosure of secrets (CDS) primitive is among the simplest cryptographic settings in which to study the relationship between communication, randomness, and security. CDS involves two parties, Alice and Bob, who do not communicate but who wish to reveal a secret $z$ to a referee if and only if a Boolean function $f$ has $f(x,y)=1$. Alice knows $x,z$, Bob knows $y$, and the referee knows $x,y$. Recently, a quantum analogue of this primitive called CDQS was defined and related to $f$-routing, a task studied in the context of quantum position-verification. CDQS has the same inputs, outputs, and communication pattern as CDS but allows the use of shared entanglement and quantum messages. We initiate the systematic study of CDQS, with the aim of better understanding the relationship between privacy and quantum resources in the information theoretic setting. Following the classical literature on CDS for guidance, we establish closure under negation, an amplification property, and prove a number of lower bounds on CDQS based on communication complexity.