Draft:Conditional disclosure of secrets

The conditional disclosure of secrets (CDS) primitive studied in information-theoretic cryptography allows distributed, non-communicating parties to coordinate the release of information to a third party. CDS was initially introduced for use in the context of private information retrieval, and has been related to communication complexity and non-local quantum computation.

Definition of conditional disclosure of secrets

The conditional disclosure of secrets setting involves three players; Alice, Bob and the referee. Alice receives an input $x\in \{0,1\}^{n}$ and a secret $z\in \{0,1\}$, and Bob receives a string $y\in \{0,1\}^{n}$. A choice of Boolean function $f:\{0,1\}^{2n}\rightarrow \{0,1\}$ is fixed in advance and known to all players. Alice and Bob cannot communicate with one another, but share a string of random bits which we label $r$. Alice and Bob compute messages $m_{A}=m_{A}(x,z,r)$ and $m_{B}=m_{B}(y,r)$, which they send to the referee. The referee knows $(x,y)$. A CDS protocol consists of the encoding maps applied by Alice and Bob.

A protocol is said to be $\epsilon$-correct if, for all $(x,y)\in f^{-1}(1)$, the referee can determine $z$ with probability $1-\epsilon$.

A protocol is said to be $\delta$-secure if, for all $(x,y)\in f^{-1}(0)$ the distribution of the messages is $\delta$ close to a simulator distribution (in total variation distance), where the simulator distribution is independent of $z$.

The communication complexity of a CDS protocol P is the total number of bits of message sent by Alice and Bob. The CDS communication cost of a function, $CDS_{\epsilon ,\delta }(f)$ is the minimal communication cost of an $\epsilon$-correct, $\delta$ secure protocol that implements $f$. The randomness complexity and randomness cost of implementing a function in the CDS model are defined similarly, but consider the number of bits of shared random bits held by Alice and Bob.

Basic properties of the primitive

Amplification

Supposing we have an $\epsilon$-correct and $\delta$-secure CDS protocol, it is known that we can find a new protocol which reduces the correctness and privacy errors at the expense of an increased communication and randomness cost. More specifically, the following theorem has been proven:

Theorem (Amplification). A CDS protocol for f which supports a single-bit secret with privacy and correctness error of 1/3 can be transformed into a new CDS protocol with privacy and correctness error of $2^{-\Omega (k)}$ and communication/randomness complexity which are larger than those of the original protocol by a multiplicative factor of O(k).

In fact, somewhat more than the above theorem is true in that the size of the secret can also be made to be of length $k$, while simultaneously reducing the correctness and privacy errors as above. The proof involves first encoding the secret $z$ into a secret sharing scheme, and then running the original CDS protocol on each share of the resulting scheme.

Closure

If a CDS protocol for a function $f$ is known, then certain simple modifications of $f$ have CDS protocols with similar efficiency.

The simplest case is to consider a CDS protocol for function $f$ and ask for a similarly efficient protocol for the negation of $f$, labelled $\neg f$. This is addressed by the following theorem

Theorem (CDS is closed under complement). Suppose that f has a CDS protocol with randomness cost of $\rho$ bits, communication complexity of $t$ bits, and privacy and correctness errors $\delta =\epsilon =2^{-k}$. Then $\neg$ has a CDS scheme with similar privacy and correctness errors, and randomness and communication complexity of $O(k^{3}\rho ^{2}t+k^{3}\rho ^{3})$.

The cost of a CDS protocol is also closed under formula's, in the following sense. Consider two functions $f_{1}$ and $f_{2}$. Then, the communication and randomness costs of $f_{1}\wedge f_{2}$ as well as $f_{1}\vee f_{2}$ are not much larger than the sum of the costs for $f_{1}$ and $f_{2}$. See Applebaum et al. for a precise statement.

Upper and lower bounds on communication cost

Given a function $f$ we would like to understand the communication and randomness costs to implement $f$ in the CDS setting. Towards understanding this, protocols for implementing CDS have been developed (which give an upper bound on the cost) and lower bound strategies have been developed. For most functions, there is a large gap between the known upper and lower bound, so understanding the cost of CDS remains largely an open problem.

This section presents some of what is known so far about the cost of CDS.

Secret sharing based upper bound

A subject with a close relationship to CDS is secret sharing. Secret sharing constructions provide an upper bound on the cost of CDS protocols.

A secret sharing scheme encodes a secret, $s$ into a set of shares $S_{1},...,S_{n}$. Associated to any secret sharing scheme is an access structure, which consists of a set of authorized sets ${\mathcal {A}}={A_{1},...,A_{k}}$ with $A_{i}\subseteq \{S_{1},...,S_{n}\}$. The authorized sets are those subsets of the $A_{i}$ from which it is possible to recover the secret recorded into the scheme.

A succinct way to describe an access structure is in terms of a function $f_{\mathcal {A}}:\{0,1\}^{n}\rightarrow \{0,1\}$. Each subset of the shares $K[x]\subset \{S_{1},...,S_{n}\}$ is labelled by a string $x\in \{0,1\}^{n}$ such that $x_{i}=1$ if and only if $S_{i}\in K$. Then we define $f_{\mathcal {A}}$ to be such that $f_{\mathcal {A}}(x)=1$ if and only if $K[x]\in {\mathcal {A}}$. In words, the function $f_{\mathcal {A}}$ is 1 when given an authorized subset as input, and 0 otherwise.

A basic result in the theory of secret sharing is that an access structure ${\mathcal {A}}$ can be realized in a secret sharing scheme if and only if $f_{\mathcal {A}}$ is monotone.

The size of a secret sharing scheme is defined as the total number of bits in the shares $S_{i}$. For monotone functions, there is an upper bound on the communication cost in CDS for any monotone function $f$ in terms of the size of any secret sharing scheme with access structure given by $f$,

$CDS_{\epsilon =0,\delta =0}(f)\leq SharingSize(f)$

For some concrete classes of secret sharing schemes, this relationship can be extended to general (non-monotone) Boolean functions. This leads to an upper bound on CDS cost in terms of the size of any span program that computes $f$,

$CDS_{\epsilon =0,\delta =0}(f)\leq SP_{k}(f)$

The class of problems with efficient (polynomial size) span program is the complexity class $Mod_{k}L$, so problems in this class have efficient CDS protocols.

Sub-exponential upper bounds for all functions

Using a matching vector family based construction, it has been proven that

$\forall f,\,\,\,\,\,\,CDS_{\epsilon =0,\delta =0}(f)\leq 2^{O({\sqrt {n\log n}})}$.

The technique for this proof is similar to one used to prove upper bounds on private information retrieval. This upper bound on CDS also leads to sub-exponential upper bounds on the size of a large class of secret sharing schemes.

Lower bounds from communication complexity

In a CDS protocol, the referee is given the inputs $(x,y)$. This means it is not clear if the messages sent by Alice and Bob need to, by themselves, determine the function value. Consequently there is not immediately a lower bound on the communication cost in CDS based on communication complexity.

Nonetheless, with some effort certain lower bounds on communication cost in CDS can be proven in terms of communication complexity. The first such bound proven is that

$CDS_{\epsilon =0.1,\delta =0.1}(f)\geq \Omega (\log R_{A\rightarrow B}(f)+R_{B\rightarrow A}(f))$

where $R_{A\rightarrow B}(f)$ is the communication complexity of computing $f$ in the one-way communication model, where Alice sends a message to Bob and then Bob should determine the function value. The proof of this lower bounds works by showing that a referee who does not receive $(x,y)$ but gets an exponential number of samples of Alice and Bob's messages (using freshly drawn randomness for each sample) can determine $f(x,y)$. The above lower bound is tight in that there are functions saturating it up to constant factors.

Notice that the above bound is never better than logarithmic, since $R_{A\rightarrow B}$ is never larger than linear. Linear lower bounds have been proven on CDS, but these come at the expense of considering either perfect correctness or perfect security.

One result regarding linear lower bounds on CDS that doesn't assume perfect security or perfect correctness is a lower bound in terms of Arthur-Merlin proof complexity, considered in a communication complexity setting. This suggests that proving linear lower bounds in the case of $\epsilon ,\delta >0$ would constitute an interesting step towards proving linear lower bounds on (communication complexity variants of) Arthur-Merlin proofs, which is a well studied open problem in communication complexity.

Quantum CDS

The CDS setting where we allow Alice and Bob to share quantum entanglement, rather than only classically correlated bits, and to send quantum messages has also been considered. An initial result about this setting is that the communication cost in the quantum setting is never larger than the classical communication cost. This follows because a classical protocol remains secure under the formal definition of a quantum CDS protocol.

Quantum CDS is closely related to non-local quantum computation (NLQC). In particular, an example of NLQC known as $f$-routing is equivalent in a certain sense to quantum CDS: an $f$-routing protocol for a function $f$ can be transformed into quantum CDS protocol for the same function, and the resulting protcol uses similar resources. Conversely, a quantum CDS protocol can be transformed into an $f$-routing protocol for the same function, which uses similar communication and using entanglement equal to the amount of randomness+entanglement in the CDS protocol.

For certain partial functions, it is known that quantum CDS protocols can use exponentially fewer resources than any classical protocol.