3
$\begingroup$

According to the Wikipedia article about SMPC:

Secure MPC is closely related and builds on to the problem of secret sharing, and more specifically verifiable secret sharing (VSS), which many secure MPC protocols use against active adversaries.

So, is there an SMPC scheme that doesn't use secret sharing? Are any in popular use?

Context: I'm not familiar with the literature on SMPC, and I've only studied it as an extension of secret sharing.

$\endgroup$
  • 2
    $\begingroup$ Secure two-party computation using garbled circuits does not rely on secret sharing. I suppose you are looking specifically for SMPC? $\endgroup$ – Occams_Trimmer May 18 at 13:05
  • $\begingroup$ Oh interesting! I didn't realize there would be different answers for 2 vs >2 parties. Are there any non-secret-sharing techniques for SMPC with >2 parties? $\endgroup$ – kennysong May 19 at 5:36
  • $\begingroup$ Not that I am aware of, but I don't really work on MPC. So, let's wait for other responses. $\endgroup$ – Occams_Trimmer May 19 at 14:20
3
$\begingroup$

Secret sharing captures a really wide set of techniques, and "not using secret sharing" is a bit ill-defined. Let me take an example: the seminal solution for two-party computation uses Yao's garbled circuits. It works as follows (very roughly):

The sender garbles the circuit of the target function, which gives the following guarantees: given an appropriate key for each bit of the input and the garbled circuit, the receiver can evaluate the full circuit without seeing anything but the end result.

The sender sends the key for each of his input bits, and the receiver uses oblivious transfer to retrieve the key for each of her own input bits, without revealing these input bits. Then, she evaluates the garbled circuit and sends the result back.

Unlike, say, GMW and it's variant, the above is not formulated in terms of secret sharing. However, it's easy to find "secret shares" hidden beneath the surface: for each gate of the circuit, the sender will hold two keys $(K_0, K_1)$, while the receiver will hold the key $K_b$, where $b$ is the result of the gate evaluation. In a sense, $(K_0, K_1)$ and $K_b$ form shares of the secret value $b$: each of them individually leaks no information about $b$, yet knowing both allows to recover $b$. In fact, they even "almost" form additive shares of $b$, since $K_b = b\cdot K_1 + (1-b)\cdot K_0 = b\cdot (K_0-K_1) + K_0$, hence $K_0$ and $K_b$ form additive shares of $b\cdot (K_0-K_1)$, where $(K_0-K_1)$ is a value known to the sender.

So, this was just to say that the notion of secret sharing is so fundamental that it does not make much sense to "not use secret sharing" whatsoever. However, if you're interested into protocols which do not directly build upon known secret sharing schemes, there are many:

  • Yao's garbled circuits, and all its modern improvements, are perhaps the most natural examples.
  • MPC protocols based on homomorphic encryption - some protocols from the 2000's used additive encryption, there are also many protocols relying on fully homomorphic encryption.
  • Some more theoretical MPC schemes achieving various "high end" properties do not inherently build upon secret sharing, like those based on indistinguishability obfuscation.

The reason why you see secret-sharing based techniques being used a lot out there is simple: the more you can rely on secret sharing, or other information-theoretic techniques, the more efficient your protocol will be in practice. Encryption, oblivious transfer, or any other public-key cryptographic primitive are expensive, since they use very heavy algebraic operations, or involve very large key size. On the other hand, secret sharing is as simple and efficient as it can get: a few XORs, perhaps some interpolation.

And the reason why we still hear a lot about garbled-circuit-based MPC, even though secret-sharing-based MPC is more computationally efficient, is because the former allow for secure computation with a constant number of rounds, while protocols built from secret sharing techniques will most of the time involve a much larger number of rounds. And in practice, if you're executing your protocol over the internet, the number of rounds matters a lot.

(actually, some of the latest state of the art MPC protocols get the best of both worlds by combining the two approaches)

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! This is a wonderful answer with a lot to dig into. I have two clarification questions. (1) You said "MPC protocols based on homomorphic encryption" don't use secret sharing, but isn't MPC with additive or Shamir secret sharing partially homomorphic? (2) What's the fundamental difference between an "information-theoretic technique" vs a "public-key cryptographic" technique? $\endgroup$ – kennysong May 21 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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