Paper 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.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in EUROCRYPT 2018
Contact author(s)
akshayaram @ berkeley edu
History
2018-02-11: received
Short URL
https://ia.cr/2018/151
License
Creative Commons Attribution
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.