**Adaptively Secure Garbling Schemes for Parallel Computations**

*Kai-Min Chung; Luowen Qian*

**Abstract: **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.

**Category / Keywords: **public-key cryptography / garbling schemes, parallel cryptography, adaptive security, garbled circuit

**Original Publication**** (with major differences): **IACR-TCC-2019

**Date: **received 20 Sep 2019, last revised 4 Oct 2019

**Contact author: **luowenq at bu edu,kmchung@iis sinica edu tw

**Available format(s): **PDF | BibTeX Citation

**Note: **This is the full version of the paper.

**Version: **20191004:202421 (All versions of this report)

**Short URL: **ia.cr/2019/1077

[ Cryptology ePrint archive ]