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

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

椭圆曲线上高效可完全模拟的不经意传输协议

不经意传输协议是安全多方计算的一个关键技术,是当前网络与信息安全研究的热点。基于双线性对及椭圆曲线上的困难问题,分别设计了半诚实模型下和标准恶意模型下的安全高效N选1不经意传输协议。,在半诚实模型下设计了一个椭圆曲线上的不经意传输协议,该协议只需2轮交互,接收方需要2次双线性对运算和1次椭圆曲线倍点运算,发送方需要n次椭圆曲线倍点运算和n次模幂运算,协议的安全可规约到椭圆曲线上的离散对数问题;构建了基于椭圆曲线上双线性对的零知识证明方案,并设计了一个恶意模型下的不经意传输协议,该协议只需3轮交互,接收者需要3次双线性对运算和3次椭圆曲线倍点运算,发送者需要n+1次椭圆曲线倍点运算和n+1次模幂运算,协议能在标准恶意模型下抵抗参与者的恶意攻击行为。实验结果得到在半诚实模型下协议平均运行时间需要0.787 9 s,在标准恶意模型下协议平均运行时间需要1.205 6 s,进一步论证协议的速度。     

随机自归约的一个四步零知识证明协议

文中用位提交（ｂｉｔ－ｃｏｍｍｉｔ）等方法，构造了随机归约的一个四步零知识主证明协议，该协议没有附加任何复杂性假设和证明者的计算能力假设，且交互次数量优，适应面最广（二次剩余，离散对数，图同构等问题都在其中）该协议符合知识和语言的证明系统的完备性，完美零知识性等条件，但它不符合知识和语言的证明系统的可靠性定义，文中给出了新的可靠性定义，在实际应用中，该定义是合理的，该协议是可靠的，可用在安全保密，     

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

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

公开可验证的零知识水印检测

对称水印方案的水印检测密钥可以被用来伪造和移去水印,因此要求它在检测过程中也是保密的.零知识的水印检测方案利用密码学中零知识和知识证明的思想和算法,实现在水印检测时使得验证者确信水印存在性的同时又不泄漏水印检测密钥.提出了公开可验证的零知识水印检测的安全需求,给出一个公开可验证的承诺方案和一个证明知道被承诺值的离散对数的零知识知识证明协议.在此基础上提出了一个公开可验证的零知识水印方案,并讨论了它的安全性.     

基于ElGamal数字签名的零知识证明身份鉴别方案

提出了一种基于ElGamal体制的零知识身份鉴别方案,结合零知识证明的思想及智能卡技术,既保证了身份证明的有效性,又保护了用户的秘密信息。该方案在离散对数问题和随机预言模型假设下是安全的。     

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

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

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

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

基于离散对数的水印检测协议

提出基于离散对数的水印检测协议，以解决通常的水印检测方案泄漏敏感信息（如水印和嵌入位置）的问题．在协议中，水印被隐藏在模指数中．标准的水印与数字作品之间的相关性判定被转换成它的等价形式，证明者通过证明此等价形式，以使得验证者相信水印的存在．在计算离散对数困难的假定下，协议没有泄漏任何敏感信息并且被证明是零知识的．     

实用的强不可分割多重息票方案

当前,多重息票方案设计中的主要困难是如何设计能自由设置兑换次数上界的息票发布协议且所得协议的复杂性并不依赖于这个上界,以及如何为兑换协议提供高效、灵活的兑换机制.为此,提出两个具备改进的效率与功能的方案.新方案分别利用Chaabouni等人的离散对数区间证明技术和Canard等人的关于被承诺元素的知识证明技术实现了对息票兑换次数上界的灵活设置,并且利用Peng等人的批量零知识证明与验证技术对兑换协议的运算复杂度进行了优化.新方案在Nguyen的形式化模型下满足可证安全,而且首次实现了实际应用中的全部理想特性,即并发发布、紧凑存储、批量兑换以及支持设置息票对象和过期日期.性能分析表明,新方案的通信与运算耗费显著低于已有的两个满足强不可分割性质的方案.     

弱公钥模型集下的零知识论证系统

根据近年来弱公钥模型集下的零知识系统的研究成果,对其发展历程和特性设置进行阐释和剖析,探讨该模型集下最优轮数的零知识协议的构造方法,提出通用的4轮模式和3轮模式,以及协议的（并发）健壮性和（可重置）零知识的证明技术和问题,并总结弱公钥模型集下零知识系统的研究将来可能发展的导向。     

安全高效的水印认证协议

基于完全零知识交互证明系统和位委托方案,提出了可证明的安全水印认证协议.现有文献大都使用基于Cox的扩频数字水印方案或对其进行修改后的扩频水印方案.采用了鲁棒性较强的更适合于版权保护的乘法嵌入规则,在宿主信号中嵌入水印;水印检测时,在充分考虑了不同的变换域、信道特性以及人类视觉特性的基础上,采用基于广义高斯分布和Weibull分布模型的各种变换域的鲁棒优化检测器.使用位委托方案对数字水印信息进行委托,并联合使用随机序列隐藏水印嵌入位置信息.协议确保了在证明相应水印存在的同时,没有泄露任何有关水印的敏感信息,防止了蓄意攻击者利用认证过程中泄露的有关水印的敏感信息(如水印、水印位置、提取密钥等)来移除或伪造水印.数字水印方案对各种变换域的水印检测器给予了较全面的考虑,所以,应用该协议进行水印认证,其安全性、有效性、鲁棒性和实用性都有较大提高.     

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.     

零知识水印验证协议

在数字产品中嵌入数字水印,是对其进行版权保护的一种有力手段.近年来提出了不少数字水印方案,但是它们中大部分都是对称的,即用于水印嵌入和水印检测的密钥是相同的.而许多实际的应用都要求非对称的数字水印方案,即水印检测时所知道的秘密不足以修改、伪造或移去水印.对基于比特承诺和零知识证明的水印验证协议进行了研究.所有权证明者采用基于扩频的对称水印技术,在宿主信号中嵌入水印;水印检测的密钥采用比特承诺的形式提交给验证者,通过证明者和验证者之间的交互协议,验证者可以提取到所嵌入的水印,但无法修改、伪造或移去水印.分别提出了验证一个和多个水印比特的协议,可应用于验证嵌入在图像、音频和视频数据中的扩频水印.     

全委托的公共可验证的外包数据库方案

为解决可验证外包数据库方案存在的预处理阶段开销较大及不支持公共可验证的问题,提出了一个全委托的公共可验证的外包数据库模型.给出了模型的架构及交互流程,对模型进行了形式化定义,并给出了模型的正确性定义和安全性定义.利用双线性映射及可验证外包模幂运算协议,构建了一个全委托的公共可验证外包数据库方案,且给出了各个算法的详细描述,证明了方案的正确性和安全性.其安全性可规约为BDHE （bilinear diffie-hellman exponent）难题.与现有方案及不进行全委托计算的方案相比,全委托的公共可验证的外包数据库方案基于可验证外包模幂运算,将大量模幂运算外包给云处理,减小了数据拥有者的开销.理论与实验分析表明：该方案数据拥有者在预处理阶段所需的代价更低,效率更高,适于实际应用.此外,验证过程无需私钥参与,实现了公共可验证.     

基于改进的椭圆曲线零知识证明的智能卡系统

零知识证明已成为密码学研究者非常感兴趣的一个领域,该证明能使验证者无法得到一点知识而相信证明者确实拥有该知识。这里提出一种基于改进的椭圆曲线零知识证明的智能卡系统,该系统能够大大地提高智能卡的安全性,可以被广泛地用于金融领域。这个新方案不仅能够保证安全性,而且还减少了交互次数。同时基于椭圆曲线上的零知识证明可以用比RSA短得多的密钥,达到与RSA同等级别的安全性。     

A secure and scalable Group Key Exchange system

We present a Group Key Exchange protocol which extends in a natural way the Diffie-Hellman protocol. Our protocol is scalable: it has two rounds (for n>2 parties) and the number of modular exponentiations per user is constant. It is secure against a passive adversary if the Diffie-Hellman problem is intractable.     

A note on the Dwork-Naor timed deniable authentication

In this paper, we present an improved Dwork-Naor 2-round timed deniable authentication scheme with reduced computational and communication complexity. The improved protocol is convenient for authenticating arbitrarily large files (e.g., the contents of a large data-base or a large software), and its first message (from the verifier to the authenticator) is independent on the message to be authenticated by the authenticator.     

Compact modular exponentiation accelerator for modern FPGA devices

We present a compact FPGA implementation of a modular exponentiation accelerator suited for cryptographic applications. The implementation efficiently exploits the properties of modern FPGAs. The accelerator consumes 434 logic elements, four 9-bit DSP elements, and 13604 memory bits in Altera Stratix EP1S40. It performs modular exponentiations with up to 2250-bit integers and scales easily to larger exponentiations. Excluding pre- and post-processing time, 1024-bit and 2048-bit exponentiations are performed in 26.39 ms and 199.11 ms, respectively. Due to its compactness, standard interface, and support for different clock domains, the accelerator can effortlessly be integrated into a larger system in the same FPGA. The accelerator and its performance are demonstrated in practice with a fully functional prototype implementation consisting of software and hardware components.     

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.