4
$\begingroup$

We know that secure multi-party computation (MPC) does not have to be implemented based solely on public-key cryptographic primitives (aka asymmetric-key primitives). Many MPC protocols rely on symmetric-key primitives, such as secret sharing-based schemes (e.g., replicated secret sharing and Shamir‘s secret sharing). However, I vaguely remember that in a paper about MPC, the author said that the MPC protocol essentially relies on asymmetric-key primitives. I was asked this question recently, and then I didn't find that paper, but I found the similar but not exactly the same statement in [IKM13]$^1$ and [DKR18]$^2$:

(Page 3 from [IKM13]) This, together with the fact that OT is complete for secure computation, shows that every functionality can be securely computed given access to an appropriate source of correlated randomness and no additional assumptions.

(Page 54 from [EKR18]) Oblivious Transfer(OT) is an essential building block for secure computation protocols, and an inherently asymmetric primitive. Impagliazzo and Rudich (1989) showed that a reduction from OT to a symmetric-key primitive (one-way functions, PRF) implies that P $\ne$ NP.

It is clear that OT is complete for secure computation and it is an inherently asymmetric primitive. I thought about secure two-party computation and thought that it does require asymmetric-key primitives. For example, considering secure two-party computation based on 2-out-of-2 additive secret sharing, secure two-party addition can be computed locally and secure two-party multiplication can be implemented by leveraging Beaver's triples. Beaver's triples can be generated via OT and homomorphic encryption (HE), which rely on the public-key encryption primitives.

Considering that secure two-party computation is naturally set in a dishonest majority environment, my question is "Must secure two-party computation be implemented based on public-key encryption primitives?" After reviewing the literature and searching online, my understanding of this issue is as follows:

(1)the (semi-honest/malicious) secure two-party computation primitive is naturally a public-key primitive, and the general secure two-party computation protocol will inevitably involve public-key primitives, such as OT and HE.

(2)but, secure two-party computing protocol for a specific functionality does not necessarily utilize the public-key primitives. Sometimes it can rely on private-key primitives.

I would like to know the answer to this question and if my understanding is correct?

Reference

  1. [IKM13]Ishai Y, Kushilevitz E, Meldgaard S, et al. On the power of correlated randomness in secure computation[C]//TCC 2013, 2013: 600-620.
  2. [EKR18]David Evans, Vladimir Kolesnikov and Mike Rosulek. A Pragmatic Introduction to Secure Multi-Party Computation.
$\endgroup$

1 Answer 1

5
$\begingroup$

Your understanding is essentially correct.

  • Secure computation of general functions with dishonest majority provably requires oblivious transfer (trivially, since OT is a special type of secure computation). OT is known to imply key exchange (the proof is an interesting exercise), hence OT is fundamentally a public-key primitive (and basing it on a symmetric assumption would be a huge breakthrough).

  • Secure computation of general functions with honest majority does not require any assumption. (the true picture is a bit more complicated than that depending on how we define "secure" exactly, but that's a reasonable way to summarize it). Note that Shamir's secret sharing is not a "symmetric key primitive" but rather an unconditional primitive (unlike e.g. hash functions, it does not require assuming any limitation on the adversarial power).

  • Some specific functions might not require public key primitives even in the dishonest majority setting. For example, the $n$-party XOR can be implemented with unconditional security with up to $n-1$ corruptions. There has been a bunch of work in the 90's characterizing more precisely what kind of functions can be securely evaluated with dishonest majority and unconditional security.

  • An important feature of oblivious transfer is that it can be extended. Concretely, that means that even if OT provably requires public key primitives, doing $N$ OTs does not require doing $N$ public key operations. That's an absolutely crucial feature of many modern secure computation protocols. It was shown a few decades ago here that given access to only $\lambda$ oblivious transfers (think $\lambda = 128$), one can extend them into an arbitrary number of oblivious transfers, using only symmetric key primitives (a sufficiently strong hash function -- in fact, even one-way functions suffice, though they yield a much less efficient extension). Hence, in essence, you can securely compute any function with dishonest majority using only $O(\lambda)$ public key operations, and only symmetric key operations on top of that.

A minor note on one of your citations: Impagliazzo and Rudich only showed that a black-box construction of OT (and other primitives) from symmetric assumptions would imply $\mathsf{P} \neq \mathsf{NP}$ (and some following works showed that black-box constructions of key exchange & OT from symmetric assumptions simply don't exist, unconditionally). We can't prove anything for arbitrary reductions (ruling out arbitrary reductions of OT to symmetric assumptions would imply that OT does not exist).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.