问布尔电路和算术电路的局限性
EN

Cryptography用户

提问于 2019-08-15 15:26:26

回答 1查看 252关注 0票数 7

现代密码学的大部分都是基于布尔或算术电路的工作。例如，在多方计算中，“著名”结果允许对任何可以表示为布尔或算术电路的函数进行安全计算。

我想知道这些电路的极限是什么，有哪些函数是我们无法安全计算的--也就是说，哪些函数不能用布尔或算术电路来表示？在现实世界中，这是降低了现代密码学的有效性，还是这些电路足以实现我们所需的一切？

发布于 2019-08-15 16:39:00

问题应该是我们可以建立一个小电路来解决哪些功能。任何将固定位数映射到固定输出的函数都可以表示为布尔电路。但它可能很大。这带来了一个几乎没有下限的难题：https://en.m.wikipedia.org/wiki/Circuit_复杂性

票数 1

页面原文内容由Cryptography提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://crypto.stackexchange.com/questions/72618

复制

相似问题

问布尔电路和算术电路的局限性EN