secret sharing with 3 parties under constraint

Question

Suppose we have $3$ parties Alice, Bob and Charlie such that Alice can't talk with Bob.

Suppose that Alice has some string $x\in\{0,1\}^n$ and Bob has a string $y\in\{0,1\}^n$.

Suppose that Alice and Bob have access to a shared random string $r$ and a shared secret $s$.

Suppose that Charlie knows both $x$ and $y$ and he doesn't have access to $r$.

Describe a protocol in which Alice sends one message to Charlie (it may depend on $x,r,s$) and simultaneously Bob sends one message to Charlie (it may depend on $y,r,s$). Afterwards, if $x=y$ Charlie will know $s$ and if $x\neq y$ Charlie will not be able to know $s$.

The general context of this problem is secret sharing, e.g. Shamir's secret sharing and so on.

I have a proposition for solution to the inverse version of this question, i.e. if $x\neq y$ Charlie will know $s$ and if $x=y$ Charlie will not be able to know $s$:

My proposition is to think of $x,y,r$ as members of the field $\mathbb{Z}_{2^n}$.

Alice computes $s+rx$ and sends it to Charlie.

Bob computes $s+ry$ and sends it to Charlie.

If $x\neq y$ Charlie can interpolate to get $s$, otherwise $x=y$ and Charlie only saw some random element of $\mathbb{Z}_{2^n}$: $s+rx=s+ry$, so he can not recover $s$.

But this is not the original question and I don't know what to do with the original.

Can we generalize it to some boolean function $f:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}$, i.e. only if $f(x,y)=1$ Charlie will be able to recover $s$?

Answer 1

This problem is known as conditional disclosure of secret in cryptography. There have been many nice recent works on the subject, I suggest having a quick look at this one for example.

In you exact scenario, can $r$ be of length $2n$? If so, here is a simple solution: call $(r_0,r_1)$ the left and right parts of $r$, each of length $n$.

• Alice sends $s + r_0x - r_1$
• Bob sends $r_1-r_0y$

Because of the mask $r_1$, these two values only leak $(s + r_0x - r_1) + (r_1-r_0y) = s + r_0(x-y)$. If $x=y$, this discloses $s$; otherwise, $r_0(x-y)$ perfectly hides $s$ (addition and multiplications are performed over $\mathbb{F}_{2^n}$).

Regarding your second questions, yes, there are results on conditional disclosure of secret for arbitrary functions. The best result we know of for arbitrary predicate $f:[N]\times[N] \mapsto \{0,1\}$ has communication $2^{O(\sqrt{\log N \log\log N})}$. For predicates represented by a boolean circuit, I think we can have communication linear in the circuit size, but I would need to check this.