Tri-State Circuits - A Circuit Model that Captures RAM
Tri-State Circuits - A Circuit Model that Captures RAM
复制标题
DOI：
10.1007/978-3-031-38551-3_5
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
David Heath;V. Kolesnikov;R. Ostrovsky
中科院分区：
文献类型：
--
作者：
David Heath;V. Kolesnikov;R. Ostrovsky
我们介绍三态电路(TSC)。TSC形成了一种自然的计算模型，据我们所知，理论家还没有考虑过这种模型。该模型捕捉到了简单和强大的令人惊讶的结合。TSC很简单，因为它们只允许三个线路值(0、1和未定义-)和三种类型的扇入两个门；它们的强大之处在于，当它们的输入定义时，它们的静态放置的门会急切地触发(执行)，这意味着取决于输入的执行顺序。这种行为足以有效地评估RAM程序。我们构造了一个TSC，它模拟任何RAM程序的步骤，并且只有门。这与从RAM到布尔电路的减少形成了对比，在布尔电路中，最佳方法在每次访问时扫描所有内存，从而产生二次成本。我们将TSC与乱码电路(GC)连接起来。TSCS比布尔电路更好地捕捉了乱码的能力，提供了一个更具表现力的计算模型，每个门的成本基本上保持不变。作为一个重要的应用，我们构造了身份验证的GarbledRAM(GRAM)，使恒定循环恶意安全的2PC RAM程序成为可能。让我们表示安全参数。我们将认证乱码扩展到TSC，通过简单地插入基于TSC的RAM，我们获得了以成本运行的认证GRAM，其性能优于以往的所有工作，包括先前的半诚实GRAM。我们还从单向函数(OWF)给出了TSC的半诚实乱码。这产生了基于OWF的GRAM的成本，表现优于之前最好的基于OWF的GRAM。
We introducetri-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 –) 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 emulatesTsteps of any RAM program and that has onlygates. 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 Garbled Circuits (GC). 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 constructauthenticated GarbledRAM (GRAM), enabling constant-round maliciously-secure 2PC of RAM programs. Letdenote the security parameter. We extend authenticated garbling to TSCs; by simply plugging in our TSC-based RAM, we obtain authenticated GRAM running at cost, 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, outperforming the best prior OWF-based GRAM by more than factor.