通用电路是一种用来模拟任意规模小于n的电路的可编程电路,和普通的逻辑电路不同,通用电路在得到输入x前,需要指定其模拟的电路C。除输入x外,还将用于编码C的控制位p_C作为输入的,而通用电路最终的输出需要保证正确性:UC(x,p_C)=C(x)。通用电路最开始由由Valiant在1976年提出,与此同时,Valiant也给出了相应的构造,并证明这一构造在渐进意义上是最优(O(n log n))。现如今,通用电路已被运用到了和密码学有关的很多领域中,例如安全的多方计算,隐藏函数求值和全同态加密等。尽管前人已经做了很多工作来优和改进小规模通用电路的效率。但对于大规模电路而言,最好的通用电路构造依旧是Valiant在四十多年前给出的。在这篇论文中,我们回顾了Valiant框架。为了实现这一构造构造,Valiant将电路建模为一张有向无环图,图中的点表示电路中的门,图中的边表示电路中的线,从而进一步引入了边通用图(EUG)的定义。简单地说,利用通用电路来模拟电路就如同寻找边通用图到有向无环图的边嵌入。而其中的超结点就是Valiant框架中的核心模块,可以用来递归的构造边通用图。在Valiant框架下,很多前人的工作都对其进行了改进以提升通用电路的效率(主要是小规模通用电路)。但随着计算机技术日益成熟,算法日益进步,现实生活对大规模电路的需求的日益提升,所以我们对大规模通用电路的效率提出了新的需求。作为我们的主要贡献之一,我们提出了一种改进的超结点的构造(如上所述,超结点是一种用来构造通用电路的核心基础模块)。基于此超结点结构,我们可以构造出新的通用电路,其平均规模比Valiant的最优构造还要小5%。且我们的优化对于任何规模的电路都有效,并不局限于规模较小的电路。同时,从成完备性的角度考虑,我们还找到了Valiant框架下通用电路规模的一个下界,从而大大缩小了通用电路领域理论与实际之间的距离。