Cryptology ePrint Archive: Report 2018/151

Adaptively Secure Garbling with Near Optimal Online Complexity

Sanjam Garg and 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.

Category / Keywords:

Original Publication (with minor differences): IACR-EUROCRYPT-2018

Date: received 7 Feb 2018, last revised 7 Feb 2018

Contact author: akshayaram at berkeley edu

Available format(s): PDF | BibTeX Citation

Version: 20180211:142921 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]