Paper 2023/455
Tri-State Circuits: A Circuit Model that Captures RAM
Abstract
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 (
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.
Metadata
- Available format(s)
-
PDF
- 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
- 2023-09-24: last of 3 revisions
- 2023-03-29: 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 = {Tri-State Circuits: A Circuit Model that Captures {RAM}}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/455}, year = {2023}, url = {https://eprint.iacr.org/2023/455} }