Abstract
Modern communication applications like blockchain consensus, cyber-physical systems and IoTs pose new security challenges. These applications require networks consisting of interconnected nodes of varying security levels. A faulty (or byzantine) node in such systems can cause communication failure for other nodes in the system as they all share the same communication medium. This dissertation considers communication in networks with byzantine users, specifically, broadcast (single sender with a common message to multiple receivers) and the multiple access (multiple senders with different messages to a single receiver).
In the first part of the dissertation (Chapters 2 and 3), we focus on realizing a cryptographic primitive called the byzantine broadcast, which ensures consensus among honest nodes in a network with one sender and multiple receivers. We use stochastic resources (like correlated randomness or a noisy channel) to realize this primitive. In the second part of this dissertation (Chapters 4, 5 and 6), we consider a noisy channel with multiple senders and a single receiver (also called a multiple access channel) where some of the senders may maliciously deviate from the protocol. We study communication in this model while ensuring that malicious senders are not able to cause undetected decoding errors for the honest senders.