Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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!
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:
K_w^0, corresponding to case x = 0.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.
[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 at 15:39