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?

$\endgroup$

1 Answer 1

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.

$\endgroup$
2
  • $\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$
    – sun
    Apr 3, 2016 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$ Apr 3, 2016 at 8:57

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.