首页    期刊浏览 2024年08月31日 星期六
登录注册

文章基本信息

  • 标题:Private Computation --- k-connected versus 1-connected Networks
  • 本地全文:下载
  • 作者:Markus Bläser ; Andreas Jakoby ; Maciej Liskiewicz
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2003
  • 卷号:2003
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:We study the role of connectivity of communication networks in private computations under information theoretic settings. It will be shown that some functions can be computed by private protocols even if the underlying network is 1-connected but not 2-connected. Then we give a complete characterisation of non-degenerate functions that can be computed on non-2-connected networks. Furthermore, a general technique for simulating private protocols on arbitrary networks will be presented. Using this technique every private protocol can be simulated on arbitrary k -connected networks using only a small number of additional random bits. Finally, we give matching lower and upper bounds for the number of random bits needed to compute the parity function on k -connected networks.
  • 关键词:cryptography , Distributed algorithms , Private computation
国家哲学社会科学文献中心版权所有