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

文章基本信息

  • 标题:Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation
  • 本地全文:下载
  • 作者:Mitali Bafna ; Badih Ghazi ; Noah Golowich
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2018
  • 卷号:2018
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples X 1 X 2 and Y 1 Y 2 with the pairs ( X 1 Y 1 ) , ( X 2 Y 2 ) , being drawn independently from some known probability distribution . They wish to communicate so as to agree on L bits of randomness. The SKG problem is the restriction of the CRG problem to the case where the key is required to be close to random even to an eavesdropper who can listen to their communication (but does not have access to the inputs of Alice and Bob). In this work, we study the relationship between the amount of communication and the number of rounds of interaction in both the CRG and the SKG problems. Specifically, we construct a family of distributions = r n L , parametrized by integers r , n and L , such that for every r there exists a constant b = b ( r ) for which CRG (respectively SKG) is feasible when ( X i Y i ) r n L with r + 1 rounds of communication, each consisting of O ( log n ) bits, but when restricted to r 2 − 3 rounds of interaction, the total communication must exceed ( n log b ( n )) bits. Prior to our work no separations were known for r 2 .

  • 关键词:Common Randomness Generation ; Communication complexity ; round complexity ; secret key agreement
国家哲学社会科学文献中心版权所有