3
$\begingroup$

Recently, I was reading the paper One Hot Garbling published on CCS 2021. I noticed a sentence in it:

In this work, we forgo the standard GC notation of garbled labels in favor of garbled sharings of cleartext values held by G and E. This will be convenient for handling vectors and matrices of bits.

I don't understand what garbled sharing is, how to construct 2PC protocol through garbled sharing? what is the difference between garbled circuits and garbled sharing?

Thanks a lot!

$\endgroup$

1 Answer 1

3
$\begingroup$

In short, Garbled sharings are a matter of notation, nothing more.

In more detail, the notation is derived from the Free XOR Garbled Circuit (GC) extension.

In classic GC, the garbler uniformly samples two keys for each wire w: a key K_w^0 encoding logical zero, and a key K_w^1 encoding logical one.

Free XOR changes this. The garbler still samples key K_w^0, but instead of sampling K_w^1, the garbler samples a single global correlation Delta, and then for every wire, sets K_w^1 = K_w^0 XOR Delta. The upshot is that we can compute XOR “for free” by simply XORing keys together.

This new Free XOR encoding admits a new perspective, which we call a garbled sharing. Consider a wire w holding logical value x. At runtime, there are only two possibilities:

  1. The evaluator holds key K_w^0, corresponding to case x = 0.
  2. The evaluator holds key K_w^0 XOR Delta, corresponding to case x = 1.

In either case, the evaluator holds K_w^0 XOR x*Delta. Based on this observation, we can view the encoding of a particular wire as a kind of secret share: The garbler holds the zero key K_w^0, and the evaluator holds K_w^0 XOR x*Delta. I.e., the parties hold XOR shares of x*Delta.

In the paper, we write such a share of x simply as [x]. Moreover, we extend this notation so that we can also share vectors and matrices: the sharing of a bit matrix is a matrix of sharings of the individual bits. In other words, if M is an n*m bit matrix, I can simply write [M] to denote the fact that the garbler and the evaluator each hold n*m labels, each corresponding to the encoding of an individual cleartext bit.

This notation becomes handy once you want to start performing linear operations on garbled values, and performing such linear operations is at the core of the one-hot technique.

$\endgroup$
3
  • 1
    $\begingroup$ The garbled sharing perspective is not restricted to free XOR, isn't it? I've always looked at standard Yao garbling with keys $(K_0, K_1)$ and bit $b$ as distributing secret shares of $K\cdot b$, where the garbler share is $K_0$, the evaluator share is $K_b$, and $K = K_0 \oplus K_1$. $\endgroup$ Mar 23, 2023 at 14:32
  • $\begingroup$ This is true, it is of course also possible to view Yao garbling as being a sharing of some kind. However, the precise syntax used should be different, e.g. [x]_K to donate that x is shared under key K. Under Yao garbling, linear homomorphism (that we care about for this specific paper) does not hold unless the two added bits share the same key K (relevant citation). Free XOR admits a simpler notation for sharing because all bits are by construction shared under the same key Delta. $\endgroup$ Mar 24, 2023 at 15:39
  • $\begingroup$ Yes, I agree - I was just pinpointing that the key difference is that free XOR is best viewed as sharing x authenticated with a global MAC, while Yao uses a per-gate MAC. This view makes the delta (pun not intended) between the two results clearer, in my opinion: both use secret sharing, but the difference lies in global versus local MAC for authentication of the shared value. $\endgroup$ Mar 24, 2023 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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