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

文章基本信息

  • 标题:A Tight Parallel-Repetition Theorem for Random-Terminating Interactive Arguments
  • 本地全文:下载
  • 作者:Itay Berman ; Iftach Haitner ; Eliad Tsfadia
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-111
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Soundness amplification is a central problem in the study of interactive protocols. While ``natural'' parallel repetition transformation is known to reduce the soundness error of some special cases of interactive arguments: three-message protocols and public-coin protocols, it fails to do so in the general case.The only known round-preserving approach that applies to the general case of interactive arguments is Haitner's "random-terminating" transform [FOCS '09, SiCOMP '13]. Roughly speaking, a protocol is first transformed into a new slightly modified protocol , referred as the random terminating variant of , and then parallel repetition is applied. Haitner's analysis shows that the parallel repetition of does reduce the soundness error at a weak exponential rate. More precisely, if has m rounds and soundness error 1 − , then k , the k -parallel repetition of , has soundness error (1 − ) k m 4 . Since the security of many cryptographic protocols (e.g., binding) depends on the soundness of a related interactive argument, improving the above analysis is a key challenge in the study of cryptographic protocols.In this work we introduce a different analysis for Haitner's method, proving that parallel repetition of random terminating protocols reduces the soundness error at a much stronger exponential rate: the soundness error of k is (1 − ) k m , only an m factor from the optimal rate of (1 − ) k , achievable in public-coin and three-message protocols. We prove the tightness of our analysis by presenting a matching protocol.

  • 关键词:parallel repetition; interactive argument; smooth KL-divergence
国家哲学社会科学文献中心版权所有