2
$\begingroup$

This question is actually continuation of my previous one.

Secure multi-party computation for digital signature

to implement solution there, I have to generate random data for padding (I will use PSS).

  1. There are N parties. Up to M are malicious adversaries (were trusted, but got taken over silently). I will be happy with solution for any N and M = 1.
  2. Parties should send to each other some random data d[i] and each party based on all d[1..N] should generate some final random value R.

From one side, value should be one and the same for all parties, i.e. calculation should be a fixed predictable process and all parties should get one and the same value R. From another side, malicious adversary party should not be able to affect randomness of R[i], i.e. even malicious adversary should not be able to generate d[m] to get specific R.

Looks like I can achieve this by simply hashing all d[i] values in predictable order. For instance sort d[i] and calculate hash of "well-known-secure-prefix" + d[1..N] + "well-known-secure-suffix".

Am I missing anything?

$\endgroup$
  • 3
    $\begingroup$ What you're looking for is called a coin-flipping protocol. $\endgroup$ – Maeher Feb 27 at 17:52
2
$\begingroup$

Looks like I can achieve this by simply hashing all d[i] values in predictable order.

That doesn't quite work; the issue is that the last one to contribute their d[i] value has seen all the previous ones, and can then quickly test candidate d[i] values, looking for one when produces the random padding they like. This is probably not a huge vulnerability (if the protocol expects a d[i] value within a few seconds, an implementation might be able to test a few million to billions of candidate values (depending on attacker resources) before having to select one); however it is something.

The fix for that is for to have everyone submit commitments to their shares before revealing them. For example, party i first publishes $\text{hash}( d[i] || r_i )$ to everyone, and not until everyone has published their commitments, everyone then publishes their $d[i]$ and $r_i$ values (and everyone can check that their revealed values matches their commitments). Then, everyone can combine all the $d[i]$ values, and you then get a hash value that no one has control over.

The best an attacker can do is arrange to be the last person to reveal their $d[i], r_i$ values, and then, if the combined value isn't what they like, just refuse (or misopen their commitment). This does allow the attacker a veto over the randomness; however for the attacker to use their veto, they have to give a hint that they are the malicious party. You could try to avoid this by using a function that is hard to compute quickly (e.g. Argon2 with appropriate parameters); I'm not sure if it's worth the trouble...

$\endgroup$

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.