如何确定电路的层次？
在许多密码应用中，如多方计算(MPC)或完全同态加密(FHE)，您可以考虑在某些代数结构(通常是字段)上由电路描述的函数f。
现在，非常典型的情况是，算法的复杂性在很大程度上取决于电路的深度，而不一定取决于电路的大小。例如，这种情况在基于格的FHE中是这样的，在这种情况下，需要低深度才能执行引导，或者在某些非恒定的圆形MPC协议中，轮数取决于电路的深度。
鉴于上述情况，我有两个问题。
- 给出一个f电路，我们如何优化得到相同f的“浅”电路？是否有任何可用于此目的的工具/算法？
- 假设f的电路作为一个门的列表给出，其中每个门指向与其输入相对应的一个或多个门。我们如何从这种表示法中确定电路的层次？对此也有什么工具/算法吗？
第二点特别适用于MPC，在MPC中，同一层中的门的通信可以并行化，提供了很大的改进。
谢谢!
回答 2
Cryptography用户
发布于 2018-09-30 22:29:16
在许多情况下，电路的深度直接关系到构建逻辑门的一致性，或者它所依赖的子协议的广泛性。考虑到一个协议的计算，以求任意大的一组n值的乘积，以及二进制乘法协议的存在，即两个输入和一个输出，电路的深度将需要一个深度\lceil \log_2 n \rceil乘法门的电路。在这种情况下，有一些代数方法可以将其转化为一个恒定的循环操作，但这在大多数情况下都是有益的，超过了n的某个阈值。一个结果说明了这种技术，特别是恒定轮，无限制扇形乘是巴，伊兰和海狸这里的工作。
Cryptography用户
发布于 2018-10-31 15:04:13
对于问题2，我怀疑这可能相当于一个拓扑排序算法，修改后可以跟踪门的“深度”(即层指数)。它可以在O(n + m)时间完成，其中n是门的数目，m是线的数目。
https://crypto.stackexchange.com/questions/62502
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号