首页    期刊浏览 2024年12月03日 星期二
登录注册

文章基本信息

  • 标题:Locally Testable Non-Malleable Codes
  • 本地全文:下载
  • 作者:Silas Richelson ; Sourya Roy
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-32
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In this work we adapt the notion of non-malleability for codes or Dziembowski, Pietrzak and Wichs (ICS 2010) to locally testable codes. Roughly speaking, a locally testable code is non-malleable if any tampered codeword which passes the local test with good probability is close to a valid codeword which either encodes the original, or an unrelated message. We instantiate our definition by proving that a Reed-Muller-type code is non-malleable in the following sense: any adversary who independently tampers the coordinates of the code so that the tampered code passes the test with good probability, is tampering the underlying polynomial according to an affine transformation. To the best of our knowledge, prior to this work, polynomial codes were not known to possess any non-malleability guarantees. Our analysis builds on the sampler-based decoding techniques common to several recent works.

  • 关键词:local testing ; non;malleable code
国家哲学社会科学文献中心版权所有