如何比较算术电路中的两个场元？
给定两个场元作为算术电路的输入(只包括加法门和乘法门)，我如何输出较大的一个？或者，如何放置门以区分哪个更大(使用算术电路)？请你描述一下图片中的方法好吗？
在零知识证明中，需要证明的语句首先以标准形式描述，如布尔电路/算术电路/ R1CS。一般的证明方案可以处理任何类型的语句，从而使任何类型的函数都可以通过算术电路来传递。那么，如果布尔电路能够实现比较功能，我认为算术电路一定能够做到同样的事情。大多数在线材料看起来像是“您可以轻松地将任何语句编译成R1CS”。但是，当谈到实现一个功能的具体方法(我的意思是，如何在一个电路中放置门)时，很少有人在互联网上讨论。搜索引擎的大部分结果是“全加器”、"xor门“、”zk-SNARKs介绍“、"verilog”、“电路复杂度”等，这是不够有用的。
我知道比较可以很容易地在布尔电路上实现，但是我仍然需要在算术电路上实现它，它包括加法门和乘法门。我曾经认为这是一个容易的目标，但我发现我可能低估了它的难度。我的同学告诉我，“这样的算术电路会非常复杂”，但即便如此，我仍然想知道它会有多复杂(具体而言)。还有一个关于StackExchange的问答(布尔电路与算术电路)，它引入了一种在算术电路上模拟布尔门的方法，我认为这将对我有所帮助。然而，我无法核实它的有效性。例如，2和5= 0010和0101 = 0000，但根据QA，结果将是2·5=10 (1010)。
我想用算术电路(只是电路，不需要零知识)来实现上面描述的比较函数，你能教我如何放置加法门和乘法门吗？如果它是一个非常复杂的电路，如何分析有多少个门就足够了？
回答 1
Cryptography用户
发布于 2023-03-10 09:23:47
你误解了我的答案，这里。当将布尔电路转换为等效算术电路时，您需要
(1)将输入放在字段上并将其转换为位字符串(例如，如果使用素数顺序字段，则通过它们的整数表示)。
(2)将每个位单独编码为字段的0或1元素。
(3)利用算术运算对标准布尔基\{\mathsf{not}, \wedge, \oplus\}进行仿真。具体而言：
- x \oplus y = x + y - 2x\cdot y，
其中-, +,\cdot是字段上的子字符串、加法和积。在这里，操作只在单个位x和y (编码为0元素或字段的1元素)上执行。
回到您的问题:不可能编写一个直接将两个字段元素作为输入并输出比较结果的算术电路(这是不可能的结果，尽管我现在还没有指针)。
编辑:更准确地说，这是可能的，但只适用于小字段上的算术电路。具体来说，电路的大小可能会以一个与场大小|\mathbb{F}|成正比的因子爆炸，当我们使用指数大小的场时，这个因子就会变成指数级的大。
如果您想在\log|\mathbb{F}|中使用多项式，首先需要对字段元素(表示)进行位分解，并将表示的各个位输入到算术电路中。然后，算术电路可以模拟您选择的任意布尔电路，例如比较，只需\mathsf{poly}(\log|\mathbb{F}|)减速即可。
https://crypto.stackexchange.com/questions/105586
复制相似问题
腾讯云开发者
