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.

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2018
Contact author(s)
akshayaram @ berkeley edu
History
Short URL
https://ia.cr/2018/151

CC BY

BibTeX

@misc{cryptoeprint:2018/151,
author = {Sanjam Garg and Akshayaram Srinivasan},
title = {Adaptively Secure Garbling with Near Optimal Online Complexity},
howpublished = {Cryptology ePrint Archive, Paper 2018/151},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/151}},
url = {https://eprint.iacr.org/2018/151}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.