Tri-State Circuits: A Better Model of Computation for Garbling

ePrint Report: Tri-State Circuits: A Better Model of Computation for Garbling

David Heath, Vladimir Kolesnikov, Rafail Ostrovsky

We introduce and formalize 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 the sense 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 …

computation eprint report fan fire knowledge model of computation power report simple state types vladimir wire