Welcome to the resource topic for 2018/151
Title:
Adaptively Secure Garbling with Near Optimal Online Complexity
Authors: Sanjam Garg, Akshayaram Srinivasan
Abstract:We construct an adaptively secure garbling scheme with an online communication complexity of n+m+\mathsf{poly}(\log |C|, \sec) where C: \{0,1\}^n \rightarrow \{0,1\}^{m} is the circuit being garbled, and \sec 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|, \sec). Previously known standard model adaptively secure garbling schemes had asymptotically worse online cost or relied on exponentially hard computational assumptions.
ePrint: https://eprint.iacr.org/2018/151
Talk: https://www.youtube.com/watch?v=vJCAJFkZP5I
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .