5
$\begingroup$

I am trying to build a protocol (or find an existing one) for creating a set $S_2$ with PKI from a set of parties $S_1$ that initially does not know anything about the other parties.

We assume end-to-end communication and broadcast, all with a delay up to $\text{Delta}_\text{transmission}$. Additionally, we also use NIST random beacon (could simplify the protocol, but it doesn't solve the deadline problem below).

So every party $p \in S_1$ would run this protocol $A$ at a time $t_1$, and we would like at $t_2$ that all honest parties have the same set $S_2$ of parties with PKI.

I could imagine a solution where all parties generate a private/public key pair, and then the protocol dictates that for each round, they broadcast a signed message with their public key and current vision of $S_2$; ie $m = [pk, S_2]$.

each time they receive a valid signed message with a new public key $pk'$ and a new set $S_2'$, they do $S_2 = S_2' \cup S_2 \cup {pk'}$, and rebroadcast $[pk, S_2]$

The main problem with this scenario is termination : if we want the protocol to terminate at any deadline $t_2$ fixed in advance; there is always a way for an attacker to break consistency (all honest parties have the same set $S_2$ in the end) by sending a new valid message $m'$ just before the deadline to a party $p$, so that this party accept it, but when the honest party rebroadcasts his new set including the new key, other honest parties discard it because it arrives after the deadline $t_2$.

Any help, either directly on how to fix the deadline problem, or indirectly how to build such protocol, would be greatly appreciated :)

|improve this question
$\endgroup$
-1
$\begingroup$

There might be multiple solutions, and this could be one of them.

You can use multiple rounds of Terminating Reliable Broadcast (TRB). Each party in $S_1$ sends a message with their own proposal $pk$ -- this corresponds to one round of TRB.

After $|S_1|$ rounds, you're good to go. Since all honest parties have the same set of individual proposals, they can deterministically compute the result $S_2$.

Naturally, if you assume $f<|S_1|$ nodes can fail (e.g. by crashing, arbitrary), you have to stop the protocol after $|S_1|-f$ rounds.

PS: I might have misunderstood some of the details in your the question, so please correct me if anything's amiss.

|improve this answer
$\endgroup$
  • $\begingroup$ Hey, thank for your answer which is already helpful. However in my case the parties don't know anything about the other ones (fully peer to peer), in particular they don't know in advance the number of parties running the protocol. $\endgroup$ – lbarman Dec 18 '14 at 7:58
  • $\begingroup$ Are you assuming a Byzantine adversary? $\endgroup$ – adizere Dec 18 '14 at 9:44
  • $\begingroup$ The adversary can send (valid) messages to every part or a specific ones, can read unencrypted communication channel (but cannot tamper or delete messages from a honest party to a honest party), and he may generate several identities (not a problem here). He can also deviate arbitrarily from the protocol given a reasonnable bound on message sent and processing power on his side. His aim is to make the protocol fail, ie two honest parties end up with different sets $S_2$ $\endgroup$ – lbarman Dec 18 '14 at 11:43

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.