Secure message transmission on directed networks

• 成果类型: Article
• 署名作者: Renault, Jerome; Renou, Ludovic; Tomala, Tristan
• 署名单位: Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; University of Essex; Hautes Etudes Commerciales (HEC) Paris
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2014.01.012
• 发表日期: 2014
• 页码: 1-18
• 关键词: Secure communication; Protocols; COMMUNICATION

摘要

A sender wishes to transmit a secret to a receiver through a communication network, where some nodes are controlled by an adversary. We characterize the directed networks for which there exist epsilon-secret and epsilon-strongly secure communication protocols (for all epsilon > 0): if all nodes are obedient the receiver learns the secret with probability at least 1 - epsilon and no information is leaked (secrecy), and this property is maintained under every strategy of the adversary (security). For secrecy, a necessary and sufficient condition is that there is a directed path from the sender to the receiver, and for each possible adversarial coalition A, there is an undirected path from the sender to the receiver that contains no node in A. For security, a necessary and sufficient condition is that for every possible adversarial coalition A, the graph obtained by removing all nodes in A still has the previous property. (C) 2014 Elsevier Inc. All rights reserved.