Paper 2022/798

One Hot Garbling

David Heath, Georgia Institute of Technology
Vladimir Kolesnikov, Georgia Institute of Technology

Garbled Circuit (GC) is the main practical 2PC technique, yet despite great interest in its performance, GC notoriously resists improvement. Essentially, we only know how to evaluate GC functions gate-by-gate using encrypted truth tables; given input labels, the GC evaluator decrypts the corresponding output label. Interactive protocols enjoy more sophisticated techniques. For example, we can expose to a party a (masked) private value. The party can then perform useful local computation and feed the resulting cleartext value back into the MPC. Such techniques are not known to work for GC. We show that it is, in fact, possible to improve GC efficiency, while keeping its round complexity, by exposing masked private values to the evaluator. Our improvements use garbled one-hot encodings of values. By using this encoding we improve a number of interesting functions, e.g., matrix multiplication, integer multiplication, field element multiplication, field inverses and AES S-Boxes, integer exponents, and more. We systematize our approach by providing a framework for designing such GC modules. Our constructions are concretely efficient. E.g., we improve binary matrix multiplication inside GC by more than $6\times$ in terms of communication and by more than $4\times$ in terms of WAN wall-clock time. Our improvement circumvents an important GC lower bound and may open GC to further improvement.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. CCS 2021
Secure 2PC Garbled Circuits
Contact author(s)
heath davidanthony @ gatech edu
kolesnikov @ gatech edu
2022-06-21: approved
2022-06-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Heath and Vladimir Kolesnikov},
      title = {One Hot Garbling},
      howpublished = {Cryptology ePrint Archive, Paper 2022/798},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.