[Resource Topic] 2019/1077: Adaptively Secure Garbling Schemes for Parallel Computations

Welcome to the resource topic for 2019/1077

Title:
Adaptively Secure Garbling Schemes for Parallel Computations

Authors: 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.

ePrint: https://eprint.iacr.org/2019/1077

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .