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:
- The evaluator holds key
K_w^0, corresponding to case x = 0.
- 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.
