宇宙是什么样子的？通用电路的复杂度(大小/深度)是多少？

Question

我正在读一个关于基于属性的加密的纸。作者证明，密文策略安倍可以利用通用电路由密钥策略安倍构造.但是通用电路应该在CP支持的电路空间中.那么，通用电路的复杂性是什么呢？

Answer 1

据我所知，优化通用电路效率的最新进展是本论文。在较高的水平上，一个通用的电路来评估任何尺寸-s电路有尺寸O(s\cdot \log s)，我想深度应该大致相似(O(s\cdot \log s))，因为在最坏的情况下，size-s电路可以有深度-s，而且我们不知道一般的技术来减小电路的深度，同时只增加一个对数因子。