Paper 2018/372

Secure Computation using Leaky Correlations (Asymptotically Optimal Constructions)

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


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.

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2018
Secure ComputationCorrelation ExtractorsLeakage Resilient CryptographyOblivious TransferError Correcting CodesSmall Bias Distributions
Contact author(s)
block9 @ purdue edu
2018-12-10: last of 4 revisions
2018-04-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexander R.  Block and Divya Gupta and Hemanta K.  Maji and Hai H.  Nguyen},
      title = {Secure Computation using Leaky Correlations (Asymptotically Optimal Constructions)},
      howpublished = {Cryptology ePrint Archive, Paper 2018/372},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.