Conditional disclosure of secrets
In-game article clicks load inline without leaving the challenge.
Conditional disclosure of secrets (CDS) is a primitive, studied in information-theoretic cryptography, that 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 ∈ { 0 , 1 } n {\displaystyle x\in \{0,1\}^{n}} and a secret z ∈ { 0 , 1 } {\displaystyle z\in \{0,1\}}, and Bob receives a string y ∈ { 0 , 1 } n {\displaystyle y\in \{0,1\}^{n}}. A choice of Boolean function f : { 0 , 1 } 2 n → { 0 , 1 } {\displaystyle 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 {\displaystyle r}. Alice and Bob compute messages m A = m A ( x , z , r ) {\displaystyle m_{A}=m_{A}(x,z,r)} and m B = m B ( y , r ) {\displaystyle m_{B}=m_{B}(y,r)}, which they send to the referee. The referee knows ( x , y ) {\displaystyle (x,y)}. A CDS protocol consists of the encoding maps applied by Alice and Bob.
A protocol is said to be ϵ {\displaystyle \epsilon }-correct if, for all ( x , y ) ∈ f − 1 ( 1 ) {\displaystyle (x,y)\in f^{-1}(1)}, the referee can determine z {\displaystyle z} with probability 1 − ϵ {\displaystyle 1-\epsilon }.
A protocol is said to be δ {\displaystyle \delta }-secure if, for all ( x , y ) ∈ f − 1 ( 0 ) {\displaystyle (x,y)\in f^{-1}(0)} the distribution of the messages is δ {\displaystyle \delta } close to a simulator distribution (in total variation distance), where the simulator distribution is independent of z {\displaystyle 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, C D S ϵ , δ ( f ) {\displaystyle CDS_{\epsilon ,\delta }(f)} is the minimal communication cost of an ϵ {\displaystyle \epsilon }-correct, δ {\displaystyle \delta } secure protocol that implements f {\displaystyle 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 ϵ {\displaystyle \epsilon }-correct and δ {\displaystyle \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 − Ω ( k ) {\displaystyle 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 {\displaystyle k}, while simultaneously reducing the correctness and privacy errors as above. The proof involves first encoding the secret z {\displaystyle 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 {\displaystyle f} is known, then certain simple modifications of f {\displaystyle f} have CDS protocols with similar efficiency.
The simplest case is to consider a CDS protocol for function f {\displaystyle f} and ask for a similarly efficient protocol for the negation of f {\displaystyle f}, labelled ¬ f {\displaystyle \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 ρ {\displaystyle \rho } bits, communication complexity of t {\displaystyle t} bits, and privacy and correctness errors δ = ϵ = 2 − k {\displaystyle \delta =\epsilon =2^{-k}}. Then ¬ f {\displaystyle \neg f} has a CDS scheme with similar privacy and correctness errors, and randomness and communication complexity of O ( k 3 ρ 2 t + k 3 ρ 3 ) {\displaystyle 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 {\displaystyle f_{1}} and f 2 {\displaystyle f_{2}}. Then, the communication and randomness costs of f 1 ∧ f 2 {\displaystyle f_{1}\wedge f_{2}} as well as f 1 ∨ f 2 {\displaystyle f_{1}\vee f_{2}} are not much larger than the sum of the costs for f 1 {\displaystyle f_{1}} and f 2 {\displaystyle f_{2}}. See Applebaum et al. for a precise statement.
Upper and lower bounds on communication cost
Given a function f {\displaystyle f} we would like to understand the communication and randomness costs to implement f {\displaystyle 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 {\displaystyle s} into a set of shares S 1 , . . . , S n {\displaystyle S_{1},...,S_{n}}. Associated to any secret sharing scheme is an access structure, which consists of a set of authorized sets A = A 1 , . . . , A k {\displaystyle {\mathcal {A}}={A_{1},...,A_{k}}} with A i ⊆ { S 1 , . . . , S n } {\displaystyle A_{i}\subseteq \{S_{1},...,S_{n}\}}. The authorized sets are those subsets of the A i {\displaystyle 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 A : { 0 , 1 } n → { 0 , 1 } {\displaystyle f_{\mathcal {A}}:\{0,1\}^{n}\rightarrow \{0,1\}}. Each subset of the shares K [ x ] ⊂ { S 1 , . . . , S n } {\displaystyle K[x]\subset \{S_{1},...,S_{n}\}} is labelled by a string x ∈ { 0 , 1 } n {\displaystyle x\in \{0,1\}^{n}} such that x i = 1 {\displaystyle x_{i}=1} if and only if S i ∈ K {\displaystyle S_{i}\in K}. Then we define f A {\displaystyle f_{\mathcal {A}}} to be such that f A ( x ) = 1 {\displaystyle f_{\mathcal {A}}(x)=1} if and only if K [ x ] ∈ A {\displaystyle K[x]\in {\mathcal {A}}}. In words, the function f A {\displaystyle 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 A {\displaystyle {\mathcal {A}}} can be realized in a secret sharing scheme if and only if f A {\displaystyle 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 {\displaystyle S_{i}}. For monotone functions, there is an upper bound on the communication cost in CDS for any monotone function f {\displaystyle f} in terms of the size of any secret sharing scheme with access structure given by f {\displaystyle f},
C D S ϵ = 0 , δ = 0 ( f ) ≤ S h a r i n g S i z e ( f ) {\displaystyle 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 {\displaystyle f},
C D S ϵ = 0 , δ = 0 ( f ) ≤ S P k ( f ) {\displaystyle CDS_{\epsilon =0,\delta =0}(f)\leq SP_{k}(f)}
The class of problems with efficient (polynomial size) span program is the complexity class M o d k L {\displaystyle 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
∀ f , C D S ϵ = 0 , δ = 0 ( f ) ≤ 2 O ( n log n ) {\displaystyle \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 ) {\displaystyle (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
C D S ϵ = 0.1 , δ = 0.1 ( f ) ≥ Ω ( log ( R A → B ( f ) + R B → A ( f ) ) ) {\displaystyle CDS_{\epsilon =0.1,\delta =0.1}(f)\geq \Omega (\log(R_{A\rightarrow B}(f)+R_{B\rightarrow A}(f)))}
where R A → B ( f ) {\displaystyle R_{A\rightarrow B}(f)} is the communication complexity of computing f {\displaystyle 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 ) {\displaystyle (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 ) {\displaystyle 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 → B {\displaystyle 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 ϵ , δ > 0 {\displaystyle \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 {\displaystyle f}-routing is equivalent in a certain sense to quantum CDS: an f {\displaystyle f}-routing protocol for a function f {\displaystyle 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 {\displaystyle 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.