Cryptology ePrint Archive: Report 2018/372

Secure Computation using Leaky Correlations (Asymptotically Optimal Constructions)

Alexander R. Block and Divya Gupta and Hemanta K. Maji and Hai H. Nguyen

Abstract: Most secure computation protocols can be effortlessly adapted to offload a significant fraction of their computationally and cryptographically expensive components to an offline phase so that the parties can run a fast online phase and perform their intended computation securely. During this offline phase, parties generate private shares of a sample generated from a particular joint distribution, referred to as the correlation. These shares, however, are susceptible to leakage attacks by adversarial parties, which can compromise the security of the entire secure computation protocol. The objective, therefore, is to preserve the security of the honest party despite the leakage performed by the adversary on her share.

Prior solutions, starting with $n$-bit leaky shares, either used 4 messages or enabled the secure computation of only sub-linear size circuits. Our work presents the first 2-message secure computation protocol for 2-party functionalities that have $\Theta(n)$ circuit-size despite $\Theta(n)$-bits of leakage, a qualitatively optimal result. We compose a suitable 2-message secure computation protocol in parallel with our new 2-message correlation extractor. Correlation extractors, introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai (FOCS--2009) as a natural generalization of privacy amplification and randomness extraction, recover ``fresh'' correlations from the leaky ones, which are subsequently used by other cryptographic protocols. We construct the first 2-message correlation extractor that produces $\Theta(n)$-bit fresh correlations even after $\Theta(n)$-bit leakage.

Our principal technical contribution, which is of potential independent interest, is the construction of a family of multiplication-friendly linear secret sharing schemes that is simultaneously a family of small-bias distributions. We construct this family by randomly ``twisting then permuting'' appropriate Algebraic Geometry codes over constant-size fields.

Category / Keywords: Secure Computation, Correlation Extractors, Leakage Resilient Cryptography, Oblivious Transfer, Error Correcting Codes, Small Bias Distributions

Original Publication (with minor differences): IACR-TCC-2018

Date: received 24 Apr 2018, last revised 10 Dec 2018

Contact author: block9 at purdue edu

Available format(s): PDF | BibTeX Citation

Version: 20181210:192647 (All versions of this report)

Short URL: ia.cr/2018/372


[ Cryptology ePrint archive ]