Rafael Pass2014-05-23 4:47 PM

回合常数中的有界并行安全两方计算 Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds 

论文摘要

我们考虑了并行构成下保证安全的构建两方安全计算的通用协议的问题。在我们处理方案中,我们把重点放在协议被构造前已被指定的并行话路数中的先验界限案例(又名有界并行机制)。我们不作任何设置假设。
Lindell(2003 STOC)已经表明,任何安全性通过黑箱模拟而建立的有界并发安全两方计算的协议,必须具有严格大于回合并行会话数的回合复杂性。在本文中,我们构造了用于在回合常数中实现有界并发安全两方计算的(非黑箱)协议。 能实现上述任务的先前已知的协议需要比预先指定边界更多有关会话数量的回合(尽管使用了非黑箱模拟技术)。

我们的构建依赖于增强的陷门排列的存在以及关于耐碰撞次指数大小回路的散列函数的存在。

Abstract 

We consider the problem of constructing a general protocol for secure two-party computation in a way that preserves security under concurrent composition. In our treatment, we focus on the case where an apriori bound on the number of concurrent sessions is specified before the protocol is constructed (a.k.a. bounded concurrency). We make no set-up assumptions. 

Lindell (STOC 2003) has shown that any protocol for bounded-concurrent secure two-party computation, whose security is established via black-box simulation, must have round complexity that is strictly larger than the bound on the number of concurrent sessions. In this paper, we construct a (non black-box) protocol for realizing bounded-concurrent secure two-party computation in a constant number of rounds. The only previously known protocol for realizing the above task required more rounds than the pre-specified bound on the number of sessions (despite usage of non black-box simulation techniques). 

Our constructions rely on the existence of enhanced trap- door permutations, as well as on the existence of hash functions that are collision-resistant against subexponential sized circuits.

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