NP问题的最优轮复杂性知识的零知识证明

NP问题已有的知识的(黑箱)零知识证明都是非常数轮的,因此,在标准的复杂性假设下,NP问题是否存在常数轮的(黑箱)知识的零知识证明是一个有意义的问题.本文对该问题进行了研究,在一定的假设下给出了HC问题的两个常数轮知识的零知识证明系统.根据Katz最近的研究结果,在多项式分层不坍塌的条件下,本文基于claw-free陷门置换给出的HC问题的5轮知识的零知识证明系统具有最优的轮复杂性.     

On constant-round concurrent non-malleable proof systems

Security under man-in-the-middle attacks is extremely important when protocols are executed on asynchronous networks, as the Internet. Focusing on interactive proof systems, one would like also to achieve unconditional soundness, so that proving a false statement is not possible even for a computationally unbounded adversarial prover. Motivated by such requirements, in this paper we address the problem of designing constant-round protocols in the plain model that enjoy simultaneously non-malleability (i.e., security against man-in-the-middle attacks) and unconditional soundness (i.e., they are proof systems).We first give a construction of a constant-round one-many (i.e., one honest prover, many honest verifiers) concurrent non-malleable zero-knowledge proof (in contrast to argument) system for every NP language in the plain model. We then give a construction of a constant-round concurrent non-malleable witness-indistinguishable proof system for every NP language. Compared with previous results, our constructions are the first constant-round proof systems that in the plain model guarantee simultaneously security against some non-trivial concurrent man-in-the-middle attacks and against unbounded malicious provers.     

基于身份的强指定验证者签名方案

针对近期提出的基于身份强指定验证者签名方案的安全漏洞,通过采用在随机Oracle模式安全的知识的零知识证明方法,构建一个安全的基于身份的强指定验证者签名方案.同时与以往体制相比,实现效率有明显提高.     

基于格的高效通用累加器与被累加值的零知识证明

通用累加器作为一种具有数据压缩性质的重要密码学元件,其多应用于隐私保护相关的区块链系统、身份认证系统以及各类权限管理系统.研究发现目前已有的基于小整数解(SIS)问题困难性假设的通用累加器内部计算效率不高,且更新效率低.因此,本文设计并实现了首个基于环小整数解(Ring-SIS)问题困难性假设的高效通用累加器,其更新开...     

基于椭圆曲线的单轮零知识证明方案

零知识证明在信息安全领域有着很广泛的应用前景。然而传统的零知识证明方案为了保证方案的正确性需要多轮的迭代,大大增加了交互双方的通信量,使得方案往往不适合实际应用。提出了一种单轮零知识证明的方案,在保证方案正确性、完全性和零知识性的同时将方案运行的迭代次数降低到1,最大程度地减少了方案的通信量。同时将零知识证明扩展到了椭圆曲线上的离散对数问题,提高了方案的安全性。最后给出了构造单轮零知识方案的一个必要条件。     

数据可恢复性的零知识证明

可恢复性证明是一种外包存储服务中的数据完整性检测技术.本文致力于交互式证明系统标准模型下的可恢复性证明协议构造方法研究,提出了首个能够防止证明者欺骗和验证数据泄露的交互式可恢复性证明协议,并通过构造多项式时间的可回卷知识抽取器,给出了基于计算Diffie-Hellman假设下的协议完备性、稳固性,以及零知识性证明.特别是,所提方案的验证过程只要求低的、固定大小的负载,达到了最小化通信复杂性的目的.     

一种改进的有序多重签名方案

分析了一般有序多重签名的安全性,文章发现存在组成员内部欺诈的情况下,该方案是不安全的。因此该文提出了一种改进方案,新方案增设了签名中心,利用零知识证明防止成员内部欺诈,解决了有序多重方案的安全性问题。     

Existence of 3-round zero-knowledge proof systems for NP

This paper considers the existence of 3-round zero-knowledge proof systems for NP. Whether there exist 3-round non-black-box zero-knowledge proof systems for NP language is an open problem. By introducing a new interactive proof model, we construct a 3-round zero-knowledge proof system for graph 3-coloring under standard assumptions. Our protocol is a non-black-box zero-knowledge proof because we adopt a special strategy to prove the zero-knowledge property. Consequently, our construction shows the existence of 3-round non-black-box zero-knowledge proof for all languages in NP under the DDH assumption.     

Zero-knowledge proofs of retrievability

Proof of retrievability (POR) is a technique for ensuring the integrity of data in outsourced storage services.In this paper,we address the construction of POR protocol on the standard model of interactive proof systems.We propose the first interactive POR scheme to prevent the fraudulence of prover and the leakage of verified data.We also give full proofs of soundness and zero-knowledge properties by constructing a polynomial-time rewindable knowledge extractor under the computational Diffie-Hellman assump...     

一种构造并发不可延展零知识的新方法

构造了一个新的并发不可延展的零知识论证系统,具有更好的鲁棒性.新方案基于Feige-Shamir结构而设计,以具有鲁棒性的不可延展承诺方案以及巧妙设计的证据不可区分性证明为基本组件,来实现并发不可延展性和鲁棒性.此外,对敌手视图的模拟借助了"茫然模拟"的策略.当与其它协议并发组合时,该方案更易于分析和应用.基于单向函数假设,该方案的轮复杂性为超对数.     

基于Brands体制的强不可伪造电子货币系统

针对Brands电子支付体制在电子货币被重复使用时所存在的安全漏洞,即获取同一电子货币不同支付信息的攻击者可以以用户的身份重复使用该货币,通过引入知识的零知识证明以及概率加密等工具,提出了一个新的公正电子货币系统的设计方案,实现了在货币被重复使用时的强不可伪造性。同时该系统即使在银行或用户密钥被泄露时,仍然可以保证整个系统的安全性。其安全性基于随机Oracle模型和限制性盲签名假设。     

Alternation in interaction

The traditional studies of multi-prover interactive proof systems have concentrated on cooperating provers. These are systems in which a verifier interacts with a set of provers who collaborate in their attempt to convince the verifier that a word is in a prespecified language L. Results on probabilistically checkable proofs coupled with parallel repetition techniques characterize NP in terms of multi-prover proof systems: languages in NP can be verified through a one-round interaction with two cooperating provers using limited randomness and communication.?Less attention has been paid to the study of competition in this complexity-theoretic setting of interactive proof systems. We consider, for example, one-round proof systems where the first prover is trying to convince the verifier to accept and the second prover is trying to convince the verifier to reject. We build into these proof systems a (crucial) asymmetry between the provers, analogous to quantifier alternation. We show that such proof systems capture, with restrictions on communication and randomness, languages in NP. We generalize this model by defining alternating prover proof systems which we show characterize each level of the polynomial hierarchy. Alternating oracle proof systems are also examined.?The main contribution of this work is the first exact characterization of the polynomial hierarchy in terms of interactive (prover) proof systems. Received: November 19, 1997.     

一种公平交换协议的攻击算法分析

公平交换(fairexchange)协议,研究电子商务中的实时公平性问题。与其他安全协议不同的是,该类协议的公平性验证应主要针对交易实体内部可能存在的失信行为。周永彬博士等提出了一种完全基于RSA算法的公平签名交换协议。然而,由于零知识证据生成与验证的不完备,以及扩环运算可能带来的安全隐患,该协议存在安全漏洞。针对协议本身,给出了一种RSA扩环攻击的实例;针对协议的应用,指出了可能存在的安全风险。     

Generalized theorems on relationships among reducibility notions to certain complexity classes

In this paper we give several generalized theorems concerning reducibility notions to certain complexity classes. We study classes that are either (I) closed under NP many-one reductions and polynomial-time conjunctive reductions or (II) closed under coNP many-one reductions and polynomial-time disjunctive reductions. We prove that, for such a classK, (1) reducibility notions of sets toK under polynomial-time constant-round truth-table reducibility, polynomial-time log-Turing reducibility, logspace constant-round truth-table reducibility, logspace log-Turing reducibility, and logspace Turing reducibility are all equivalent and (2) every set that is polynomial-time positive Turing reducible to a set inK is already inK.From these results, we derive some observations on the reducibility notions to C₌P and NP.     

Structuring Resolution Proofs by Introducing New Lemmata

Resolution proofs are unstructured by their very nature, since theycannot use substantial lemmata. To impose structure on given resolutionproofs and thereby improve their readability we will introduce new lemmatain a postprocessing step. As these lemmata cannot be generated byresolution, we will employ function introduction rules as presented by Baazand Leitsch and give a correct and complete criterion for theirapplicability to the proofs. Applying function introduction rules toresolution proofs enables us to detect and eliminate certain homomorphicsubproofs immune to the known redundancy elimination rules. For the caseswhen the criterion is satisfied we will characterize the transformation oftree resolution proofs to their condensation-reduced functional extensions,which may result in a double exponential reduction of proof height.Moreover, the proofs obtained by this transformation are more structured andhence more intelligible.     

基于独立集问题的零知识证明研究

零知识证明已经成为信息安全领域身份认证的关键技术之一。为了避免已知零知识证明系统的图同构问题,提出了一种知识的计算零知识证明系统,其安全性建立在NPC独立集问题上。该算法的构造基于离散对数问题的困难性,从而保证了系统的合理性、完全性、计算零知识性。并从计算复杂度和通信复杂度两方面对系统及其算法参数的选取进行了分析。理论证明,该系统是可行有效的。     

具有直线提取器的匿名指纹方案

迄今为止,基于群签名构造匿名指纹方案的问题尚未得到较好地解决。为此,提出一个具有直线提取器的匿名指纹方案,新方案的设计过程使用了关于OR逻辑的Canard-Gouget-Hufschmitt知识证明技术(CANARD S, GOUGET A, HUFSCHMITT E. A handy multi-coupon system. ACNS 2006: Proceedings of the 4th International Conference on Applied Cryptography and Network Security, LNCS 3989. Berlin: Springer-Verlag, 2006: 66-81),Chida-Yamamoto批量零知识证明与验证技术(CHIDA K, YAMAMOTO G. Batch processing for proofs of partial knowledge and its applications. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2008, E91-A(1): 150-159)以及Arita(ARITA S. A straight-line extractable non-malleable commitment scheme. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2007, E90-A(7): 1384-1394)的直线可提取的承诺方案。需要指出的是,新方案支持并发注册,因此特别适合于基于互联网的应用环境。此外,新方案具有直线提取器,使得安全性证明中的归约算法无需依赖于低效的重绕策略,从而实现了紧密的安全性归约。形式化的安全性分析表明,新方案满足匿名指纹方案要求的所有性质。     

A hybrid approach to vector-based homomorphic tallying remote voting

Vector-based homomorphic tallying remote voting schemes provide an efficient protocol for vote tallying, but they require voters to prove in zero-knowledge that the ballots they cast have been properly generated. This is usually achieved by means of the so-called zero-knowledge range proofs, which should be verified by the polling station before tallying. In this paper, we present an end-to-end verifiable hybrid proposal in which ballots are proven to be correct by making use of a zero-knowledge proof of mixing but still using a homomorphic tallying for gathering the election results. Our proposal offers all the advantages of the homomorphic tallying paradigm, while it avoids the elevated computational cost of range proofs. As a result, ballot verification performance is improved in comparison with the equivalent homomorphic systems. The proposed voting scheme is suitable for multi-candidate elections as well as for elections in which the votes have different weights.     

Delegateable signatures based on non-interactive witness indistinguishable and non-interactive witness hiding proofs

A delegateable signature scheme （DSS） which was first introduced by Barak is mainly based on the non-interactive zero-knowledge proof （NIZK） for preventing the signing verifier from telling which witness （i.e., restricted subset） is being used. However, the scheme is not significantly efficient due to the difficulty of constructing NIZK. We first show that a non-interactive witness indistinguishable （NlWl） proof system and a non-interactive witness hiding （NIWH） proof system are easier and more efficient proof models than NIZK in some cases. Furthermore, the witnesses em- ployed in these two protocols （NlWl and NIWT） cannot also be distinguished by the verifiers. Combined with the E-protocol, we then construct NlWl and NIWH proofs for any NP statement under the existence of one-way functions and show that each proof is different from those under the existence of trapdoor permutations, Finally, based on our NlWl and NIWH proofs, we construct delegateable signature schemes under the existence of one-way functions, which are more efficient than Barak＇s scheme under the existence of trapdoor permutations.