3
$\begingroup$

Could anyone direct me to literature regarding privacy proofs in the MPC setting.

For example, how can one prove the following simple problem:
Suppose a setting with $n$ parties $S_1, \ldots, S_n$ wish to compute an additive sharing of $0$, so $r_i\in S_i$ such that $\sum r_i = 0$.

The parties can be assumed to hold some precomputed pairwise shared secrets $k_{ij}=k_{ji}\in S_i,S_j$.

Assume that $H$ is a public hash function. Then the parties compute $$ h_i = \sum_{j\not= i}(-1)^{i<j}H(k_{ij}), $$ where $i<j$ is $1$ if true and $0$ otherwise. Certainly $h_i$ is an additive secret sharing of $0$, and this should be computationaly indistinguishable from, for example, a truly random additive secret sharing computed by some functionality and provided to the parties.

I imagine there should be a generic proof technique for these kinds of problems. Could you direct me to some literature that covers this. I am reading "Secure Multiparty Computation and Secret Sharing" by Cramer, Damgard and Nielsen, but the book seems like an overkill, and I feel like there should be a simpler proof for such a simple statement.

Similarly, consider this statement for a malicious adversary setting. Suppose 1 out of 4 servers can be malicious, they hold a replicated secret sharing of a value, and wish to publish the value itself.
More precisely let $a = a_1 + a_2 + a_3 + a_4$, and let server $i$ hold values $a_i, a_{i+1}$. They wish to reveal $a$, but not all the shares. What they will do is compute a replicated secret sharing of the same form $0=r_1 + r_2 + r_3 + r_4$, server $i$ holding $r_i, r_{i+1}$, and then the servers will publish $(b^i_i, b^i_{i+1})=(a_i+r_i, a_{i+1} + r_{i+1})$ as shown in the table below.

servers value mask output
$S_1$ $a_1,a_2$ $r_1, r_2$ $b^1_1 = a_1 + r_1,\; b^1_2 = a_2 + r_2$
$S_2$ $a_2,a_3$ $r_2, r_3$ $b^2_2 = a_2 + r_2,\; b^2_3 = a_3 + r_3$
$S_3$ $a_3,a_4$ $r_3, r_4$ $b^3_3 = a_3 + r_3,\; b^3_4 = a_4 + r_4$
$S_4$ $a_4,a_1$ $r_4, r_1$ $b^4_4 = a_4 + r_4,\; b^4_1 = a_1 + r_1$

After the servers reveal the outputs, anyone can confirm the correctness of the outputs by checking that $b^i_j = b^k_j$ for all $j=1,2,3,4$, and $k=j, j-1$. Since there is at most one malicious server, we can check their output by comparing it to one of an honest server. Certainly a malicious user can't force a malicious output in this game (but can force an abort since if two outputs are different, there is no way to check which is the honest one.)

Now, I would like to ask how to prove security in this very simple game in the malicious setting? We can also assume that there is a functionality for computing the $r_i$'s, very similar to the one above, by assuming some common secrets and computational security. It seems like there should be a simpler way to prove it rather than going through all the UC framework, but maybe I am wrong.

$\endgroup$

1 Answer 1

2
$\begingroup$

This won't be a full-fledged answer, since I don't have good pointers in mind (I read very few MPC textbooks). Still, a few comments on your proposal:

  • the construction can be simplified a lot. First, you should view the $k_{ij} = k_{ji}$ as 2-party additive shares of zero. For that, simply have one of the parties flip its key (say, the party $S_i$ with $i<j$)$^1$. Second, I don't see the point of the hashes: the parties with $k_{ij} = k_{ji}$ can just define their hashes $H(k_{ij}) = H(k_{ji})$ to be their shared keys. Hashing does not add any security.
  • With this view, your construction becomes: we assume that $n$ parties start with $n\cdot(n-1)/2$ pairwise 2-party shares of zero. Then, they locally sum all their shares. The resulting values form $n$-party shares of zero.
  • Viewed this way, this is an extremely standard way to get $n$-party shares of a sum of values given pairwise $2$-party shares of each of the values. It is used for example in the construction of $n$-party Beaver triples from 2-party Beaver triples, which I'm sure you can find in several textbooks. But also, it's so simple that most writeups will simply omit the proof as a standard exercise.
  • If you want to prove it yourself, here's a sketch: consider an adversary corrupting $t$ parties. The goal is to show that the share of each uncorrupted party is, from the viewpoint of the adversary, uniformly random conditioned on the sum of all shares being equal to zero. Then, if $t=n-1$ the condition is vacuous and there is nothing to prove (since the share of the honest party is fixed by the other shares). If $t= n-2$, then from the viewpoint of the adversary, if all corrupted parties' shares sum to a value $v$, the shares of the remaining parties should be distributed as random shares of $-v$. Now, by construction, the share of $P_i$ is $-v_i+k$ and the share of $P_j$ is $-v_j-k$, where $v_i + v_j = v$ and $k$ is their truly random shared key, which is unknown to the adversary. It is easy to see that this is distributed as a random share of $-v$. The proof for smaller values of $t$ follows similarly.

Not entirely related, but "computing random-looking additive shares of 0" is a standard cryptographic problem. In particular, there are very nice constructions (from any pseudorandom function, hence any OWF) with formal security proofs in Gilboa-Ishai, CRYPTO'99, which allow generating an arbitrary number of (pseudorandom) zero-shares, without any communication.

$^1$: also, if you view the keys $k_{i,j}$ as elements of $\mathbb{F}_2^n$ (that is, the sum is the bitwise-XOR), then you can dispense with the $(-1)$'s entirely, since $+1 = -1$ over $\mathbb{F}_2$. Of course, if you need additive shares over a different group, you'll need these (-1)'s.

$\endgroup$
4
  • $\begingroup$ Thank you very much, this is very helpful! Can't believe I didn't notice the 2-party secret sharing :) This is a nicer approach definitely. My problem is with showing that this is secure even when you use some computationaly secure primitive to generate these shares. IMO it is obvious, but I would like to see a formal proof and the only proofs I find are complicated, I still haven't seen a single introductory simple proof for some basic constructions. Is it enough to just say that 2-party 0 sharing with hashes is comp. secure and so the rest follows? $\endgroup$
    – Kolja
    Oct 17, 2023 at 10:49
  • $\begingroup$ The reference is great, thanks for sharing it ! $\endgroup$
    – Kolja
    Oct 17, 2023 at 10:49
  • $\begingroup$ If you use a computational primitive to generate these shares, a nice way to analyze it is to use a hybrid model: assume that all parties are given access to an ideal functionality that distributes (perfectly secure) 2-party shares of zero. Give a protocol that, given access to such a functionality, securely implements the functionality that distributes n-party shares of zero. Then, show separately that your computational protocol securely implement the ideal 2-party functionality. $\endgroup$ Oct 17, 2023 at 11:22
  • $\begingroup$ Once this is done, security follows from a composition theorem which states that, in the semi-honest model, if P securely implements a functionality A and P' securely implements B in a hybrid world given access to A, then the protocol P'' which is "P' but calls to A are replaced by execution of P" is secure (note that this theorem is not true in the malicious setting in general). The theorem is stated and proved formally in "Foundations of Cryptography, volume 2" for example. For proving security given ideal functionalities, Yehuda Lindell's "tutorial on simulation" is a great resource. $\endgroup$ Oct 17, 2023 at 11:25

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.