Rafael Pass2014-05-23 4:28 PM

知识保留交互编码 Knowledge-Preserving Interactive Coding 

论文摘要


我们如何编码双方之间的通信协议才能抵御通信信道中的对抗性误差?如果我们在通信协议中用“好”的纠错码(ECC)来编码每个消息,则 编码协议的误差率将会变差(如O(1/m)中的m表示通讯回合数目)。致力于解决这个问题,Schulman(FOCS'92,STOC'93)给出了交互编码的概念。我们认为用ECC单独编码每条信息的方法保证了编码协议作为原协议携带相同信息量, 如果使用互动式编码则可能无法做相同保证。特别来说,该编码协议可能完全泄漏某一玩家的隐私输出,即使它在原来协议中仍受保密。为了解决这个问题,我们介绍了知识保留互动编码的概念,在该概念中要求互动编码协议保留在原协议中传输的“知识”。我们的主要结果如下。


• 在每条消息中单独应用ECC的方法基本具有最佳误差率:没有知识保留交互编码方案能具有1 / m误差率,其中m表示原协议回合数。


•如果限制于计算有界(多项式时间)的对手,我们假设每个ε> 0具有单向函数(相应次指数硬单向函数),且存在具有常误差率和信息率为n−ε (resp. 1/polylog(n))的知识保留交互编码方案,其中n为安全参数; 另外要实现1 / m的误差则需要存在单向函数。 


•最后,即使我们只限于计算有界的对手,具有常误差率的知识保留互动编码方案可具有至多为o(1/ log n)的信息速率。 该结果甚至适用于非建设性交互编码方案。


Abstract 


How can we encode a communication protocol between two parties to become resilient to adversarial errors on the communication channel? If we encode each message in the commu- nication protocol with a “good” error-correcting code (ECC), the error rate of the encoded protocol becomes poor (namely O(1/m) where m is the number of communication rounds). To- wards addressing this issue, Schulman (FOCS’92, STOC’93) introduced the notion of interactive coding. 

We argue that whereas the method of separately encoding each message with an ECC ensures that the encoded protocol carries the same amount of information as the original protocol, this may no longer be the case if using interactive coding. In particular, the encoded protocol may completely leak a player’s private input, even if it would remain secret in the original protocol. Towards addressing this problem, we introduce the notion of knowledge-preserving interactive coding, where the interactive coding protocol is required to preserve the “knowledge” transmitted in the original protocol. Our main results are as follows. 

• The method of separately applying ECCs to each message has essentially optimal error rate: No knowledge-preserving interactive coding scheme can have an error rate of 1/m, where m is the number of rounds in the original protocol. 

• If restricting to computationally-bounded (polynomial-time) adversaries, then assuming the existence of one-way functions (resp. subexponentially-hard one-way functions), for every ε > 0, there exists a knowledge-preserving interactive coding schemes with constant error rate and information rate n−ε (resp. 1/polylog(n)) where n is the security parameter; additionally to achieve an error of even 1/m requires the existence of one-way functions. 

• Finally, even if we restrict to computationally-bounded adversaries, knowledge-preserving interactive coding schemes with constant error rate can have an information rate of at most o(1/ log n). This results applies even to non-constructive interactive coding schemes. 

KEYWORDS

SHARE & LIKE

COMMENTS

ABOUT THE AUTHOR

Rafael Pass

0 Following 0 Fans 0 Projects 14 Articles

SIMILAR ARTICLES

论文摘要Goldreich和Oren (JoC’94)表明只有平凡的语言才具有两轮的零知识的论点。在本说明中,我们考虑超多项式时间的模拟(SPS),弱零知识概念。通过 满足SPS零知识的高效验证者策略,我们设置障碍来使用黑盒减少来证实两轮的协议的稳健性。更精确地说,我们表明假设T (n)硬多项式单向函

Read More

论文摘要我们如何编码双方之间的通信协议才能抵御通信信道中的对抗性误差?如果我们在通信协议中用“好”的纠错码(ECC)来编码每个消息,则 编码协议的误差率将会变差(如O(1/m)中的m表示通讯回合数目)。致力于解决这个问题,Schulman(FOCS'92,STOC'93)给出了交互编码的概念。我们认为

Read More

论文摘要Brandenburger和Dekel表明理性的共同信念(CBR)和所谓后验均衡的主观相关均衡的完善描绘了理性化策略。这可能是玩家信仰是不相容的,在该意义上,玩家i可以将概率1分配给事件E,而参与者分配给它概率0。阻止不相容性的一种方法是假设一个普通先验。我们在此考虑不同的方法:我们要求玩家持

Read More

论文摘要我们引入了所谓群体混合隐私的新定义,即严格放宽不同隐私的概念。粗略地说,数据库的K-群体混合的隐私处理要求数据库中的每个个体i与数据库中的其他k个个体j“混合”,意为假如i的数据被j的所替代,则处理的输出结果为“不能区分”。我们展示了直方图和用于释放合成数据点的群体混合隐私机制,这使得比起使用

Read More

论文摘要考虑具有稳健误差1 /2的m回合交互式协议。需要多少通过并行重复的额外随机性来降低稳健误差δ?由Bellare,Goldreich和Goldwasser发起的以往研究工作表明具有统计稳健性的公共硬币互动协议,具有m · O(log(1/δ))位数的额外随机性就足够了。在这项工作中,我们发起了对

Read More

论文摘要我们构建了除已验证通信外不需要信任的基础设施以及满足有关在通用组成下(假设只存在增强的陷门排列)受保护的安全性的有意义概念的首次安全计算协议。安全性概念与Prabhakaran和Sahai“angel-based”框架( STOC'04 )的广泛化相契合并表明了超多项式时间模拟安全性。目前已知

Read More

论文摘要我们提出了定时模型中的新的高效并发零知识协议。相对于通过人为强加的延迟来要求每个协议实行以网络最慢链接速度运行的早期作品来说,我们的协议基本上只推迟基于每个验证者实际响应时间的消息(甚至可以显著更少)。 Abstract We present new and efficient concurr

Read More

论文摘要我们表明只有BPP语言具有在平行重复的无界(多项式)数目下安全的公用硬币黑箱零知识协议。这一结果同时在原始模型(不带任何设置)和在Bare公钥模型中都成立(其中认证者和检验者已注册了公共密钥)。我们基于在任何并发执行的先验界数下保持安全的单向函数,通过构建公用硬币黑箱零知识证明将这一结果进行了

Read More

论文摘要我们介绍了普遍复杂性理论硬度新假设。这些假设将随机预言的具体性能进行抽象化并且显著比传统加密硬度假设更强; 然而假设其有效性,我们可以解决在密码学中一些长期存在的开放性问题。Abstract We introduce new and general complexity theoretic h

Read More

论文摘要我们提出了精确零知识的概念并提供其在标准复杂性假设下各种设置的首次实现。零知识的经典概念在参与者潜在计算能力方面界定了他的知识(技术上定义为多项式时间计算),而精确零知识则界定了在实际计算方面参与者获得的知识(可以远远小于任意多项式时间计算)。Abstract We put forward t

Read More