New Approaches to Practical Secure Two-Party Computation

Peter Sebastian Nordholt

Research output: Book/anthology/dissertation/reportPh.D. thesis

392 Downloads (Pure)

Abstract

We present two new approaches to maliciously secure two-party computation
with practical efficiency:
• First, we present the first maliciously secure two-party computation protocol
with practical efficiency based on the classic semi-honest protocol
given by Goldreich et al. at STOC 1987. Before now all practical protocols
with malicious security were based on Yao’s garbled circuits.
We report on an implementation of this protocol demonstrating its high
efficiency. For larger circuits it evaluates 20000 Boolean gates per second.
As an example, evaluating one oblivious AES encryption (around 34000
gates) takes 64 seconds, but when repeating the task 27 times it only
takes less than 3 seconds per instance.
• Second, we revisit the LEGO protocol of Nielsen and Orlandi presented
at TCC 2009. Their protocol demonstrated a more efficient technique to
get malicious security in secure two-party computation protocols based
on Yao’s garbled circuit. Namely, doing the cut-n-choose test on the gate
level instead of the circuit level. This idea speeds up the protocol by
a factor the logarithm of the size of the circuit to be evaluated. The
resulting protocol, however, was not considered practically efficient as it
relies on public-key operations for every gate of the circuit.
We demonstrate how to get rid of this dependency on public-key operations
by replacing them with inexpensive Minicrypt type primitives. The
resulting protocol maintains the LEGO protocols good asymptotic complexity,
hopefully yielding a protocol of high practical efficiency.
• As a bi-product of these two new protocols for secure two-party computations
we develop two new cryptographic tools of independent interest: for
the first protocol we give a highly practical OT-extension protocol that,
apart from a few OTs to bootstrap the construction, only needs 14 calls
to hash function for each OT. For the second protocol we develop a new
XOR-homomorphic commitment scheme based on OT.
Original languageEnglish
PublisherInstitut for Datalogi, Aarhus Universitet
Number of pages119
Publication statusPublished - 2013

Fingerprint

Dive into the research topics of 'New Approaches to Practical Secure Two-Party Computation'. Together they form a unique fingerprint.

Cite this