3
$\begingroup$

A set of parties can securely generate a random number $r \in \{1,2,3,\dots, k\}$ when $k$ is publicly known. However, can we generate the random number $r$ if $k$ is not publicly known and is held by the parties using a VSS scheme?

Can you point me to any Multiparty Computation literature which looks at the above question?

Improve this question
$\endgroup$
5
$\begingroup$

You can do anything in MPC, as long as you can express it in a circuit. I assume that there is a known upper bound on $k$ (otherwise you can't even share it). In that case, all you need to do is to take enough randomness (security parameter number of bits more than the upper bound) and then compute the sum of the randomness held by each party modulo $k$ (plus 1). This can certainly be done via a circuit.

Improve this answer
$\endgroup$
  • $\begingroup$ Let us say that $m$ is a publicly known upper bound on $k$. Further let say each party $P_i$ picks $r_i \in_R Z_m$. Let us assume that the parties are able to perform $s = \sum_{i=1}^{n}r_i\ mod\ k$ securely [1]. Now my question is whether $s$ is a uniformly random number in the range $\{ 0,1,2,3,\dots,k-1 \}$? I don't think that this is true for every possible value of $m$. \\ [1] Damgård, Ivan, et al. "Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation." Theory of Cryptography. Springer Berlin Heidelberg, 2006. 285-304. $\endgroup$ – Itachi Apr 3 '16 at 8:56
  • 2
    $\begingroup$ It is not. That's why you have to take security parameter more bits, as I wrote in my answer. $\endgroup$ – Yehuda Lindell Apr 3 '16 at 8:57

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.