零知识证明及承诺协议的不可延展性研究
|
摘要
上世纪七、八十年代,现代密码学迎来了蓬勃发展的新时期,产生了诸如公钥密码学、交互证明系统、伪随机发生器等一系列具有里程碑式意义的成果,并开启了现代密码学与计算复杂性理论相结合的道路。Goldwasser在1997年FOCS会议上曾发表了题为"Cryptography and Complexity Theory:A Match Made in Heaven"的特邀报告,她指出：现代密码学最重大的进展是将密码学建立在计算复杂性的基础之上,并且正是计算复杂性理论将密码学从一门艺术发展成为一门严谨的科学。而零知识证明则是密码学和复杂性理论相互交织、相互促进的最好见证。
简言之,零知识证明系统是一个两方交互协议,其中证明者通过交互来向验证者证明某一个断言,并且确保不向验证者泄露任何额外的信息。零知识证明自提出以来一直处于密码学的中心位置,对密码学的发展起到关键作用。首先,零知识证明为密码协议安全性的形式化分析奠定了基础,其基于模拟不可区分性的证明思想已成为可证明安全理论的核心。更重要的是,零知识证明看似矛盾的独特性质令其集“保密性”和“认证性”于一身,因此广泛应用于各类密码算法和密码协议的构造,例如身份认证协议、抗选择密文攻击安全的加密方案、以及抵抗恶意敌手的安全多方计算协议。
作为构造零知识证明系统以及其他安全计算协议的一个基本组件,承诺的思想先于零知识证明而被学者们用于设计电话投币、虚拟扑克等协议,并最终由Brassard等人给出了形式化的定义以及“承诺(commitment)"这个形象的名称。简言之,承诺协议是一类两方参与的两阶段交互协议。首先在承诺阶段,承诺者对一个字符串v承诺,发送给接收者,并且确保接受者得不到关于v的任何信息；随后在打开阶段,承诺者公开v,并证明其与第一阶段的一致性。承诺协议的两个基本性质分别称为隐藏性和绑定性。所谓隐藏性,是指在承诺阶段任意恶意的接收者都不能获取承诺字符串的信息；而绑定性是指在打开阶段,任意恶意的承诺者都不能将承诺打开为另外一个值,并且通过验证。
在密码协议的设计中,承诺协议通常作为子协议来构造更为复杂的安全计算协议,其主要作用是固定参与者的输入,同时保证其隐私性。它通常与零知识证明系统配合来实现抵抗恶意敌手的安全多方计算协议。另外,承诺协议与零知识证明系统存在着内在的联系,并且两者的研究总是相互促进,共同发展的。
近年来,随着互联网的兴起,密码协议在并发、异步的网络环境下的面临着更多的安全性冲击,协议基本的安全属性已经不足以应对复杂的网络环境和应用。如何建立合理的协议安全模型,以及设计满足更高安全性需求、适用于互联网应用的密码协议逐渐成为了密码学界关注的热点问题。
其中,并发不可延展性定义了零知识证明及承诺协议在多次并发执行的过程中抵抗中间人攻击的能力。以零知识证明为例,考虑如下情景：一个中间人敌手并发的参与多个会话,执行同一个零知识证明协议,在其中一部分会话中,敌手作为验证者接收并验证诚实证明者对某些断言的证明,而在另一部分会话中,敌手作为证明者与诚实的验证者交互,试图构造对相关断言的证明。能够抵抗上述并发中间人攻击的零知识证明或者承诺协议称为并发不可延展的。研究者普遍认为,并发不可延展性在最大程度上反映了协议在开放网络环境下所要达到的安全性要求。
本文的研究主要围绕并发不可延展的零知识证明系统以及承诺方案而展开,重点在与协议鲁棒性研究,具体包括以下方面：
●关于并发不可延展的零知识
近期,Lin等人将承诺协议的不可延展性扩展到更一般化的形式,称为对任意k-轮协议的不可延展性,讨论承诺协议在以下场景中的安全性：敌手在左侧会话中参与任意一个k-轮协议,而在右侧与多个接收者交互,执行某个承诺协议。k-不可延展性反应了一个承诺协议与其他协议组合执行时的鲁棒性,即一个k-不可延展的承诺可以与任意轮数不超过k的协议组合执行,而不影响其安全性。因此,当与其他协议组合执行时,此类承诺协议的不可延展性更易于分析。本文受上述文献所启发,研究并发不可延展零知识的鲁棒性。在已有的不可延展零知识协议中,一部分使用了非黑盒的模拟机制,而缺乏鲁棒性正是非黑盒模拟机制自身的限制,尤其在并发环境下；另一部分虽然采用的黑盒模拟,但都是基于Goldreich-Kahan结构而构造,包含一个零知识子协议。由于零知识在并发组合下并不封闭,因此这些协议的鲁棒性难于分析。为此,本文提出了第一个具有鲁棒性并发不可延展零知识论证系统,具有如下特点：
a)基于Feige-Shamir结构而构造,以具有鲁棒性的不可延展承诺协议以及巧妙设计的证据不可区分证明系统来实现零知识,并确保整个协议的鲁棒性。
b)采用“茫然模拟(oblivious simulation)"的策略来模拟敌手的视图。
c)在单向函数假设下,拥有最优的轮复杂度,即超对数。
d)通过适当调整子协议的轮数,可以实现与任意协议的组合。
●关于并发不可延展的承诺
承诺协议的不可延展性针对其两个阶段分别定义,即关于承诺阶段的不可延展性以及关于打开阶段的不可延展性,分别描述了两个阶段相对于自身的独立性。近期,在TCC’09的一项工作中,Ostrovsky等人研究了这两类不可延展性之间的关系,并指出,在基于模拟的不可延展性定义下,承诺阶段的不可延展性并不一定蕴含打开阶段的不可延展性,因此设计同时满足这两种性质的承诺协议具有重要的理论意义。文中同时构造了一个计算隐藏且计算绑定的承诺方案,同时满足承诺阶段和打开阶段的并发不可延展性。此后,在PKC'10中,Cao等人将该方案扩展并得到一个统计绑定的版本。然而,上述两方案(以及几乎所有已知的不可延展承诺方案)都存在一个共同的限制：承诺阶段和打开阶段在时间上不可重叠。因此,如何构造一个两阶段可重叠的完全并发不可延展的承诺方案仍然是一个公开问题。
为此,本文作了如下工作：
a)分析并指出在目前的不可延展性定义下,上述问题无法解决。同时,本文给出了一个新的并发不可延展性定义,它与原定义在本质上相同,但适用于两阶段可重叠的承诺协议。
b)分析了上述问题存在的原因,并在此基础上构造了一个计算绑定且计算隐藏的承诺方案,同时满足承诺阶段和打开阶段的并发不可延展性,并且允许两阶段可重叠,解决了上述公开问题。在单向函数假设下,该方案的承诺阶段和打开阶段的轮复杂性均为超对数。
In the last seventies and eighties, the research of modern cryptography has ushered in a new era of vigorous development, in which a series of milestone achievements, such as public key cryptography, interactive proof system and pseudo-random generators, have emerged, opening up the way of combining cryptography with complexity theory. In the FOCS'97conference, Goldwasser gives an invited talk with the tile "Cryptography and Complexity Theory:A Match Made in Heaven", and points out that, the most important progress made in modern cryptography is basing this field on complexity theory, and it is complexity theory that has transformed cryptography from an art to a rigorous science. Moreover, zero-knowledge is the best witness of the intertwining and cross-promoting between cryptography and complexity theory.
Informally speaking, a zero-knowledge proof system is a two-party interactive protocol, in which a prover tries to convince a verifier the correctness of a statement, but ensures that the verifier learns no extra information during the interactive procedure. Zero-knowledge has been at the heart of cryptography since its invention, and plays a key role in the development of cryptography. First, zero-knowledge laid the foundation for the formal analysis of cryptographic protocols, and its simulation-based way of security proofs have become the core of provable security theory. More importantly, the seemingly contradictory nature enables zero-knowledge proof system to integrate "privacy" and "authentication" within the single primitive, which results in a wide array of applications, such as identification protocols, encryption schemes secure against chosen ciphertext attack, and secure multi-party protocols against malicious adversaries.
As a fundamental building block of zero-knowledge proof system and other secure protocols, the idea of a commitment scheme (sealed envelope) appears earlier than zero-knowledge in the design of protocols for coin-tossing by telephone, mental poker and so on. Finally, it is formally defined by Brassard et al. and gets the vivid name of "commitment". Roughly speaking, a commitment scheme is a two-phase interactive protocol between two parties. First in the commit phase, the committer commits himself to a string (say v), and sends the commitment to the receiver, while ensuring that the receiver knows nothing about v; then in the reveal phase, the committer publishes v, and proves it is consistent with the messages in the first stage. Two basic properties of commitment scheme are known as hiding and binding, in which hiding says that, in the commit phase no malicious receiver can get any information about the secret string v, and binding says that, in the reveal phase no malicious committer can open the commitment to another value successfully while passing the decomitment verification.
In the research of cryptographic protocols, commitment schemes are often used as sub-protocols to build more complex ones, in which they are taken to fix the inputs of the participants as well as keep their privacy. Furthermore, they usually cooperate with zero-knowledge proof systems to achieve secure multi-party protocols against malicious adversaries. Besides, there exit inherent relations between commitment schemes and zero-knowledge proof systems, so that the researches in both areas are always proceeding hand-in-hand.
In recent years, with the rapid development of internet, cryptographic protocols that run in the concurrent and asynchronous network encounter more and more security challenges, so that the basic security properties of protocols are not sufficient to cope with the complex network applications. Therefore, how to build reasonable security models and design cryptographic protocols that enjoy higher security and apply to the internet applications has been one of the attractive areas in cryptography.
Concurrent non-malleability defines the security property of zero-knowledge proof systems as well as commitment schemes against "man-in-the-middle" attack, when executing multi times concurrently. Taking zero-knowledge for example, consider the follow scenario:a man-in-the-middle adversary concurrently participates many sessions running the same zero-knowledge protocol, in some of which the adversary plays the role of verifier receiving and verifying proofs of some statements given by the honest provers, while in others the adversary interacts with the honest verifiers as a prover trying to construct proofs of some related statements, Zero-knowledge proof systems and commitment schemes secure against the above concurrent man-in-the-middle attack are called concurrent non-malleable. It is generally believed that, concurrent non-malleability is most suitable for modeling the security requirements in the open network.
In this paper, we investigate concurrent non-malleable zero-knowledge as well as commitment schemes, and focus mainly on the robustness of protocols. Specifically, we work on the following points:
·On concurrent non-malleable zero-knowledge
Recently, Lin et al. extends the original non-malleability of commitment schemes to a more general form called non-malleability with respect to arbitrary k-round protocol (or k-non-malleability for short), studying the security of commitments in the following scenario:the man-in-the-middle adversary participates one left session running an arbitrary k-round protocol, and multi right sessions interacting with a set of honest receivers and executing a commitment scheme. Loosely speaking, k-non-malleability shows the robustness of a commitment scheme when composed with other protocols. That is, a k-non-malleable commitment scheme can be composed with any protocols with no more than k rounds, and does not affect its security. Hence, this kind of protocol is easier to analyze when concurrently composed with other protocols.
Highly inspired by the above literature, we turn to study the robustness of concurrent non-malleable zero-knowledge. In the existing concurrent non-malleable zero-knowledge protocols, some rely on non-black-box simulation technique. However, as we know that, less robustness is the inherent limitation of non-black-box techniques, let alone in the concurrent setting. Besides, all the other constructions applying black-box simulation follows the Goldreich-Kahan style incorporating a zero-knowledge sub-protocol, which makes robustness hard to argue (sine zero-knowledge is not closed under concurrent composition).
In this paper, we present the first robust concurrent non-malleable zero-knowledge argument system that enjoys the properties below:
a) Following the Feige-Shamir style, takes robust non-malleable commitment and specifically designed witness indistinguishable proofs as basic components to achieve zero-knowledge, and at the same time ensures the robustness of the whole protocol.
b) Applies the "oblivious simulation" strategy to emulate the view of the adversary.
c) Achieves optimal (super-logarithmic) round complexity under the minimal assumption of one-way functions.
d) Can be composed with any protocols by appropriately adjusting the round complexity of the sub-protocols.
·On concurrent non-malleable commitments
The non-malleability of commitment schemes are defined respectively for each stage, i.e. non-malleability with respect to commitment and non-malleability with respect to decommitment, describing the independence of each stage with respect to itself separately. In a recent work in TCC'09, Ostrovsky et al. investigate the relation between these two kinds of non-malleability definitions, and pointed out that, under the simulation-based definition, non-malleability with respect to commitment does not imply the non-malleability with respect to decommitment, so that it is of great theoretical significance to design a commitment protocol that satisfies both kind of non-malleability. Additionally, this paper shows a way to construct a computationally hiding and computationally binding commitment which is concurrent non-malleable with respect to commitment as well as decommitment. Later in PKC'10, Cao et al. patch this protocol to obtain a statistically binding version. However, both of these two schemes (and almost all existing non-malleable commitment schemes) are subjected to the same constraint:the commitment phase and decommit phase cannot overlap in time. Hence, it remains an open question to construct a fully concurrent non-malleable commitment scheme with stage-overlapping.
In this paper, we do the following work on this problem:
a) We show that under the current definition of non-malleability, it is impossible to solve the above problem. At the same time, we present a new definition for the concurrent non-malleability of commitment schemes, which is essentially the same with the original one but takes a different form to fit this scenario.
b) We analyze the reason why this problem exists, and then solve it by constructing a computationally hiding and computationally binding commitment scheme, which is concurrent non-malleable with respect to commitment and decommitment, even though stage-overlapping is allowed. Based on the one-way function assumption, either the commit phase or the decommit phase needs super-logarithmic rounds.
简言之,零知识证明系统是一个两方交互协议,其中证明者通过交互来向验证者证明某一个断言,并且确保不向验证者泄露任何额外的信息。零知识证明自提出以来一直处于密码学的中心位置,对密码学的发展起到关键作用。首先,零知识证明为密码协议安全性的形式化分析奠定了基础,其基于模拟不可区分性的证明思想已成为可证明安全理论的核心。更重要的是,零知识证明看似矛盾的独特性质令其集“保密性”和“认证性”于一身,因此广泛应用于各类密码算法和密码协议的构造,例如身份认证协议、抗选择密文攻击安全的加密方案、以及抵抗恶意敌手的安全多方计算协议。
作为构造零知识证明系统以及其他安全计算协议的一个基本组件,承诺的思想先于零知识证明而被学者们用于设计电话投币、虚拟扑克等协议,并最终由Brassard等人给出了形式化的定义以及“承诺(commitment)"这个形象的名称。简言之,承诺协议是一类两方参与的两阶段交互协议。首先在承诺阶段,承诺者对一个字符串v承诺,发送给接收者,并且确保接受者得不到关于v的任何信息；随后在打开阶段,承诺者公开v,并证明其与第一阶段的一致性。承诺协议的两个基本性质分别称为隐藏性和绑定性。所谓隐藏性,是指在承诺阶段任意恶意的接收者都不能获取承诺字符串的信息；而绑定性是指在打开阶段,任意恶意的承诺者都不能将承诺打开为另外一个值,并且通过验证。
在密码协议的设计中,承诺协议通常作为子协议来构造更为复杂的安全计算协议,其主要作用是固定参与者的输入,同时保证其隐私性。它通常与零知识证明系统配合来实现抵抗恶意敌手的安全多方计算协议。另外,承诺协议与零知识证明系统存在着内在的联系,并且两者的研究总是相互促进,共同发展的。
近年来,随着互联网的兴起,密码协议在并发、异步的网络环境下的面临着更多的安全性冲击,协议基本的安全属性已经不足以应对复杂的网络环境和应用。如何建立合理的协议安全模型,以及设计满足更高安全性需求、适用于互联网应用的密码协议逐渐成为了密码学界关注的热点问题。
其中,并发不可延展性定义了零知识证明及承诺协议在多次并发执行的过程中抵抗中间人攻击的能力。以零知识证明为例,考虑如下情景：一个中间人敌手并发的参与多个会话,执行同一个零知识证明协议,在其中一部分会话中,敌手作为验证者接收并验证诚实证明者对某些断言的证明,而在另一部分会话中,敌手作为证明者与诚实的验证者交互,试图构造对相关断言的证明。能够抵抗上述并发中间人攻击的零知识证明或者承诺协议称为并发不可延展的。研究者普遍认为,并发不可延展性在最大程度上反映了协议在开放网络环境下所要达到的安全性要求。
本文的研究主要围绕并发不可延展的零知识证明系统以及承诺方案而展开,重点在与协议鲁棒性研究,具体包括以下方面：
●关于并发不可延展的零知识
近期,Lin等人将承诺协议的不可延展性扩展到更一般化的形式,称为对任意k-轮协议的不可延展性,讨论承诺协议在以下场景中的安全性：敌手在左侧会话中参与任意一个k-轮协议,而在右侧与多个接收者交互,执行某个承诺协议。k-不可延展性反应了一个承诺协议与其他协议组合执行时的鲁棒性,即一个k-不可延展的承诺可以与任意轮数不超过k的协议组合执行,而不影响其安全性。因此,当与其他协议组合执行时,此类承诺协议的不可延展性更易于分析。本文受上述文献所启发,研究并发不可延展零知识的鲁棒性。在已有的不可延展零知识协议中,一部分使用了非黑盒的模拟机制,而缺乏鲁棒性正是非黑盒模拟机制自身的限制,尤其在并发环境下；另一部分虽然采用的黑盒模拟,但都是基于Goldreich-Kahan结构而构造,包含一个零知识子协议。由于零知识在并发组合下并不封闭,因此这些协议的鲁棒性难于分析。为此,本文提出了第一个具有鲁棒性并发不可延展零知识论证系统,具有如下特点：
a)基于Feige-Shamir结构而构造,以具有鲁棒性的不可延展承诺协议以及巧妙设计的证据不可区分证明系统来实现零知识,并确保整个协议的鲁棒性。
b)采用“茫然模拟(oblivious simulation)"的策略来模拟敌手的视图。
c)在单向函数假设下,拥有最优的轮复杂度,即超对数。
d)通过适当调整子协议的轮数,可以实现与任意协议的组合。
●关于并发不可延展的承诺
承诺协议的不可延展性针对其两个阶段分别定义,即关于承诺阶段的不可延展性以及关于打开阶段的不可延展性,分别描述了两个阶段相对于自身的独立性。近期,在TCC’09的一项工作中,Ostrovsky等人研究了这两类不可延展性之间的关系,并指出,在基于模拟的不可延展性定义下,承诺阶段的不可延展性并不一定蕴含打开阶段的不可延展性,因此设计同时满足这两种性质的承诺协议具有重要的理论意义。文中同时构造了一个计算隐藏且计算绑定的承诺方案,同时满足承诺阶段和打开阶段的并发不可延展性。此后,在PKC'10中,Cao等人将该方案扩展并得到一个统计绑定的版本。然而,上述两方案(以及几乎所有已知的不可延展承诺方案)都存在一个共同的限制：承诺阶段和打开阶段在时间上不可重叠。因此,如何构造一个两阶段可重叠的完全并发不可延展的承诺方案仍然是一个公开问题。
为此,本文作了如下工作：
a)分析并指出在目前的不可延展性定义下,上述问题无法解决。同时,本文给出了一个新的并发不可延展性定义,它与原定义在本质上相同,但适用于两阶段可重叠的承诺协议。
b)分析了上述问题存在的原因,并在此基础上构造了一个计算绑定且计算隐藏的承诺方案,同时满足承诺阶段和打开阶段的并发不可延展性,并且允许两阶段可重叠,解决了上述公开问题。在单向函数假设下,该方案的承诺阶段和打开阶段的轮复杂性均为超对数。
In the last seventies and eighties, the research of modern cryptography has ushered in a new era of vigorous development, in which a series of milestone achievements, such as public key cryptography, interactive proof system and pseudo-random generators, have emerged, opening up the way of combining cryptography with complexity theory. In the FOCS'97conference, Goldwasser gives an invited talk with the tile "Cryptography and Complexity Theory:A Match Made in Heaven", and points out that, the most important progress made in modern cryptography is basing this field on complexity theory, and it is complexity theory that has transformed cryptography from an art to a rigorous science. Moreover, zero-knowledge is the best witness of the intertwining and cross-promoting between cryptography and complexity theory.
Informally speaking, a zero-knowledge proof system is a two-party interactive protocol, in which a prover tries to convince a verifier the correctness of a statement, but ensures that the verifier learns no extra information during the interactive procedure. Zero-knowledge has been at the heart of cryptography since its invention, and plays a key role in the development of cryptography. First, zero-knowledge laid the foundation for the formal analysis of cryptographic protocols, and its simulation-based way of security proofs have become the core of provable security theory. More importantly, the seemingly contradictory nature enables zero-knowledge proof system to integrate "privacy" and "authentication" within the single primitive, which results in a wide array of applications, such as identification protocols, encryption schemes secure against chosen ciphertext attack, and secure multi-party protocols against malicious adversaries.
As a fundamental building block of zero-knowledge proof system and other secure protocols, the idea of a commitment scheme (sealed envelope) appears earlier than zero-knowledge in the design of protocols for coin-tossing by telephone, mental poker and so on. Finally, it is formally defined by Brassard et al. and gets the vivid name of "commitment". Roughly speaking, a commitment scheme is a two-phase interactive protocol between two parties. First in the commit phase, the committer commits himself to a string (say v), and sends the commitment to the receiver, while ensuring that the receiver knows nothing about v; then in the reveal phase, the committer publishes v, and proves it is consistent with the messages in the first stage. Two basic properties of commitment scheme are known as hiding and binding, in which hiding says that, in the commit phase no malicious receiver can get any information about the secret string v, and binding says that, in the reveal phase no malicious committer can open the commitment to another value successfully while passing the decomitment verification.
In the research of cryptographic protocols, commitment schemes are often used as sub-protocols to build more complex ones, in which they are taken to fix the inputs of the participants as well as keep their privacy. Furthermore, they usually cooperate with zero-knowledge proof systems to achieve secure multi-party protocols against malicious adversaries. Besides, there exit inherent relations between commitment schemes and zero-knowledge proof systems, so that the researches in both areas are always proceeding hand-in-hand.
In recent years, with the rapid development of internet, cryptographic protocols that run in the concurrent and asynchronous network encounter more and more security challenges, so that the basic security properties of protocols are not sufficient to cope with the complex network applications. Therefore, how to build reasonable security models and design cryptographic protocols that enjoy higher security and apply to the internet applications has been one of the attractive areas in cryptography.
Concurrent non-malleability defines the security property of zero-knowledge proof systems as well as commitment schemes against "man-in-the-middle" attack, when executing multi times concurrently. Taking zero-knowledge for example, consider the follow scenario:a man-in-the-middle adversary concurrently participates many sessions running the same zero-knowledge protocol, in some of which the adversary plays the role of verifier receiving and verifying proofs of some statements given by the honest provers, while in others the adversary interacts with the honest verifiers as a prover trying to construct proofs of some related statements, Zero-knowledge proof systems and commitment schemes secure against the above concurrent man-in-the-middle attack are called concurrent non-malleable. It is generally believed that, concurrent non-malleability is most suitable for modeling the security requirements in the open network.
In this paper, we investigate concurrent non-malleable zero-knowledge as well as commitment schemes, and focus mainly on the robustness of protocols. Specifically, we work on the following points:
·On concurrent non-malleable zero-knowledge
Recently, Lin et al. extends the original non-malleability of commitment schemes to a more general form called non-malleability with respect to arbitrary k-round protocol (or k-non-malleability for short), studying the security of commitments in the following scenario:the man-in-the-middle adversary participates one left session running an arbitrary k-round protocol, and multi right sessions interacting with a set of honest receivers and executing a commitment scheme. Loosely speaking, k-non-malleability shows the robustness of a commitment scheme when composed with other protocols. That is, a k-non-malleable commitment scheme can be composed with any protocols with no more than k rounds, and does not affect its security. Hence, this kind of protocol is easier to analyze when concurrently composed with other protocols.
Highly inspired by the above literature, we turn to study the robustness of concurrent non-malleable zero-knowledge. In the existing concurrent non-malleable zero-knowledge protocols, some rely on non-black-box simulation technique. However, as we know that, less robustness is the inherent limitation of non-black-box techniques, let alone in the concurrent setting. Besides, all the other constructions applying black-box simulation follows the Goldreich-Kahan style incorporating a zero-knowledge sub-protocol, which makes robustness hard to argue (sine zero-knowledge is not closed under concurrent composition).
In this paper, we present the first robust concurrent non-malleable zero-knowledge argument system that enjoys the properties below:
a) Following the Feige-Shamir style, takes robust non-malleable commitment and specifically designed witness indistinguishable proofs as basic components to achieve zero-knowledge, and at the same time ensures the robustness of the whole protocol.
b) Applies the "oblivious simulation" strategy to emulate the view of the adversary.
c) Achieves optimal (super-logarithmic) round complexity under the minimal assumption of one-way functions.
d) Can be composed with any protocols by appropriately adjusting the round complexity of the sub-protocols.
·On concurrent non-malleable commitments
The non-malleability of commitment schemes are defined respectively for each stage, i.e. non-malleability with respect to commitment and non-malleability with respect to decommitment, describing the independence of each stage with respect to itself separately. In a recent work in TCC'09, Ostrovsky et al. investigate the relation between these two kinds of non-malleability definitions, and pointed out that, under the simulation-based definition, non-malleability with respect to commitment does not imply the non-malleability with respect to decommitment, so that it is of great theoretical significance to design a commitment protocol that satisfies both kind of non-malleability. Additionally, this paper shows a way to construct a computationally hiding and computationally binding commitment which is concurrent non-malleable with respect to commitment as well as decommitment. Later in PKC'10, Cao et al. patch this protocol to obtain a statistically binding version. However, both of these two schemes (and almost all existing non-malleable commitment schemes) are subjected to the same constraint:the commitment phase and decommit phase cannot overlap in time. Hence, it remains an open question to construct a fully concurrent non-malleable commitment scheme with stage-overlapping.
In this paper, we do the following work on this problem:
a) We show that under the current definition of non-malleability, it is impossible to solve the above problem. At the same time, we present a new definition for the concurrent non-malleability of commitment schemes, which is essentially the same with the original one but takes a different form to fit this scenario.
b) We analyze the reason why this problem exists, and then solve it by constructing a computationally hiding and computationally binding commitment scheme, which is concurrent non-malleable with respect to commitment and decommitment, even though stage-overlapping is allowed. Based on the one-way function assumption, either the commit phase or the decommit phase needs super-logarithmic rounds.
引文
[1]Whitfield Diffie, Martin E. Hellman:New Directions in Cryptography. IEEE Transactions on Information Theory 22(6):644-654 (1976).
[2]Shafi Goldwasser:New directions in cryptography:twenty some years later. FOCS 1997:314-324.
[3]Shafi Goldwasser, Silvio Micali, Charles Rackoff:The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). STOC 1985:291-304.
[4]Shafi Goldwasser, Silvio Micali:Probabilistic Encryption. J. Comput. Syst. Sci. 28(2):270-299 (1984).
[5]Oded Goldreich, Silvio Micali, Avi Wigderson:How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. STOC 1987: 218-229.
[6]Amos Fiat, Adi Shamir:How to Prove Yourself:Practical Solutions to Identification and Signature Problems. CRYPTO 1986:186-194.
[7]Manuel Blum, Paul Feldman, Silvio Micali:Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract). STOC 1988:103-112.
[8]Moni Naor, Moti Yung:Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. STOC 1990:427-437.
[9]Manuel Blum:Coin Flipping by Telephone. CRYPTO 1981:11-15.
[10]Adi Shamir, Ron Rivest, Leonard Adleman:Mental Poker. Technical Report LCS/TR-125, Massachusetts Institute of Technology, April 1979.
[11]Gilles Brassard, David Chaum, Claude Crepeau:Minimum Disclosure Proofs of Knowledge. J. Comput. Syst. Sci.37(2):156-189 (1988).
[12]Shien Jin Ong, Salil P. Vadhan:An Equivalence Between Zero Knowledge and Commitments. TCC 2008:482-500
[13]Cynthia Dwork, Moni Naor, Amit Sahai:Concurrent zero-knowledge. J. ACM 51(6):851-898 (2004).
[14]Danny Dolev, Cynthia Dwork, Moni Naor:Non-malleable Cryptography. SIAM J. Comput.30(2):391-437 (2000).
[15]Ran Canetti:Universally Composable Security:A New Paradigm for Cryptographic Protocols. FOCS 2001:136-145.
[16]Ran Canetti, Marc Fischlin:Universally Composable Commitments. CRYPTO 2001:19-40.
[17]Ran Canetti, Eyal Kushilevitz, Yehuda Lindell:On the Limitations of Universally Composable Two-Party Computation without Set-up Assumptions. EUROCRYPT 2003:68-86.
[18]Rafael Pass, Alon Rosen:New and improved constructions of non-malleable cryptographic protocols. STOC 2005:533-542.
[19]Boaz Barak, Manoj Prabhakaran, Amit Sahai:Concurrent Non-Malleable Zero Knowledge. FOCS 2006:345-354.
[20]Rafail Ostrovsky, Omkant Pandey, Ivan Visconti:Efficiency Preserving Transformations for Concurrent Non-malleable Zero Knowledge. TCC 2010: 535-552.
[21]Huijia Lin, Rafael Pass, Wei-Lung Dustin Tseng, Muthuramakrishnan Venkitasubramaniam:Concurrent Non-Malleable Zero Knowledge Proofs. CRYPTO 2010:429-446.
[22]Huijia Lin, Rafael Pass:Non-malleability amplification. STOC 2009:189-198.
[23]Oded Goldreich, Ariel Kahan:How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. J. Cryptology 9(3):167-190 (1996).
[24]Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti:Simulation-Based Concurrent Non-malleable Commitments and Decommitments. TCC 2009: 91-108.
[25]Rafael Pass, Alon Rosen:Concurrent Non-Malleable Commitments. FOCS 2005: 563-572.
[26]Huijia Lin, Rafael Pass, Muthuramakrishnan Venkitasubramaniam:Concurrent Non-malleable Commitments from Any One-Way Function. TCC 2008:571-588.
[27]Rafael Pass, Hoeteck Wee:Black-Box Constructions of Two-Party Protocols from One-Way Functions. TCC 2009:403-418.
[28]Hoeteck Wee:Black-Box, Round-Efficient Secure Computation via Non-malleability Amplification. FOCS 2010:531-540.
[29]Rafael Pass, Hoeteck Wee:Constant-Round Non-malleable Commitments from Sub-exponential One-Way Functions. EUROCRYPT 2010:638-655
[30]Huijia Lin, Rafael Pass:Constant-round non-malleable commitments from any one-way function. STOC 2011:705-714
[31]Vipul Goyal:Constant round non-malleable protocols using one way functions. STOC 2011:695-704.
[32]Zongyang Zhang, Zhenfu Cao, Ning Ding, Rong Ma:Non-malleable Statistically Hiding Commitment from Any One-Way Function. ASIACRYPT 2009:303-318.
[33]Zhenfu Cao, Ivan Visconti, Zongyang Zhang:Constant-Round Concurrent Non-Malleable Statistically Binding Commitments and Decommitments. Public Key Cryptography 2010:193-208.
[34]Andrew Chi-Chih Yao:Theory and Applications of Trapdoor Functions (Extended Abstract). FOCS 1982:80-91.
[35]Adi Shamir:IP=PSPACE. J. ACM 39(4):869-877 (1992).
[36]Laszlo Babai:Trading Group Theory for Randomness. STOC 1985:421-429.
[37]Yair Oren:On the Cunning Power of Cheating Verifiers:Some Observations about Zero Knowledge Proofs (Extended Abstract). FOCS 1987:462-471.
[38]Uriel Feige, Adi Shamir:Witness Indistinguishable and Witness Hiding Protocols STOC 1990:416-426.
[39]Mihir Bellare, Oded Goldreich:On Defining Proofs of Knowledge. CRYPTO 1992:390-420.
[40]Ronald Cramer, Ivan Damgard, Berry Schoenmakers:Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. CRYPTO 1994: 174-187
[41]Manuel Blum:How to prove a theorem so no one else can claim it. Proceedings of the International Congress of Mathematicians, Berkeley, California, USA,1986: 1444-1451.
[42]Boaz Barak:How to Go Beyond the Black-Box Simulation Barrier. FOCS 2001: 106-115.
[43]Ransom Richardson, Joe Kilian:On the Concurrent Composition of Zero-Knowledge Proofs. EUROCRYPT 1999:415-431.
[44]Rafael Pass, Muthuramakrishnan Venkitasubramaniam:On Constant-Round Concurrent Zero-Knowledge. TCC 2008:553-570.
[45]Joe Kilian, Erez Petrank:Concurrent and resettable zero-knowledge in poly-loalgorithm rounds. STOC 2001:560-569.
[46]Manoj Prabhakaran, Alon Rosen, Amit Sahai:Concurrent Zero Knowledge with Logarithmic Round-Complexity. FOCS 2002:366-375.
[47]Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti:Constant-Round Concurrent Non-malleable Zero Knowledge in the Bare Public-Key Model. ICALP (2) 2008: 548-559.
[48]Yi Deng, Giovanni Di Crescenzo, Dongdai Lin, Dengguo Feng:Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model. CSR 2009:80-91.
[49]Boaz Barak, Amit Sahai:How To Play Almost Any Mental Game Over The Net-Concurrent Composition via Super-Polynomial Simulation. FOCS 2005:543-552.
[50]Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil P. Vadhan:Concurrent Zero Knowledge Without Complexity Assumptions. TCC 2006:1-20.
[51]Rafael Pass, Wei-Lung Dustin Tseng, Muthuramakrishnan Venkitasubramaniam: Concurrent zero knowledge:simplifications and generalizations. Computing and Information Science Technical Reports, Cornell University,2008.
[52]Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith:Efficient and Non-interactive Non-malleable Commitment. EUROCRYPT 2001:40-59.
[53]Boaz Barak:Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model. FOCS 2002:345-355.
[54]Rui Li, Qiuliang Xu, Hao Wang:Concurrent Non-malleable Statistically Hiding Commitment. CIS 2011:920-924.
[55]Zongyang Zhang, Zhenfu Cao:Concurrent non-malleable statistically hiding commitment. Inf. Process. Lett.112(11):443-448 (2012).
[56]Sanjam Garg, Abhishek Jain, Amit Sahai:Leakage-Resilient Zero Knowledge. CRYPTO 2011:297-315
[2]Shafi Goldwasser:New directions in cryptography:twenty some years later. FOCS 1997:314-324.
[3]Shafi Goldwasser, Silvio Micali, Charles Rackoff:The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). STOC 1985:291-304.
[4]Shafi Goldwasser, Silvio Micali:Probabilistic Encryption. J. Comput. Syst. Sci. 28(2):270-299 (1984).
[5]Oded Goldreich, Silvio Micali, Avi Wigderson:How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. STOC 1987: 218-229.
[6]Amos Fiat, Adi Shamir:How to Prove Yourself:Practical Solutions to Identification and Signature Problems. CRYPTO 1986:186-194.
[7]Manuel Blum, Paul Feldman, Silvio Micali:Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract). STOC 1988:103-112.
[8]Moni Naor, Moti Yung:Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. STOC 1990:427-437.
[9]Manuel Blum:Coin Flipping by Telephone. CRYPTO 1981:11-15.
[10]Adi Shamir, Ron Rivest, Leonard Adleman:Mental Poker. Technical Report LCS/TR-125, Massachusetts Institute of Technology, April 1979.
[11]Gilles Brassard, David Chaum, Claude Crepeau:Minimum Disclosure Proofs of Knowledge. J. Comput. Syst. Sci.37(2):156-189 (1988).
[12]Shien Jin Ong, Salil P. Vadhan:An Equivalence Between Zero Knowledge and Commitments. TCC 2008:482-500
[13]Cynthia Dwork, Moni Naor, Amit Sahai:Concurrent zero-knowledge. J. ACM 51(6):851-898 (2004).
[14]Danny Dolev, Cynthia Dwork, Moni Naor:Non-malleable Cryptography. SIAM J. Comput.30(2):391-437 (2000).
[15]Ran Canetti:Universally Composable Security:A New Paradigm for Cryptographic Protocols. FOCS 2001:136-145.
[16]Ran Canetti, Marc Fischlin:Universally Composable Commitments. CRYPTO 2001:19-40.
[17]Ran Canetti, Eyal Kushilevitz, Yehuda Lindell:On the Limitations of Universally Composable Two-Party Computation without Set-up Assumptions. EUROCRYPT 2003:68-86.
[18]Rafael Pass, Alon Rosen:New and improved constructions of non-malleable cryptographic protocols. STOC 2005:533-542.
[19]Boaz Barak, Manoj Prabhakaran, Amit Sahai:Concurrent Non-Malleable Zero Knowledge. FOCS 2006:345-354.
[20]Rafail Ostrovsky, Omkant Pandey, Ivan Visconti:Efficiency Preserving Transformations for Concurrent Non-malleable Zero Knowledge. TCC 2010: 535-552.
[21]Huijia Lin, Rafael Pass, Wei-Lung Dustin Tseng, Muthuramakrishnan Venkitasubramaniam:Concurrent Non-Malleable Zero Knowledge Proofs. CRYPTO 2010:429-446.
[22]Huijia Lin, Rafael Pass:Non-malleability amplification. STOC 2009:189-198.
[23]Oded Goldreich, Ariel Kahan:How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. J. Cryptology 9(3):167-190 (1996).
[24]Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti:Simulation-Based Concurrent Non-malleable Commitments and Decommitments. TCC 2009: 91-108.
[25]Rafael Pass, Alon Rosen:Concurrent Non-Malleable Commitments. FOCS 2005: 563-572.
[26]Huijia Lin, Rafael Pass, Muthuramakrishnan Venkitasubramaniam:Concurrent Non-malleable Commitments from Any One-Way Function. TCC 2008:571-588.
[27]Rafael Pass, Hoeteck Wee:Black-Box Constructions of Two-Party Protocols from One-Way Functions. TCC 2009:403-418.
[28]Hoeteck Wee:Black-Box, Round-Efficient Secure Computation via Non-malleability Amplification. FOCS 2010:531-540.
[29]Rafael Pass, Hoeteck Wee:Constant-Round Non-malleable Commitments from Sub-exponential One-Way Functions. EUROCRYPT 2010:638-655
[30]Huijia Lin, Rafael Pass:Constant-round non-malleable commitments from any one-way function. STOC 2011:705-714
[31]Vipul Goyal:Constant round non-malleable protocols using one way functions. STOC 2011:695-704.
[32]Zongyang Zhang, Zhenfu Cao, Ning Ding, Rong Ma:Non-malleable Statistically Hiding Commitment from Any One-Way Function. ASIACRYPT 2009:303-318.
[33]Zhenfu Cao, Ivan Visconti, Zongyang Zhang:Constant-Round Concurrent Non-Malleable Statistically Binding Commitments and Decommitments. Public Key Cryptography 2010:193-208.
[34]Andrew Chi-Chih Yao:Theory and Applications of Trapdoor Functions (Extended Abstract). FOCS 1982:80-91.
[35]Adi Shamir:IP=PSPACE. J. ACM 39(4):869-877 (1992).
[36]Laszlo Babai:Trading Group Theory for Randomness. STOC 1985:421-429.
[37]Yair Oren:On the Cunning Power of Cheating Verifiers:Some Observations about Zero Knowledge Proofs (Extended Abstract). FOCS 1987:462-471.
[38]Uriel Feige, Adi Shamir:Witness Indistinguishable and Witness Hiding Protocols STOC 1990:416-426.
[39]Mihir Bellare, Oded Goldreich:On Defining Proofs of Knowledge. CRYPTO 1992:390-420.
[40]Ronald Cramer, Ivan Damgard, Berry Schoenmakers:Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. CRYPTO 1994: 174-187
[41]Manuel Blum:How to prove a theorem so no one else can claim it. Proceedings of the International Congress of Mathematicians, Berkeley, California, USA,1986: 1444-1451.
[42]Boaz Barak:How to Go Beyond the Black-Box Simulation Barrier. FOCS 2001: 106-115.
[43]Ransom Richardson, Joe Kilian:On the Concurrent Composition of Zero-Knowledge Proofs. EUROCRYPT 1999:415-431.
[44]Rafael Pass, Muthuramakrishnan Venkitasubramaniam:On Constant-Round Concurrent Zero-Knowledge. TCC 2008:553-570.
[45]Joe Kilian, Erez Petrank:Concurrent and resettable zero-knowledge in poly-loalgorithm rounds. STOC 2001:560-569.
[46]Manoj Prabhakaran, Alon Rosen, Amit Sahai:Concurrent Zero Knowledge with Logarithmic Round-Complexity. FOCS 2002:366-375.
[47]Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti:Constant-Round Concurrent Non-malleable Zero Knowledge in the Bare Public-Key Model. ICALP (2) 2008: 548-559.
[48]Yi Deng, Giovanni Di Crescenzo, Dongdai Lin, Dengguo Feng:Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model. CSR 2009:80-91.
[49]Boaz Barak, Amit Sahai:How To Play Almost Any Mental Game Over The Net-Concurrent Composition via Super-Polynomial Simulation. FOCS 2005:543-552.
[50]Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil P. Vadhan:Concurrent Zero Knowledge Without Complexity Assumptions. TCC 2006:1-20.
[51]Rafael Pass, Wei-Lung Dustin Tseng, Muthuramakrishnan Venkitasubramaniam: Concurrent zero knowledge:simplifications and generalizations. Computing and Information Science Technical Reports, Cornell University,2008.
[52]Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith:Efficient and Non-interactive Non-malleable Commitment. EUROCRYPT 2001:40-59.
[53]Boaz Barak:Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model. FOCS 2002:345-355.
[54]Rui Li, Qiuliang Xu, Hao Wang:Concurrent Non-malleable Statistically Hiding Commitment. CIS 2011:920-924.
[55]Zongyang Zhang, Zhenfu Cao:Concurrent non-malleable statistically hiding commitment. Inf. Process. Lett.112(11):443-448 (2012).
[56]Sanjam Garg, Abhishek Jain, Amit Sahai:Leakage-Resilient Zero Knowledge. CRYPTO 2011:297-315