布尔电路与算术电路

#1 楼

布尔电路和算术电路是表示计算的两种不同方式。主要区别在于它们的输入类型及其门类型：布尔电路在位输入上工作，而电路的门对应于布尔运算（例如XOR，AND）。另一方面，算术电路在作为某些字段$ \ mathbb {F} $的元素的输入上工作，并且电路的门对应于算术运算，id est，场运算（例如加法和乘法）。可以通过多项式大小的布尔电路计算的函数类别与可以通过多项式大小的算术电路计算的函数类别一致。确实，人们总是可以使用字段元素的某种表示形式，并将字段操作转换为布尔操作（字段元素的长度具有爆炸式多项式）。相反，通过将$ 0 $解释为对$ \ mathbb {F} $的加法，将$ 1 $解释为对$ \ mathbb {F} $的相乘的中立，并进行翻译，始终可以将布尔电路转换为算术电路算术运算的布尔门（例如$ a \ phantom {i} \ mathsf {OR} \ phantom {i} b $变为$ a + b-a * b $）。

在特定应用中确定布尔电路是否比算术电路更好取决于您要执行的计算类型。在密码学中，依靠计算现场元素是很常见的，并且我们拥有加密工具，可以让我们以原子方式操纵字段元素，尤其是将给定的字段元素视为单个输入（而不是作为单个输入）。位字符串）。在这种情况下，用算术电路表示计算是有意义的。但是，例如安全计算的许多应用程序都涉及非算术运算（例如，整数比较，这是许多计算中的基本过程）。在这种情况下，将这种非算术运算实现为算术运算效率会非常低下，布尔电路是更自然的表示。布尔电路到任意字段；布尔电路对应于域$ \ mathbb {F} _2 $上的算术电路。已经有许多论文致力于将加密方法扩展为以布尔电路表示的计算效果最佳，并将其设置为最好由算术电路捕获的计算设置，以提高这些电路的效率（例如，姚明的乱码方法已扩展为错误的算术电路），或在适用于布尔电路的方法与适合算术电路的方法之间架桥，以捕获其最佳表示形式是两者之间的混合表现的计算。
>

我正在寻找建立以下结果的参考：“可以通过多项式大小的布尔电路计算的函数类别与可以通过多项式大小的算术电路计算的函数类别一致”。您可以提供参考书或科学论文吗？我的搜索没有成功...


正如我在评论中提到的那样，您可能找不到参考文献，因为结果是民间传说。固定一个任意字段$（\ mathbb {F}，+，\ cdot）$并考虑一个函数$ f $，该函数可以由大小为多项式的布尔电路在其输入大小上计算，例如，在标准基础$ \ { \ mathsf {XOR}，\ mathsf {AND}，\ mathsf {NOT} \} $。要在$ \ mathbb {F} $上模拟计算，请将$ 0 $编码为$ 0_ \ mathbb {F} $（在$ \ mathbb {F} $中加法的中性），将$ 1 $编码为$ 1_ \ mathbb {F} $（乘法的中性）。布尔门可以模拟如下：


要计算输入$（x，y）$的$ \ mathsf {AND} $门，返回$ x \ cdot y $

要计算输入$（x，y）$的$ \ mathsf {XOR} $门，返回$ x + y-2 \ cdot x \ cdot y $

要计算输入$ x $的$ \ mathsf {NOT} $门，请返回$ 1_ \ mathbb {F} -x $。

我将让您检查一下它是否正确模拟了布尔运算。由于仿真每个布尔门最多需要4个算术运算，因此只要布尔电路为多项式大小，在$ \ mathbb {F} $上模拟布尔电路的算术电路就是多项式大小的。相反的方向是微不足道的，因为布尔电路只是$ \ mathbb {F} _2 $之上的算术电路。

为了通用起见，我补充说，您通常可以在使用布尔电路的任意字段$ \ mathbb {F} $；确实，这就是您的计算机每天在做的事情：修复字段$ \ mathbb {F} $，并考虑$ \ mathbb {F} $的任何元素$ x $的二进制分解：$ x = \ sum_ {i = 0} ^ {\\ lceil \ log | \ mathbb {F} || \ rceil-1} b_i \ cdot 2 ^ i $，在$ {0_ \ mathbb {F}，1_ \ mathbb {F} \} $中有$ b_i \。


要模拟$ \ mathbb {F} $上的加法，使用教科书二进制加法，该方法只需观察$ \ mathsf {XOR} $给出$ i $ th个值，而$ \ mathsf {AND} $给您$ i $ th个进位。
要模拟$ \ mathbb {F} $上的乘法，请使用教科书乘法算法，该算法仅依赖于$ \ mathsf {AND} $门和字段加法，我们已经证明了可以模拟。

总的来说，大小的增加由教科书二进制乘法的$ O（\ log ^ 2 | \ mathbb {F} |）$成本决定。