Paper 2018/395
Secure Computation with Constant Communication Overhead using Multiplication Embeddings
Alexander R. Block, Hemanta K. Maji, and Hai H. Nguyen
Abstract
Secure multiparty computation (MPC) allows mutually distrusting parties to compute securely over their private data. The hardness of MPC, essentially, lies in performing secure multiplications over suitable algebras. Parties use diverse cryptographic resources, like computational hardness assumptions or physical resources, to securely compute these multiplications. There are several cryptographic resources that help securely compute one multiplication over a large finite field, say $\mathbb{G}\mathbb{F}[2^n]$, with linear communication complexity. For example, the computational hardness assumption like noisy ReedSolomon codewords are pseudorandom. However, it is not known if we can securely compute, say, a linear number of ANDgates from such resources, i.e., a linear number of multiplications over the base field $\mathbb{G}\mathbb{F}[2]$. Before our work, we could only perform $o(n)$ secure ANDevaluations. This example highlights the general inefficiency of multiplying over the base field using one multiplication over the extension field. Our objective is to remove this hurdle and enable secure computation of boolean circuits while incurring a constant communication overhead based on more diverse cryptographic resources. Technically, we construct a perfectly secure protocol that realizes a linear number of multiplication gates over the base field using one multiplication gate over a degree$n$ extension field. This construction relies on the toolkit provided by algebraic function fields. Using this construction, we obtain the following results. If we can perform one multiplication over $\mathbb{G}\mathbb{F}[2^n]$ with linear communication using a particular cryptographic resource, then we can also evaluate linearsize boolean circuits with linear communication using the same cryptographic resource. In particular, we provide the first construction that computes a linear number of oblivious transfers with linear communication complexity from the computational hardness assumptions like noisy ReedSolomon codewords are pseudorandom, or arithmeticanalogues of LPNstyle assumptions. Next, we highlight the potential of our result for other applications to MPC by constructing the first correlation extractor that has $1/2$ resilience and produces a linear number of oblivious transfers.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. MINOR revision.INDOCRYPT 2018
 DOI
 10.1007/9783030053789_20
 Contact author(s)
 block9 @ purdue edu
 History
 20181210: last of 4 revisions
 20180501: received
 See all versions
 Short URL
 https://ia.cr/2018/395
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/395, author = {Alexander R. Block and Hemanta K. Maji and Hai H. Nguyen}, title = {Secure Computation with Constant Communication Overhead using Multiplication Embeddings}, howpublished = {Cryptology ePrint Archive, Paper 2018/395}, year = {2018}, doi = {10.1007/9783030053789_20}, note = {\url{https://eprint.iacr.org/2018/395}}, url = {https://eprint.iacr.org/2018/395} }