International Association for Cryptologic Research

International Association
for Cryptologic Research


Prasant Gopal


Authenticated Byzantine Generals Strike Again
Pease {\em et al.}\/ introduced the problem of \emph{Authenticated Byzantine General} (ABG) where players could use digital signatures (or similar tools) to thwart the challenge posed by Byzantine faults in distributed protocols for agreement. Subsequently it is well known that ABG among $n$ players tolerating up to $t$ faults is (efficiently) possible if and only if $t < n$ (which is a huge improvement over the $n > 3t$ condition in the absence of authentication for the same functionality). However, in this paper we argue that the extant result of $n>t$ does not \emph{truly} simulate a broadcast channel as intended. Thus, we re-initiate the study of ABG. We show that in a completely connected synchronous network of $n$ players where up to any $t$ players are controlled by an adversary, ABG is possible if and only if $n > 2t-1$. The result is pleasantly surprising since it deviates from the standard template of ``$n > \beta t$" for some integer $\beta$, particularly $\beta = 1,2$ or $3$. The result uses new proof/design techniques which may be of independent interest.
Topology Knowledge Versus Fault Tolerance: The Case of Probabilistic Communication Or: How Far Must You See to Hear Reliably?
We consider the problem of probabilistic reliable communication (PRC) over synchronous networks modeled as directed graphs in the presence of a Byzantine adversary when players' knowledge of the network topology is not complete. We show that possibility of PRC is extremely sensitive to the changes in players' knowledge of the topology. This is in complete contrast with earlier known results on the possibility of perfectly reliable communication over undirected graphs where the case of each player knowing only its neighbours gives the same result as the case where players have complete knowledge of the network. Specifically, in either case, $2t+1$-vertex connectivity is necessary and sufficient, where $t$ is the number of nodes that can be corrupted by the adversary [1][2]. We use a novel model for quantifying players' knowledge of network topology, denoted by {$\mathcal K$}. Given a directed graph $G$, influenced by a Byzantine adversary that can corrupt up to any $t$ players, we give a necessary and sufficient condition for possibility of PRC over $G$ for any arbitrary topology knowledge {$\mathcal K$}. As a corollary, we answer the question: {\em Up to what neighbourhood level $\ell$ must the players know for the possibility of PRC} where, a player is said to know up to neighbourhood level: $1$ - if it knows only its neighbours; $2$ - if it knows its neighbours and its neighbours' neighbours and so on. [1] Subramanian, L., Katz, R. H., Roth, V., Shenker, S., and Stoica, I. 2005. Reliable broadcast in unknown fixed-identity networks. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing (Las Vegas, NV, USA, July 17 - 20, 2005). PODC '05. ACM, New York, NY, 342-351. [2] DOLEV, D. The byzantine generals strike again. In Journal of Algorithms (1982), pp. 14–30.