Privacy-Free Garbled Circuits for Formulas: Size Zero and Information-Theoretic
Privacy-Free Garbled Circuits for Formulas: Size Zero and Information-Theoretic
复制标题
公式的无隐私乱码电路：零大小和信息理论
DOI：
10.1007/978-3-319-63688-7_7
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Patra
中科院分区：
文献类型：
--
作者：
Yashvanth Kondi;A. Patra
乱码电路在密码学中具有核心重要性，在安全计算、零知识（ZK）协议和可验证的计算外包等方面有着广泛的应用。我们感兴趣的是一种特殊的乱码方案，在文献中称为隐私自由。我们表明，布尔公式可以乱码信息理论上在隐私自由的设置，不产生密文。现有的乱码方案或者依赖于密码学假设（并且因此需要密码学操作来构造和评估乱码电路），产生非零大小的乱码电路，或者被限制为低深度公式化电路。我们的结果具有理论和实际意义的乱码电路作为一个原始的。在理论方面，我们的结果打破了已知的理论下限的一个密文乱码的与门在这种设置。作为一个有趣的含义，生产大小为零的乱码电路，我们的计划分数自适应安全免费。在实践方面，我们的乱码方案只涉及廉价的XOR运算，并产生大小为零的乱码电路。作为一个副作用，我们提出了几个有趣的扩展我们的计划。也就是说，我们展示了如何混淆阈值和高扇入门。
Garbled circuits are of central importance in cryptography, finding widespread application in secure computation, zero-knowledge (ZK) protocols, and verifiable outsourcing of computation to name a few. We are interested in a particular kind of garbling scheme, termed privacy-free in the literature. We show that Boolean formulas can be garbled information-theoretically in the privacy-free setting, producing no ciphertexts at all. Existing garbling schemes either rely on cryptographic assumptions (and thus require cryptographic operations to construct and evaluate garbled circuits), produce garbled circuits of non-zero size, or are restricted to low depth formulaic circuits. Our result has both theoretical and practical implications for garbled circuits as a primitive. On the theory front, our result breaks the known theoretical lower bound of one ciphertext for garbling an AND gate in this setting. As an interesting implication of producing size zero garbled circuits, our scheme scores adaptive security for free. On the practical side, our garbling scheme involves only cheap XOR operations and produces size zero garbled circuits. As a side result, we propose several interesting extensions of our scheme. Namely, we show how to garble threshold and high fan-in gates.