Paper 2019/1077

Adaptively Secure Garbling Schemes for Parallel Computations

Kai-Min Chung and Luowen Qian


We construct the first adaptively secure garbling scheme based on standard public-key assumptions for garbling a circuit $C: \{0, 1\}^n \mapsto \{0, 1\}^m$ that simultaneously achieves a near-optimal online complexity $n + m + \textrm{poly}(\lambda, \log |C|)$ (where $\lambda$ is the security parameter) and \emph{preserves the parallel efficiency} for evaluating the garbled circuit; namely, if the depth of $C$ is $d$, then the garbled circuit can be evaluated in parallel time $d \cdot \textrm{poly}(\log|C|, \lambda)$. In particular, our construction improves over the recent seminal work of Garg et al. (Eurocrypt 2018), which constructs the first adaptively secure garbling scheme with a near-optimal online complexity under the same assumptions, but the garbled circuit can only be evaluated gate by gate in a sequential manner. Our construction combines their novel idea of linearization with several new ideas to achieve parallel efficiency without compromising online complexity. We take one step further to construct the first adaptively secure garbling scheme for parallel RAM (PRAM) programs under standard assumptions that preserves the parallel efficiency. Previous such constructions we are aware of is from strong assumptions like indistinguishability obfuscation. Our construction is based on the work of Garg et al. (Crypto 2018) for adaptively secure garbled RAM, but again introduces several new ideas to handle parallel RAM computation, which may be of independent interests. As an application, this yields the first constant round secure computation protocol for persistent PRAM programs in the malicious settings from standard assumptions.

Note: This is the full version of the paper.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in TCC 2019
garbling schemesparallel cryptographyadaptive securitygarbled circuit
Contact author(s)
luowenq @ bu edu
kmchung @ iis sinica edu tw
2019-10-04: last of 2 revisions
2019-09-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kai-Min Chung and Luowen Qian},
      title = {Adaptively Secure Garbling Schemes for Parallel Computations},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1077},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.