2
$\begingroup$

I am not sure if this is the right place to ask but I will give it a try. If not, let me know and I will ask somewhere else :)

We discussed the byzantine agreement and broadcast channel in class. We showed that broadcast implies byzantine agreement if $t < \frac{n}{2}$, where $t$ are dishonest parties and $n$ are the honest parties.

We designed a protocol for the byzantine agreement

  1. All parties send input $p_i$ over broadcast channel
  2. Parties output majority of received values

All parties receive same message $p_i$ via broadcast channel -> Majority is unique.

Now I have to show that byzantine implies broadcast. That means I have to design a broadcast protocol which uses Byzantine agreement as subroutine. At the end we have to explain why it satisfies the security properties of the broadcast channel.

I am stuck with designing the protocol. From what I understood is the byzantine agreement based on point-to-point channels. I had the idea to have it based on a PKI structure. Each sender owns the public key of the other parties, encrypts the message and sends it.

This would simulate a point-to-point channel, but on the other hand it means a lot calculation and time. Not sure if the last point is important to consider in this kind of view but I took it into consideration due to the "Termination" security property.

Would be nice if someone is able to help me.

$\endgroup$
1
$\begingroup$

Note that if the dealer in broadcast is corrupted, then we don't need to guarantee anything except that all honest parties agree on the output. In contrast, if the dealer is honest, then all honest parties must output the dealer's input. Now, think about what happens if the dealer is instructed to send its input first to all parties over the point-to-point channel. What can the parties do after receiving this message (note that a corrupted dealer can send different values to different parties)? How can they ensure the properties... Of course, you should use agreement. I think that this is more than enough of a hint.

$\endgroup$
  • $\begingroup$ Thank you for the hint. I found another pdf file with some more information. Your hint and the PDF will help me. As soon I have a result I will post it for everyone. $\endgroup$ – Donut Jun 18 '17 at 9:24

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.