4
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ I don't think you're using "dual" quite correctly. $\endgroup$ – Acccumulation Jan 2 '18 at 21:46
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.