• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Theory of cryptography >Authenticated Adversarial Routing
【24h】

Authenticated Adversarial Routing

机译：认证对抗路由

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The aim of this paper is to demonstrate the feasibility of authenticated throughput-efficient routing in an unreliable and dynamically changing synchronous network in which the majority of malicious insiders try to destroy and alter messages or disrupt communication in any way. More specifically, in this paper we seek to answer the following question: Given a network in which the majority of nodes are controlled by a node-controlling adversary and whose topology is changing every round, is it possible to develop a protocol with polynomially-bounded memory per processor that guarantees throughput-efficient and correct end-to-end communication? We answer the question affirmatively for extremely general corruption patterns: we only request that the topology of the network and the corruption pattern of the adversary leaves at least one path each round connecting the sender and receiver through honest nodes (though this path may change at every round). Out construction works in the public-key setting and enjoys bounded memory per processor (that is polynomial in the network size and does not depend on the amount of traffic). Our protocol achieves optimal transfer rate with negligible decoding error. We stress that our protocol assumes no knowledge of which nodes are corrupted nor which path is reliable at any round, and is also fully distributed with nodes making decisions locally, so that they need not know the topology of the network at any time.rnThe optimality that we prove for our protocol is very strong. Given any routing protocol, we evaluate its efficiency (rate of message delivery) in the "worst case," that is with respect to the worst possible graph and against the worst possible (polynomially bounded) adversarial strategy (subject to the above mentioned connectivity constraints). Using this metric, we show that there does not exist any protocol that can be asymptotically superior (in terms of throughput) to ours in this setting.rnWe remark that the aim of our paper is to demonstrate via explicit example the feasibility of throughput-efficient authenticated adversarial routing. However, we stress that out protocol is not intended to provide a practical solution, as due to its complexity, no attempt thus far has been made to reduce constants and memory requirements.rnOur result is related to recent work of Barak, Goldberg and Xiao in 2008 [9] who studied fault localization in networks assuming a private-key trusted setup setting. Our work, in contrast, assumes a public-key PKI setup and aims at not only fault localization, but also transmission optimality. Among other things, our work answers one of the open questions posed in the Barak et. al. paper regarding fault localization on multiple paths. The use of a public-key setting to achieve strong error-correction results in networks was inspired by the work of Micali, Peikert, Sudan and Wilson [14] who showed that classical error-correction against a polynomially-bounded adversary can be achieved with surprisingly high precision. Our work is also related to an interactive coding theorem of Rajagopalan and Schulman [15] who showed that in noisy-edge static-topology networks a constant overhead in communication can also be achieved (provided none of the processors are malicious), thus establishing an optimal-rate routing theorem for static-topology networks.rnFinally, our work is closely related and builds upon to the problem of End-To-End Communication in distributed networks, studied by Afek and Gafni [1], Awebuch, Mansour, and Shavit [8], and Afek, Awerbuch, Gafni, Mansour, Rosen, and Shavit [2], though none of these papers consider or ensure correctness in the setting of a node-controlling adversary that may corrupt the majority of the network.
机译：本文的目的是证明在不可靠且动态变化的同步网络中进行身份验证的吞吐量高效路由的可行性，在该网络中，大多数恶意内部人员试图以任何方式破坏和更改消息或破坏通信。更具体地说，在本文中，我们试图回答以下问题：假设在一个网络中，多数节点由节点控制对手控制，并且其拓扑结构每轮都在变化，那么是否有可能开发出具有多项式边界的协议每个处理器的内存可确保吞吐效率和正确的端到端通信？对于极端普遍的腐败模式，我们肯定地回答了这个问题：我们仅要求网络的拓扑结构和对手的腐败模式每轮至少留下一条通过诚实节点连接发送方和接收方的路径（尽管该路径可能会在每一次更改回合）。 Out结构以公钥设置工作，并享受每个处理器的有限内存（即网络大小的多项式，而不取决于通信量）。我们的协议以最小的解码误差实现了最佳传输速率。我们强调说，我们的协议不假设哪个节点损坏，也不知道哪个路径在任何时候都是可靠的，并且还与节点本地决策一起完全分布，因此他们不需要随时了解网络拓扑。我们证明我们的协议非常强大。给定任何路由协议，我们在“最坏情况”下评估其效率（消息传递率），即相对于最差的图以及针对最坏的可能（多项式有界）的对抗策略（受上述连接性约束） ）。使用此度量，我们表明在这种情况下不存在任何可以在渐近上优于（就吞吐量而言）的协议.rn我们注意到本文的目的是通过显式示例来证明吞吐效率的可行性经过身份验证的对抗式路由。但是，我们强调out协议并非旨在提供一种实用的解决方案，因为其复杂性，迄今为止尚未尝试减少常量和内存需求。rn我们的结果与Barak，Goldberg和Xiao的最新工作有关。 2008 [9]谁研究了网络中的故障定位，并假设使用了私钥受信任的设置。相比之下，我们的工作假设使用公共密钥PKI设置，不仅针对故障定位，而且针对传输最优性。除其他事项外，我们的工作回答了Barak等人提出的一个开放性问题。等关于多路径故障定位的论文。 Micali，Peikert，Sudan和Wilson [14]的工作启发了使用公钥设置在网络中实现强大的纠错结果，他们证明，利用多项式约束的对手可以实现经典的纠错。惊人的高精度。我们的工作还涉及Rajagopalan和Schulman [15]的交互式编码定理，他们证明，在嘈杂的边缘静态拓扑网络中，也可以实现恒定的通信开销（只要没有处理器是恶意的），从而建立了一个最后，我们的工作密切相关，并以Afek和Gafni [1]，Awebuch，Mansour和Shavit研究的分布式网络中的端到端通信问题为基础。 [8]，以及Afek，Awerbuch，Gafni，Mansour，Rosen和Shavit [2]，尽管这些论文都没有考虑或确保节点控制对手设置的正确性，这可能会破坏大多数网络。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号