.png){kind=icon}
返回
Instance-Hiding Interactive Proofs
.png){kind=icon}
PRE
AI
DOI：10.1007/s00145-026-09573-w.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
在实例隐藏交互式证明（IHIP）（Beaver等人，载于Menezes和Vanstone主编的《密码学进展-CRYPTO 1990论文集》，计算机科学讲义笔记（包括人工智能和生物信息学子系列讲义笔记），Springer出版社，第326-338页，1990年）中，一个具有私有输入x的高效验证者与无界证明者交互，以确定x是否包含在语言L中。除完备性和可靠性外，实例隐藏属性要求证明者在交互过程中不得获知x的任何信息。此类证明系统捕获了自然的隐私属性，可被视为随机编码这一重要概念的推广（Ishai和Kushilevitz，载于第41届计算机科学基础年会论文集，第294-304页，2000年；Applebaum等人，载于第45届IEEE计算机科学基础年会论文集，第166-175页，2004年；Agrawal等人，载于Halldórsson、Iwama、Kobayashi和Speckmann主编的《自动机、语言与编程》，Springer出版社，柏林，海德堡，第1-13页，2015年），并作为零知识证明的对偶（Goldwasser等人，载于计算理论研讨会，1985年）。我们研究了此类实例隐藏证明的性质和功能，并证明了以下结论：任何具有IHIP的语言都包含于NP/poly布尔与coNP/poly中。如果一个平均情况困难的语言具有常数轮次的IHIP，那么存在无限次数的非均匀单向函数。存在一个相对于某个预言机的语言，该语言具有IHIP但没有SZK证明。IHIP在组合任何高效可计算函数时是封闭的。我们进一步研究了一种更强的IHIP版本（我们称之为可模拟IHIP），其中诚实证明者的视图可以被高效模拟。对于这些版本，我们得到了上述某些结论的更强版本：任何具有可模拟IHIP的语言都包含于AM布尔与coAM中。如果一个最坏情况困难的语言具有可模拟IHIP，那么存在明确的均匀单向函数。
Keyword:
Interactive Proofs
Instance-hiding
