Adaptively Secure Garbling with Near Optimal Online Complexity
Adaptively Secure Garbling with Near Optimal Online Complexity
复制标题
具有近乎最佳在线复杂性的自适应安全乱码
DOI：
10.1007/978-3-319-78375-8_18
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Akshayaram Srinivasan
中科院分区：
文献类型：
--
作者：
Sanjam Garg;Akshayaram Srinivasan
构造了一个在线通信复杂度为(n+m+mathsf{pol}(\log|C|，\lambda))的自适应安全置乱方案，其中C：0，1^n\right tarrow(0，1^m)是被置乱的电路，而lambda是安全参数。我们方案的安全性可以基于计算Diffie-Hellman(CDH)假设、因式分解假设或有错误学习假设(多项式难度)。这几乎是标准模型(即没有随机预言)下所能达到的最好结果，因为在线通信的复杂度必须大于n和m。该方案的在线计算复杂度为\(O(n+m)+\mathsf{poly}(\log|C|，\lambda)\)。以前已知的标准模型自适应安全乱码方案具有渐近更差的在线成本或依赖于指数级困难的计算假设。
We construct an adaptively secure garbling scheme with an online communication complexity of \(n+m+\mathsf {poly}(\log |C|, \lambda )\) where \(C: \{0,1\}^n \rightarrow \{0,1\}^{m}\) is the circuit being garbled, and \(\lambda \) is the security parameter. The security of our scheme can be based on (polynomial hardness of) the Computational Diffie-Hellman (CDH) assumption, or the Factoring assumption or the Learning with Errors assumption. This is nearly the best achievable in the standard model (i.e., without random oracles) as the online communication complexity must be larger than both n and m. The online computational complexity of our scheme is \(O(n+m)+\mathsf {poly}(\log |C|, \lambda )\). Previously known standard model adaptively secure garbling schemes had asymptotically worse online cost or relied on exponentially hard computational assumptions.
黑盒乱码RAM
DOI：
--
发表时间：
2015
期刊：
Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Garg, Sanjam;Lu, Steve;Ostrovsky, Rafail
通讯作者：
Ostrovsky, Rafail