Paper 2023/455

Tri-State Circuits: A Circuit Model that Captures RAM

David Heath, University of Illinois Urbana-Champaign
Vladimir Kolesnikov, Georgia Institute of Technology
Rafail Ostrovsky, University of California, Los Angeles

We introduce tri-state circuits (TSCs). TSCs form a natural model of computation that, to our knowledge, has not been considered by theorists. The model captures a surprising combination of simplicity and power. TSCs are simple in that they allow only three wire values ($0,1,$ and undefined - $\mathcal{Z}$) and three types of fan-in two gates; they are powerful in that their statically placed gates fire (execute) eagerly as their inputs become defined, implying orders of execution that depend on input. This behavior is sufficient to efficiently evaluate RAM programs. We construct a TSC that emulates $T$ steps of any RAM program and that has only $O(T \cdot \log^3 T \cdot \log \log T)$ gates. Contrast this with the reduction from RAM to Boolean circuits, where the best approach scans all of memory on each access, incurring quadratic cost. We connect TSCs with cryptography by using them to improve Yao's Garbled Circuit (GC) technique. TSCs capture the power of garbling far better than Boolean Circuits, offering a more expressive model of computation that leaves per-gate cost essentially unchanged. As an important application, we construct authenticated Garbled RAM (GRAM), enabling constant-round maliciously-secure 2PC of RAM programs. Let $\lambda$ denote the security parameter. We extend authenticated garbling to TSCs; by simply plugging in our TSC-based RAM, we obtain authenticated GRAM running at cost $O(T \cdot \log^3 T \cdot \log \log T \cdot \lambda)$, outperforming all prior work, including prior semi-honest GRAM. We also give semi-honest garbling of TSCs from a one-way function (OWF). This yields OWF-based GRAM at cost $O(T \cdot \log^3 T \cdot \log \log T \cdot \lambda)$, outperforming the best prior OWF-based GRAM by more than factor $\lambda$.

Note: The main difference between this version and prior versions is a reformulation of tri-state semantics (Definition 1 and Figure 1). This new definition is more general, and it makes clear that tri-state gates may fire in *any* order. Additionally, the revision cleans up several explanations and addresses several small typos.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2023
Models of ComputationRandom Access MachinesCircuitsOblivious ComputationMPCGarbled RAM.
Contact author(s)
daheath @ illinois edu
kolesnikov @ gatech edu
rafail @ cs ucla edu
2023-09-24: last of 3 revisions
2023-03-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Heath and Vladimir Kolesnikov and Rafail Ostrovsky},
      title = {Tri-State Circuits: A Circuit Model that Captures RAM},
      howpublished = {Cryptology ePrint Archive, Paper 2023/455},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.