Interactive code to correct and detect omniscient Byzantine adversaries
Zhiqing Xiao, Yunzhou Li, Ming Zhao, Jing Wang · 2014
This paper considers interactive transmissions in the presence of omniscient Byzantine attacks. Unlike prior papers, it is assumed that the number of transmissions, the number of erroneous transmissions therein, and the direction of each transmission are predetermined. Besides, the size of the alphabet in each transmission is unequal and predefined. Using these transmissions, two nodes communicate interactively to send a message. In this model, both attack strategies and coding bounds are considered. Although the codebook can not fully describe the interactive code, we still assert the existence of successful attack strategies according to the relations between codewords in the codebook. Furthermore, to ensure that the code is able to detect or correct a given number of transmission errors, upper bounds on the size of code are derived. Finally, the tightness of the bounds is discussed.