Paper 2023/455
TriState Circuits: A Circuit Model that Captures RAM
Abstract
We introduce tristate 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 fanin 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 pergate cost essentially unchanged. As an important application, we construct authenticated Garbled RAM (GRAM), enabling constantround maliciouslysecure 2PC of RAM programs. Let $\lambda$ denote the security parameter. We extend authenticated garbling to TSCs; by simply plugging in our TSCbased 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 semihonest GRAM. We also give semihonest garbling of TSCs from a oneway function (OWF). This yields OWFbased GRAM at cost $O(T \cdot \log^3 T \cdot \log \log T \cdot \lambda)$, outperforming the best prior OWFbased GRAM by more than factor $\lambda$.
Note: The main difference between this version and prior versions is a reformulation of tristate semantics (Definition 1 and Figure 1). This new definition is more general, and it makes clear that tristate gates may fire in *any* order. Additionally, the revision cleans up several explanations and addresses several small typos.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A minor revision of an IACR publication in CRYPTO 2023
 Keywords
 Models of ComputationRandom Access MachinesCircuitsOblivious ComputationMPCGarbled RAM.
 Contact author(s)

daheath @ illinois edu
kolesnikov @ gatech edu
rafail @ cs ucla edu  History
 20230924: last of 3 revisions
 20230329: received
 See all versions
 Short URL
 https://ia.cr/2023/455
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/455, author = {David Heath and Vladimir Kolesnikov and Rafail Ostrovsky}, title = {TriState Circuits: A Circuit Model that Captures RAM}, howpublished = {Cryptology ePrint Archive, Paper 2023/455}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/455}}, url = {https://eprint.iacr.org/2023/455} }