Comparing classical and quantum conditional disclosure of secrets

The conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in information-theoretic cryptography. Motivated by a connection to non-local quantum computation and position-based cryptography, CDS with quantum resources has recently been considered. Here, we study the differences between quantum and classical CDS, with the aims of clarifying the power of quantum resources in information-theoretic cryptography. We establish the following results:1) We prove a <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi mathvariant="normal">&amp;#x03A9;</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo>&amp;#x2061;</mml:mo> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="sans-serif">R</mml:mi> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mi>A</mml:mi> <mml:mo stretchy="false">&amp;#x2192;</mml:mo> <mml:mi>B</mml:mi> </mml:mrow> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>f</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>+</mml:mo> <mml:mi>log</mml:mi> <mml:mo>&amp;#x2061;</mml:mo> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="sans-serif">R</mml:mi> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mi>B</mml:mi> <mml:mo stretchy="false">&amp;#x2192;</mml:mo> <mml:mi>A</mml:mi> </mml:mrow> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>f</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> </mml:math> lower bound on quantum CDS where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="sans-serif">R</mml:mi> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mi>A</mml:mi> <mml:mo stretchy="false">&amp;#x2192;</mml:mo> <mml:mi>B</mml:mi> </mml:mrow> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>f</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> is the classical one-way communication complexity with perfect correctness.2) We prove a lower bound on quantum CDS in terms of two round, public coin, two-prover interactive proofs.3) For perfectly correct CDS, we give a separation for a promise version of the not-equals function, showing a quantum upper bound of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo>&amp;#x2061;</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> and classical lower bound of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi mathvariant="normal">&amp;#x03A9;</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> .4) We give a logarithmic upper bound for quantum CDS on forrelation, while the best known classical algorithm is linear. We interpret this as preliminary evidence that classical and quantum CDS are separated even with correctness and security error allowed.We also give a separation for classical and quantum private simultaneous message passing for a partial function, improving on an earlier relational separation. Our results use novel combinations of techniques from non-local quantum computation and communication complexity.