One sub-component used a couple of times is a combined broadcast commitment functionality, implemented via echo broadcast.

In a nutshell, the idea behind echo broadcast is to ensure that a party sends the same message to all others. We accomplish this by sending a hash of all the messages we’ve received to everyone else, thus enabling us to realize if a different message was sent in the first round.

Definition (Echo Broadcast Protocol): The broadcast protocol $P [EchoBroadcast]$ is defined as follows:

P [EchoBroadcast] P_{i} \underline{(1) StartBroadcast_{i} (x) :} ↱_{i} (⋆, x, 0) \underline{WaitBroadcast_{i} (x) :} \overset{x}{^}_∙ ↰_{i} (⋆, 0) con_{i} \leftarrow Hash (\overset{x}{^}_∙) ↱_{i} (⋆, con_{i}, 1) return x_∙ \underline{EndBroadcast_{i} () :} \overset{con}{^}_∙ ↰_{i} (⋆, 1) if \exists j . \overset{con}{^}_{j} \neq = con_{i} : stop (⋆, 1) F [SyncComm] \otimes F [Hash] Leakage := {Hash, stop}

$□$

We model this hash function as a random oracle here.

The functionality that this implements is basically what you’d expect. The parties have to set their broadcast value, and then the functionality forces them to send it to all others. However, there is a sort of catch, in that adversaries can set a “trap” value, which will cause an abort later if the wrong broadcast value is set after the trap. This reflects the fact that adversaries can send their confirmation message early, thus potentially causing an abort later.

In practice this won’t matter for our purpose of using broadcasts for commitments, because the commitment values will be random, and thus not trappable.

Definition (Ideal Broadcast Protocol):

The protocol capturing the ideal behavior of broadcast is defined as follows:

P [IdealBroadcast] P_{i} \underline{(1) StartBroadcast_{i} (x) :} SetBroadcast_{i} (x) SendBroadcast_{i} (⋆) \underline{WaitBroadcast_{i} () :} x_∙ \leftarrow GetBroadcast_{i} (⋆) Sync_{i} (⋆) return x_∙ \underline{EndBroadcast_{i} () :} WaitSync_{i} (⋆) if BadBroadcast_{i} () : stop (⋆, 1) x_{i}, sent_ij, trap_ij \leftarrow ⊥ \underline{(1) (x) :} x_{i} \leftarrow x \underline{(S) :} assert x_{i} = ⊥ sent_ij \leftarrow true (\forall j \in S) \underline{(S) :} wait_(i, 0) sent_ji (\forall j \in S) return [x_{j} ∣ j \in S] \underline{Trap (j, m_∙) :} assert \forall i . m_{i} = ⊥ \lor (trap_ij = ⊥ \land x_{i} = ⊥) trap_ij \leftarrow m_{i} \underline{() :} return \exists j . trap_ji = ⊥ \land trap_ji = x_j \otimes F [Sync (1)] \otimes F [Stop] Leakage := {Trap, stop}

$□$

Another little detail is that the ideal functionality reflects the fact that the original broadcast had two rounds, via the synchronization mechanism.

Lemma:

For a negligible $ϵ$ , and any combination of malicious parties:

P [EchoBroadcast] ⇝ ϵ P [IdealBroadcast]

Proof:

As per usual, we unroll $Inst (P [EchoBroadcast])$ , to get:

Γ_{H}^{0} \underline{(1) StartBroadcast_{i} (x) :} \dots \otimes Γ_{M}^{0} = 1 ↱_{k}, ↰_{k}, Hash \circ F [SyncComm] \otimes F [Hash]

having split the game into an honest part, and a malicious part, long with the ideal functionalities. The malicious part will slowly become our simulator.

Our next step will be to modify the honest part to send both the hash of their messages, and an entire vector confirmation. The malicious part will ignore this new information, giving us an identical game.

Γ_{H}^{1} \dots \underline{WaitBroadcast_{i} () :} \overset{x}{^}_∙ ↰_{i} (⋆, 0) h_{i} \leftarrow Hash (\overset{x}{^}_∙) ↱_{i} (⋆, (h_{i}, \overset{x}{^}_∙), 1) \underline{EndBroadcast_{i} () :} (\hat{h}_∙, x_∙) ↰_{i} (⋆, 1) if \exists j . \hat{h}_{j} \neq = h_{i} : stop (⋆, 1) \otimes Γ_{M}^{1} \underline{↱_{k} (S, h_∙, 1) :} ↱_{k} (S, (h_∙, ⊥), 1) \underline{↰_{k} (S, 1) :} (\hat{h}_∙, \dots) ↰_{k} (S, 1) return [\hat{h}_{j} ∣ j \in S] \otimes 1 (↱_{k}, ↰_{k}, Hash) \circ F [SyncComm] \otimes F [Hash]

Now, we can have the honest parties omit their hash completely, only sending the vector. This requires moving some of the hashing logic into the malicious part, and the verification check at the end, but otherwise gives us an identical game.

Γ_{H}^{2} \dots \underline{WaitBroadcast_{i} () :} ↱_{i} (⋆, x, 0) \overset{x}{^}_∙ ↰_{i} (⋆, 0) ↱_{i} (⋆, (⊥, \overset{x}{^}_∙), 1) \underline{EndBroadcast_{i} () :} (\hat{h}_∙, x_∙) ↰_{i} (⋆, 1) if \exists j . (\hat{h}_{j} \neq = ⊥ \land \hat{h}_{j} \neq = Hash (x_{i})) \lor (x_{j} \neq = ⊥ \land Hash (x_{j}) \neq = Hash (x_{i})) : stop (⋆, 1) \otimes Γ_{M}^{2} \underline{↱_{k} (S, h_∙, 1) :} ↱_{k} (S, (h_∙, ⊥), 1) \underline{↰ (S, 1) :} (\hat{h}_∙, x_∙) ↰_{k} (S, 1) if \hat{h}_{j} = ⊥ : assert x_{j} \neq = ⊥ \hat{h}_{j} \leftarrow Hash (x_{j}) return [\hat{h}_{j} ∣ j \in S] \otimes 1 (↱_{k}, ↰_{k}, Hash) \circ F [SyncComm] \otimes F [Hash]

Because we’re using a random oracle. Nowe, we can extract preimages by snopping on the hash queries made by the adversary, and send those instead.

Γ_{H}^{3} \dots \underline{WaitBroadcast_{i} () :} \overset{x}{^}_∙ ↰_{i} (⋆, 0) ↱_{i} (⋆, (⊥, \overset{x}{^}_∙), 1) \underline{EndBroadcast_{i} () :} (\hat{h}_∙, x_∙) ↰_{i} (⋆, 1) if \exists j . (\hat{h}_{j} \neq = ⊥ \land \hat{h}_{j} \neq = Hash (x_{i})) \lor (x_{j} \neq = ⊥ \land Hash (x_{j}) \neq = Hash (x_{i})) : stop (⋆, 1) \otimes Γ_{M}^{3} μ [\dots] \leftarrow ⊥ \underline{Hash (x_∙) :} h \leftarrow Hash (x_∙) μ [h] \leftarrow x_∙ return h h_ij \leftarrow ⊥ \underline{↱_{k} (S, h_∙, 1) :} assert \forall j \in S . h_{j} \neq = ⊥ for j \in S \cap M : h_kj \leftarrow h_{j} for j \in S \cap H : if μ [h_{j}] \neq = ⊥ : ↱_{k} ({j}, (⊥, μ [h_{j}]), 1) else : ↱_{k} ({j}, (h_{j}, ⊥), 1) \underline{↰_{k} (S, 1) :} (\dots, x_∙) ↰_{k} (S \cap H, 1) wait_(k, 1) \forall j \in S \cap M . h_jk \neq = ⊥ return [Hash (_j) h_jk ∣ ∣ j \in S \cap H j \in S \cap M] \otimes 1 (↱_{k}, ↰_{k}, Hash) \circ F [SyncComm] \otimes F [Hash]

Now, except with negligible probability, a hash with no pre-image will cause the final verification check made by honest parties to fail, so we can instead cause an abort when the adversary tries to send such a hash, allowing us to always extract a pre-image, or to abort:

Γ_{H}^{4} \dots \underline{WaitBroadcast_{i} () :} \overset{x}{^}_∙ ↰_{i} (⋆, 0) ↱_{i} (⋆, \overset{x}{^}_∙, 1) \underline{EndBroadcast_{i} () :} x_∙ ↰_{i} (⋆, 1) if \exists j . Hash (x_{j}) \neq = Hash (x_{i}) : stop (⋆, 1) \otimes Γ_{M}^{4} \dots \underline{↱_{k} (S, h_∙, 1) :} \dots for j \in S \cap H : if μ [h_{j}] \neq = ⊥ : ↱_{k} ({j}, μ [h_{j}], 1) else : stop (⋆, 1) \underline{↰_{k} (S, 1) :} x_∙ ↰_{k} (S \cap H, 1) \dots \otimes 1 (↱_{k}, ↰_{k}, Hash) \circ F [SyncComm] \otimes F [Hash]

At this point, we’ve actually written a simulator for a protocol $P^{0}$ , which is like our initial protocol, except that the parties send their entire vector, rather than their hash. This shows that $P [EchoBroadcast] ⇝ P^{0}$ .

We can unroll $Inst (P^{0})$ to get:

Γ_{H}^{5} \dots \underline{WaitBroadcast_{i} () :} ↱_{i} (⋆, x, 0) \overset{x}{^}_∙ ↰_{i} (⋆, 0) ↱_{i} (⋆, \overset{x}{^}_∙, 1) \underline{EndBroadcast_{i} () :} x_∙ ↰_{i} (⋆, 1) if \exists j . Hash (x_{j}) \neq = Hash (x_{i}) : stop (⋆, 1) \otimes Γ_{M}^{5} = 1 ↱_{k}, ↰_{k}, Hash \circ F [SyncComm] \otimes F [Hash]

Except with negligible probability, the hashes won’t collide, so we can replace the hash based check with an actual check of equality.

Γ_{H}^{6} \dots \underline{EndBroadcast_{i} () :} \dots if \exists j . x_{j} \neq = x_{i} : stop (⋆, 1) \otimes Γ_{M}^{6} = Γ_{M}^{5} \circ F [SyncComm] \otimes F [Hash]

Now, we employ a classic trick, and are trying to get rid of $F [SyncComm]$ . Our strategy to do this will be to inline all of the variables in a common mutable functionality:

Γ_{H}^{7} \underline{(1) StartBroadcast_{i} (x) :} \overset{x}{^}_ij \leftarrow x \underline{WaitBroadcast_{i} () :} wait_(i, 0) \forall j . \overset{x}{^}_ji \neq = ⊥ x_ij \leftarrow \overset{x}{^}_∙ i sync_ij \leftarrow true \underline{EndBroadcast_{i} () :} wait_(i, 1) \forall j . sync_ji \neq = ⊥ if \exists j . x_ji \neq = \overset{x}{^}_∙ i : stop (⋆, 1) \otimes Γ_{M}^{7} \underline{↱_{k} (S, m_∙, 0) :} assert \forall j \in S . m_{j} \neq = ⊥ \land \overset{x}{^}_kj = ⊥ \overset{x}{^}_kj \leftarrow m_{j} (\forall j \in S) \underline{↱_{k} (S, m_∙, 1) :} assert \forall j \in S . m_{j} \neq = ⊥ \land x_kj = ⊥ x_kj \leftarrow m_{j} (\forall j \in S) sync_kj \leftarrow true (\forall j \in S) \underline{↰_{k} (S, 0) :} wait_(k, 0) \forall j \in S . \overset{x}{^}_jk \neq = ⊥ return [\overset{x}{^}_jk ∣ j \in S] \underline{↰_{k} (S, 1) :} wait_(k, 1) \forall j \in S . sync_jk \neq = ⊥ return [x_jk ∣ j \in S] \otimes F [SyncComm] \otimes F [Hash] \circ pub \overset{x}{^}_ij, x_ij, sync_ij \leftarrow ⊥ \otimes F [Stop]

Next, we can split the verification check into an honest check, and a malicious check.

Γ_{H}^{8} \dots \underline{EndBroadcast_{i} () :} \dots if \exists j \in H . \overset{x}{^}_∙ j \neq = \overset{x}{^}_∙ i : stop (⋆, 1) if \exists j \in M . x_ji \neq = \overset{x}{^}_∙ i : stop (⋆, 1) \otimes Γ_{M}^{8} = Γ_{M}^{7} \otimes F [SyncComm] \otimes F [Hash] \circ pub \overset{x}{^}_ij, x_ij, sync_ij \leftarrow ⊥ \otimes F [Stop]

The only reason the honest check will fail is if the adversary sends to different messages to honest parties, causing their confirmations to differ. We can detect that in $Γ_{M}$ instead, replacing the honest check.

Γ_{H}^{9} \underline{(1) StartBroadcast_{i} (x) :} \overset{x}{^}_ij \leftarrow x sent_ij \leftarrow true \underline{WaitBroadcast_{i} () :} wait_(i, 0) \forall j . \overset{x}{^}_ij \neq = ⊥ x_ij \leftarrow \overset{x}{^}_∙ i sync_ij \leftarrow true \underline{EndBroadcast_{i} () :} wait_(i, 1) \forall j . sync_ji \neq = ⊥ if \exists j \in M . x_ji \neq = \overset{x}{^}_∙ i : stop (⋆, 1) \otimes Γ_{M}^{9} x_{k} \leftarrow ⊥ \underline{↱_{k} (S, m_∙, 0) :} assert \forall j \in S . m_{j} \neq = ⊥ \land \overset{x}{^}_kj = ⊥ for j \in S \cap H : if x_{k} = ⊥ : x_{k} \leftarrow m_{j} elif x_{k} \neq = m_{j} : stop ({j}, 1) \overset{x}{^}_kj \leftarrow m_{j} (\forall j \in S) \dots \otimes F [SyncComm] \otimes F [Hash] \circ pub \overset{x}{^}_ij, x_ij, sent_ij, sync_ij \leftarrow ⊥ \otimes F [Stop]

Now, the only thing that can cause a malicious failure is if a bad $x_ij$ value is set. We can capture this with a trap value.

Γ_{H}^{10} \underline{(1) Broadcast_{i} (x) :} \overset{x}{^}_ij \leftarrow x sent_ij \leftarrow true \underline{WaitBroadcast_{i} () :} wait_(i, 0) \forall j . \overset{x}{^}_ij \neq = ⊥ x_ij \leftarrow \overset{x}{^}_∙ i sync_ij \leftarrow true \underline{EndBroadcast_{i} () :} wait_(i, 1) \forall j . sync_ji \neq = ⊥ if trap_∙ i \neq = ⊥ \land trap_∙ i \neq = \overset{x}{^}_∙ i : stop (⋆, 1) \otimes Γ_{M}^{10} \dots \underline{↱_{k} (S, m_∙, 1) :} assert \forall j \in S . m_{j} \neq = ⊥ \land x_kj = ⊥ for j \in S \cap H : if trap_∙ j = ⊥ : trap_∙ j \leftarrow m_{j} elif trap_∙ j \neq = m_{j} : stop ({j}, 1) x_kj \leftarrow m_{j} (\forall j \in S) sync_kj \leftarrow true (\forall j \in S) \otimes F [SyncComm] \otimes F [Hash] \circ pub \overset{x}{^}_ij, trap_ij, x_ij, sent_ij, sync_ij \leftarrow ⊥ \otimes F [Stop]

Since we can’t equivocate, simplify variables.

Γ_{H}^{11} \underline{(1) Broadcast_{i} (x) :} SetBroadcast_{i} (x) SendBroadcast_{i} (⋆) \underline{WaitBroadcast_{i} () :} x_∙ \leftarrow GetBroadcast_{i} (⋆) Sync_{i} (⋆) \underline{EndBroadcast_{i} () :} WaitSync_{i} (⋆) if BadBroadcast_{i} () : stop (⋆, 1) \otimes Γ_{M}^{11} x_{k}, \overset{x}{^}_ij, x_ij \leftarrow ⊥ \underline{↱_{k} (S, m_∙, 0) :} assert \forall j \in S . m_{j} \neq = ⊥ \land \overset{x}{^}_kj = ⊥ for j \in S \cap H : if x_{k} = ⊥ : x_{k} \leftarrow m_{j} SetBroadcast_{k} (x_{k}) elif x_{k} \neq = m_{j} : stop ({j}, 1) \overset{x}{^}_kj \leftarrow m_{j} (\forall j \in S \cap M) SendBroadcast_{k} (S \cap H) \underline{↱_{k} (S, m_∙, 1) :} assert \forall j \in S . m_{j} \neq = ⊥ \land x_kj = ⊥ for j \in S \cap H : if trap_∙ j = ⊥ : Trap (j, m_{j}) elif trap_∙ j \neq = m_{j} : stop ({j}, 1) x_kj \leftarrow m_{j} (\forall j \in S) Sync_{k} (S) \underline{↰_{k} (S, 0) :} wait_(k, 0) \forall j \in S \cap M . \overset{x}{^}_jk \neq = ⊥ \overset{x}{^}_jk \leftarrow GetBroadcast_{k} ({j}) (\forall j \in S \cap H) return [\overset{x}{^}_jk ∣ j \in S] \underline{↰_{k} (S, 1) :} WaitSync_{k} () x_jk \leftarrow GetBroadcast_{k} (⋆) (\forall j \in S \cap H) return [x_jk ∣ j \in S] \otimes F [SyncComm] \otimes F [Hash] \circ F [Broadcast]^{'} x_{i}, sent_ij, trap_ij \leftarrow ⊥ \underline{(1) SetBroadcast_{i} (x) :} x_{i} \leftarrow x \underline{GetBroadcast_{i} (S) :} wait_(i, 0) sent_ji (\forall j \in S) return [x_{j} ∣ j \in S] \underline{Trap (j, m_∙) :} assert trap_∙ j = ⊥ trap_ij \leftarrow m_{i} \underline{BadBroadcast (j, m_∙) :} return \exists i . trap_ij \neq = ⊥ \land trap_ij \neq = x_i \otimes F [Sync (1)] \otimes F [Stop]

As suggested by the introduction of this broadcast functionality, we now have a new protocol $P^{1}$ , and have shown that $P^{0} ⇝ P^{1}$ by our game hopping. We’re not quite done yet, because the trapping here is a bit too strong, in that the adversary can trap even after a broadcast value has been set. We can simulate this freedom away.

Next, unroll again.

Γ_{H}^{12} \underline{(1) StartBroadcast_{i} (x) :} \dots \otimes Γ_{M}^{12} = 1 SetBroadcast_{k}, GetBroadcast_{k}, BadBroadcast_{k}, Sync_{k}, Trap \circ F [Broadcast]^{'} \otimes F [Sync (1)] \otimes F [Stop]

Traps that happen after a broadcast can be simulated by triggering an abort ourselves in the simulator.

Γ_{H}^{13} = Γ_{H}^{12} \otimes Γ_{M}^{13} \underline{Trap (j, m_∙) :} for i \in H : if \exists k . x \leftarrow nowait GetBroadcast_{k} ({i}) : if m_{i} \neq = x : stop ({j}, 1) return Trap (j, m_∙) \circ F [Broadcast] \otimes F [Sync (1)] \otimes F [Stop]

This is a simulator for $P [IdealBroadcast]$ , which concludes our proof, via the logic:

P [EchoBroadcast] ⇝ P^{0} ⇝ P^{1} ⇝ P [IdealBroadcast]

$■$

Commitments

Our main application of broadcast will be to define a commitment protocol. The basic idea is that you commit to a value by hashing it, along with a random salt, and then broadcast that commitment. Later, you can open the value by sending it along with the salt.

Definition (Commitment Protocol):

P [Commit] P_{i} x_{i}, r_{i} \leftarrow ⊥ \underline{(1) SetCommit_{i} (x) :} x_{i} \leftarrow x, r_{i} $ 01^{2 λ} SetBroadcast_{i} (Hash (x_{i}, r_{i})) \underline{Commit_{i} () :} SendBroadcast_{i} (⋆) \underline{WaitCommit_{i} () :} return WaitBroadcast_{i} () \underline{Open_{i} () :} assert x_{i} \neq = ⊥ ↱_{i} (⋆, (x_{i}, r_{i}), 2) \underline{WaitOpen_{i} () :} c_∙ \leftarrow WaitCommit_{i} () EndBroadcast_{i} () (\overset{x}{^}_∙, \overset{r}{^}_∙) ↰_{i} (⋆, 2) if \exists j . Hash (\overset{x}{^}_{j}, \overset{r}{^}_{j}) \neq = c_{j} : stop (⋆, 2) return \overset{x}{^}_∙ F [Stop] ⊚ F [SyncComm] \otimes F [Hash] Leakage := {Hash, stop} ⊲ P [EchoBroadcast]

$□$

The ideal functionality this is supposed to implement is relatively straightforward. You set a commit value, and can wait for others to commit as well. Finally, you can open, which doesn’t allow you to actually change the value you’ve committed to, it just makes it now visible to others. We also have the usual abort points remaining in the protocol.

Definition (Ideal Commitment):

P [IdealCommit] P_{i} \underline{(1) SetCommit_{i} (x) :} SetCommit_{i} (x) \underline{Commit_{i} () :} Commit_{i} (⋆) \underline{WaitCommit_{i} () :} WaitCommit_{i} (⋆) Sync_{i} (⋆) \underline{Open_{i} () :} Open_{i} (⋆) \underline{WaitOpen_{i} () :} WaitCommit_{i} () WaitSync_{i} (⋆) return WaitOpen_{i} (⋆) x_{i}, com_ij, open_ij \leftarrow ⊥ \underline{(1) (x) :} x_{i} \leftarrow x \underline{(S) :} com_ij \leftarrow true (\forall j \in S) \underline{(S) :} wait_(i, 0) \forall j \in S . com_ji \underline{(S) :} assert x_{i} = ⊥ open_ij \leftarrow true (\forall j \in S) \underline{(S) :} wait_(i, 2) \forall j \in S . open_ji return x_∙ \otimes F [Sync (1)] ⊚ F [Stop] Leakage := {Hash, stop}

$□$

Lemma:

For some negligible $ϵ$ , and any combination of malicious parties, we have:

P [Commit ⇝ ϵ P [IdealCommit]

Proof:

First, we have $P [Commit] ⇝ P^{0}$ , where $P^{0}$ replaces $P [EchoBroadcast]$ with $P [IdealBroadcast]$ , and we start from there.

We unroll $Inst (P^{0})$ to get:

Γ_{H}^{0} \underline{(1) SetCommit_{i} (x) :} \dots \otimes Γ_{M}^{0} = 1 SetBroadcast_{k}, SendBroadcast_{k}, GetBroadcast_{k}, BadBroadcast_{k}, Trap, Sync_{k}, WaitSync_{k}, ↱_{k}, ↰_{k}, Hash, stop \circ F [Broadcast] \otimes F [Sync (1)] \otimes F [SyncComm] \otimes F [Hash] ⊚ F [Stop]

Now, a trap value needs to be provided before the commitment value is known. However, for honest parties, these commitment values are in all likelihood freshly sampled, because of the entropy in $r$ . This means that trapping honest values is useless, since except with negligible probability, it has no effect.

Γ_{H}^{1} = Γ_{H}^{0} \otimes Γ_{M}^{1} \dots \underline{Trap (j, m_∙) :} com_{i} \leftarrow x_{i} \neq = ⊥ (\forall i \in M) com_{i} \leftarrow nowait GetBroadcast_{k} ({i}) \neq = ⊥ (\forall i \in H) assert \forall i . m_{i} = ⊥ \lor (trap_ij = ⊥ \land \neg com_{i}) \forall i \in H . m_{i} \leftarrow ⊥ Trap (j, m_∙) \circ F [Broadcast] \otimes F [Sync (1)] \otimes F [SyncComm] \otimes F [Hash] ⊚ F [Stop]

We can now replace $F [Broadcast]$ with a function $F [Broadcast^{'}]$ , in which trapping isn’t possible, because we can simulate the effects ourself.

Γ_{H}^{2} = Γ_{H}^{1} \otimes Γ_{M}^{2} \dots c_{k}, trap_ij, bad_{k} \leftarrow ⊥ \underline{Trap (j, m_∙) :} com_{i} \leftarrow c_{i} \neq = ⊥ (\forall i \in M) com_{i} \leftarrow nowait GetBroadcast_{k} ({i}) \neq = ⊥ (\forall i \in H) assert \forall i . m_{i} = ⊥ \lor (trap_ij = ⊥ \land \neg com_{i}) \forall i \in H . m_{i} \leftarrow ⊥ trap_ij \leftarrow m_{i} \underline{SetBroadcast_{k} (c) :} c_{k} \leftarrow c if \exists j . trap_jk \neq = ⊥ \land trap_jk \neq = c : bad_{j} \leftarrow true if j \in H : stop ({j}, 1) \underline{BadBroadcast_{k} () :} return bad_{k} \circ F [Broadcast^{'}] \otimes F [Sync (1)] \otimes F [SyncComm] \otimes F [Hash] ⊚ F [Stop]

From this we see that we’re in fact simulating a protocol $P^{1}$ , which is like $P [IdealBroadcast]$ , except that trapping is not possible. Let’s unroll that protocol, to get:

Γ_{H}^{3} \underline{(1) SetCommit_{i} (x) :} \dots \otimes Γ_{M}^{3} = 1 SetBroadcast_{k}, SendBroadcast_{k}, GetBroadcast_{k},, Sync_{k}, WaitSync_{k}, ↱_{k}, ↰_{k}, Hash, stop \circ F [Broadcast^{'}] \otimes F [Sync (1)] \otimes F [SyncComm] \otimes F [Hash] ⊚ F [Stop]

At the end of $WaitOpen_{i}$ , we check that the opened values match the commitments. Because honest parties will always open the right values, we can instead limit the check to malicious parties.

Γ_{H}^{4} \underline{WaitOpen_{i} (x) :} c_∙ \leftarrow WaitCommit_{i} () EndBroadcast_{i} () (\overset{x}{^}_∙, \overset{r}{^}_∙) ↰_{i} (⋆, 2) if \exists j \in M . Hash (\overset{x}{^}_{j}, \overset{r}{^}_{j}) \neq = c_{j} : stop (⋆, 2) return \overset{x}{^}_∙ \otimes Γ_{M}^{4} = Γ_{M}^{3} \circ F [Broadcast^{'}] \otimes F [Sync (1)] \otimes F [SyncComm] \otimes F [Hash] ⊚ F [Stop]

Now, because of the entropy of the $r$ values, in all likelihood the random oracle will not have been queried at that value before, and so we can instead assume that the value is random, and then backfill it later. Thus, we have honest parties broadcast completely random commitments, and then program the random oracle after they open the commitment.

Γ_{H}^{5} x_{i}, c_{i} \leftarrow ⊥ \dots \underline{(1) SetCommit_{i} (x) :} x_{i} \leftarrow x c_{i} $ 01^{2 λ} SetBroadcast_{i} (c_{i}) \underline{Open_{i} () :} assert x_{i} \neq = ⊥ r_{i} $ 01^{2 λ} ↱_{i} (⋆, (x_{i}, r_{i}), 2) \underline{WaitOpen_{i} (x) :} c_∙ \leftarrow WaitCommit_{i} () EndBroadcast_{i} () (\overset{x}{^}_∙, \overset{r}{^}_∙) ↰_{i} (⋆, 2) if \exists j \in M . Hash (\overset{x}{^}_{j}, \overset{r}{^}_{j}) \neq = c_{j} : stop (⋆, 2) return \overset{x}{^}_∙ \otimes Γ_{H}^{5} \dots \underline{Hash (x, r) :} if \exists k \in M, j \in H . nowait ↰_{k} ({j}, 2) = (x, r) : if \exists k \in M, j \in H . nowait GetBroadcast ({j}) \to c_{j} : return c_{j} return Hash (x, r) \circ F [Broadcast^{'}] \otimes F [Sync (1)] \otimes F [SyncComm] \otimes F [Hash] ⊚ F [Stop]

Next, except with negligible probability we can extract preimages of commitments, since a commitment that hasn’t come from the hash function will fail with probability $\leq 2^{- 2 λ}$ .

Γ_{H}^{6} = Γ_{H}^{5} \otimes Γ_{H}^{6} μ [∙], x_{k}, r_{k} \leftarrow ⊥ \dots \underline{SetBroadcast_{k} (h) :} assert h \in μ (x_{k}, r_{k}) \leftarrow μ [h] SetBroadcast_{k} (h) \underline{Hash (x, r) :} h \leftarrow Hash^{'} (x, r) μ [h] \leftarrow (x, r) return h \underline{Hash^{'} (x, r) :} \dots \circ F [Broadcast^{'}] \otimes F [Sync (1)] \otimes F [SyncComm] \otimes F [Hash] ⊚ F [Stop]

Next, instead of checking for bad openings inside honest parties, we can instead have malicious parties directly cause a stop once they send a bad value.

Γ_{H}^{7} \dots \underline{WaitOpen_{i} () :} c_∙ \leftarrow WaitCommit_{i} () EndBroadcast_{i} () (\overset{x}{^}_∙, \overset{r}{^}_∙) ↰_{i} (⋆, 2) if \exists j . Hash (\overset{x}{^}_{j}, \overset{r}{^}_{j}) \neq = c_{j} : stop (⋆, 2) return \overset{x}{^}_∙ \otimes Γ_{H}^{7} μ [∙], x_{k}, r_{k} \leftarrow ⊥ \dots \underline{↱_{k} (S, (\overset{x}{^}_∙, \overset{r}{^}_∙)) :} for j \in S \cap H . Hash (\overset{x}{^}_{j}, \overset{r}{^}_{j}) \neq = Hash (x_{k}, r_{k}) : stop ({j}, 2) ↱_{k} (S, (\overset{x}{^}_∙, \overset{r}{^}_∙)) \circ F [Broadcast^{'}] \otimes F [Sync (1)] \otimes F [SyncComm] \otimes F [Hash] ⊚ F [Stop]

(red parts deleted).

Now, because random oracles are collision resistant, we get the same result to check full equality rather than hash equality.

Γ_{H}^{8} = Γ_{H}^{7} \otimes Γ_{H}^{8} \dots \underline{↱_{k} (S, (\overset{x}{^}_∙, \overset{r}{^}_∙), 2) :} for j \in S \cap H . (\overset{x}{^}_{j}, \overset{r}{^}_{j}) \neq = (x_{k}, r_{k}) : stop ({j}, 2) ↱_{k} (S, (\overset{x}{^}_∙, \overset{r}{^}_∙)) \circ F [Broadcast^{'}] \otimes F [Sync (1)] \otimes F [SyncComm] \otimes F [Hash] ⊚ F [Stop]

At this point, the malicious party can’t actually send honest parties an opened value that’s any different than the one they used to generate their initial broadcast hash. We can now rewrite the adversary to use the ideal commitment functionality instead.

Γ_{H}^{9} \underline{(1) SetCommit_{i} (x) :} SetCommit_{i} (x) \underline{Commit_{i} () :} Commit_{i} (⋆) \underline{WaitCommit_{i} () :} WaitCommit_{i} (⋆) Sync_{i} (⋆) \underline{Open_{i} () :} Open_{i} (⋆) \underline{WaitOpen_{i} () :} WaitCommit_{i} () WaitSync_{i} (⋆) return WaitOpen_{i} (⋆) \otimes Γ_{H}^{9} \dots \underline{SetBroadcast_{k} (h) :} assert h \in μ h_{k} \leftarrow h SetCommit_{k} (μ [h]) \underline{SendBroadcast_{k} (S) :} \hat{h}_kj \leftarrow h_{k} (\forall j \in S \cap m) Commit_{k} (S) \underline{GetBroadcast_{k} (S) :} WaitCommit_{k} (S) for j \in S \cap H . c_{j} = ⊥ : c_{j} $ 01^{2 λ} return [c \hat{h}_jk ∣ j \in S \cap H ∣ j \in S \cap M] \underline{↱_{k} (S, \overset{m}{^}_∙, 2) :} (\overset{x}{^}_∙, \overset{r}{^}_∙) \leftarrow \overset{m}{^}_∙ for j \in S \cap H . (\overset{x}{^}_{j}, \overset{r}{^}_{j}) \neq = (x_{k}, r_{k}) : stop ({j}, 2) S \leftarrow S / {j} m_kj \leftarrow (\forall j \in S \cap M) Open_{k} (S) \underline{↰_{k} (S, 2) :} xr_∙ \leftarrow WaitOpen_{k} (S) return [xr m_kj ∣ j \in S \cap H ∣ j \in S \cap M] \underline{Hash (x, r) :} h \leftarrow Hash^{'} (x, r) μ [h] \leftarrow (x, r) return h \underline{Hash^{'} (x, r) :} if \exists k \in M, j \in H . nowait ↰_{k} ({j}, 2) = (x, r) : if \exists k \in M, j \in H . nowait GetBroadcast ({j}) \to c_{j} : return c_{j} return Hash (x, r) \otimes 1 (Sync_{k}, WaitSync_{k}, stop) \otimes F [Hash] \circ F [IdealCommit] \otimes F [Sync (1)] ⊚ F [Stop]

This is fact a simulator over $P [IdealCommit]$ , concluding our proof.

$■$

cronokirby

Explorer

Cait-Sith Security (1): Echo Broadcast

Commitments

Graph View