| Popis: |
We present two new approaches to maliciously secure two-party computationwith practical efficiency:• First, we present the first maliciously secure two-party computation protocolwith practical efficiency based on the classic semi-honest protocolgiven by Goldreich et al. at STOC 1987. Before now all practical protocolswith malicious security were based on Yao’s garbled circuits.We report on an implementation of this protocol demonstrating its highefficiency. For larger circuits it evaluates 20000 Boolean gates per second.As an example, evaluating one oblivious AES encryption (around 34000gates) takes 64 seconds, but when repeating the task 27 times it onlytakes less than 3 seconds per instance.• Second, we revisit the LEGO protocol of Nielsen and Orlandi presentedat TCC 2009. Their protocol demonstrated a more efficient technique toget malicious security in secure two-party computation protocols basedon Yao’s garbled circuit. Namely, doing the cut-n-choose test on the gatelevel instead of the circuit level. This idea speeds up the protocol bya factor the logarithm of the size of the circuit to be evaluated. Theresulting protocol, however, was not considered practically efficient as itrelies on public-key operations for every gate of the circuit.We demonstrate how to get rid of this dependency on public-key operationsby replacing them with inexpensive Minicrypt type primitives. Theresulting 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 computationswe develop two new cryptographic tools of independent interest: forthe first protocol we give a highly practical OT-extension protocol that,apart from a few OTs to bootstrap the construction, only needs 14 callsto hash function for each OT. For the second protocol we develop a newXOR-homomorphic commitment scheme based on OT. We present two new approaches to maliciously secure two-party computationwith practical efficiency:• First, we present the first maliciously secure two-party computation protocolwith practical efficiency based on the classic semi-honest protocolgiven by Goldreich et al. at STOC 1987. Before now all practical protocolswith malicious security were based on Yao’s garbled circuits.We report on an implementation of this protocol demonstrating its highefficiency. For larger circuits it evaluates 20000 Boolean gates per second.As an example, evaluating one oblivious AES encryption (around 34000gates) takes 64 seconds, but when repeating the task 27 times it onlytakes less than 3 seconds per instance.• Second, we revisit the LEGO protocol of Nielsen and Orlandi presentedat TCC 2009. Their protocol demonstrated a more efficient technique toget malicious security in secure two-party computation protocols basedon Yao’s garbled circuit. Namely, doing the cut-n-choose test on the gatelevel instead of the circuit level. This idea speeds up the protocol bya factor the logarithm of the size of the circuit to be evaluated. Theresulting protocol, however, was not considered practically efficient as itrelies on public-key operations for every gate of the circuit.We demonstrate how to get rid of this dependency on public-key operationsby replacing them with inexpensive Minicrypt type primitives. Theresulting 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 computationswe develop two new cryptographic tools of independent interest: forthe first protocol we give a highly practical OT-extension protocol that,apart from a few OTs to bootstrap the construction, only needs 14 callsto hash function for each OT. For the second protocol we develop a newXOR-homomorphic commitment scheme based on OT. |
