【作者】 伍前红；

【导师】 王育民；

【作者基本信息】 西安电子科技大学 ， 密码学， 2004， 博士

【摘要】 本文对可信密码学计算的关键技术进行比较深入的研究,内容包括高效的知识证明协议、可信的公钥加密与不经意加密、高安全性的数字签字与匿名数字签字、可信的电子商务协议设计等问题,提高这些密码学原型与系统的安全性与效率。主要成果有: 1、在知识证明技术方面,给出一个简单的知识证明协议,证明一个秘密整数在特定区间内,用于电子商务系统和论文中其它协议的设计。该协议比Boudot给出的协议更简单,效率更高。2、在加密和可信加密技术方面,首次将对称密码的核心技术非线性S盒用于设计公钥密码系统,给出基于子集和问题的公钥密码体制的新设计,改进可验证的ElGamal加密和RSA加密。提出利用迭代S盒模拟指数运算,从而模拟基于离散对数问题的密钥协商,公钥加密和数字签字。给出一个实例,在该实例中S盒的迭代远远快于模指数计算。其模拟的离散对数密码系统较RSA和ElGamal系统快大约300倍。由于从S盒的输入和输出计算S盒的迭代次数不比离散对数容易,因此该系统可以使用更短的公钥和私钥达到同等的安全性。这一方法有很高的应用前景。使用高密度随机背包问题,模拟ElGamal密码体制和McEliece密码体制。在高密度随机背包困难性假设下,可以证明方案在唯密文攻击下是安全的。在计算上的效率大约是RSA体制的14000倍。由于背包问题是NP-完全问题,该方案有望抗击未来的量子敌手。改进Stadler的ElGamal可验证加密方案,使可公开验证的ElGamal加密仍然具有语义安全性,并推广到多接收者的ElGamal加密情形;给出可公开验证的RSA加密,效率较通用构造方法高。3、在数字签字与认证方面,给出对抗量子敌手的数字签字的计算复杂性假设和签字模型,提出基于随机高密度背包问题的数字签字方案。在合理的参数设置和复杂性假设下,该方案具有接近于RSA签字的复杂性,并可能抗击量子敌手的攻击。首次提出利用不可逆物理过程的数字签字,基于热力学第二定律建议一个数字签字方案,对签字的实现进行离散化处理。扩展Able等的环签字通用方法,使其可以用于使用分割-选择技术的知识签字。利用该方法,基于图同构问题给出一个环签字。首次提出共享公钥但私钥独立的匿名签字概念,从原理上解决在Ad Hoc群体中匿名签字复杂性线性增长的问题。基于NP-完全的弱独立性问题,给出一个具体的签字方案。4、在可信不经意加密方面,基于离散对数问题,给出具有最优在线效率的适应性和非适应性不经意传输。该方案最先实现具有最优在线效率的适应性和非适应性不经意传输,也不可能有更高在线效率的设计。提高上述方案的安全性,使得不经意传输具有可公开验证性,保证协议的输入和输出是可信的。更多还原

【Abstract】 An investigation of the key techniques of trusted cryptographic computation is taken in this thesis, including efficient knowledge proofs, trusted public-key encryptions and oblivious encryptions, digital signatures and anonymous signatures with high security, and trusted electronic commerce. Attention is focused on improving the security and efficiency of such cryptographic primitives. The main contributions follow below. 1. The first aspect is about knowledge proof techniques. A simple knowledge proof to prove that one secret integer lies in a specific interval is proposed. The proposal is much simpler but more efficient than the proof protocol due to Boudot. 2. The second aspect is about encryptions and trusted encryptions. The core technique in symmetric cryptosystem, i.e., nonlinear S-Box, is first introduced to public-key cryptosystem. Novel public-key cryptosystems are suggested using random high-density knapsack problem to simulate ElGamal/McEliece cryptosystems. Improvements of ElGamal encryption and RSA encryption are proposed. An approach is proposed to efficiently simulate exponentiation operation using iteration of S-Box, and then to implement the key agreement, public-key encryption and digital signature based on discrete logarithm problem. A concrete instance is presented in which the S-Box iteration is much less time-consuming than modular exponentiation. The analog of DLP-based cryptosystems is about 300 times more efficient than RSA cryptosystem or ElGamal cryptosystem. Since it is more difficult to determine the times of iterations from the input and output of S-Box than to compute discrete logarithm, smaller key size is possible to achieve the same security. Therefore, the new method to design public-key cryptosystem is enjoying a promising application. Under the assumption that the random high-density knapsack problem is infeasible, the proposed schemes are provably secure against ciphertext-only attack. The schemes are computationally 14000 times more efficient than RSA cryptosystem. Since knapsack problem is NP-complete, the scheme seems secure against quantum adversaries in the future. The publicly verifiable ElGamal encryption due to Stadler is improved to meet semantic security and extended to multiple-receiver settings. Also, a new publicly verifiable RSA encryption is suggested, which is more efficient than the generic construction. 3. The third aspect is about digital signatures. The computation complexity assumptions and signature pattern are formalized against quantum adversaries. According to the pattern, a digital signature based on random high-density knapsack problem is proposed. Under rational complexity assumptions and security parameters, the scheme enjoys the same computation cost as that of RSA signature but plausible security against quantum adversaries. Digital signatures are first proposed using irreversible physical process. Based on the second principle of thermodynamics, a digital signature is presented and its implementation in discrete model is considered. The generic ring signature method due to Abe is extended to meet knowledge signature using cut-and-choose technique. Based on the graphic isomorphism problem, a ring signature is proposed using the extended method. The concept of shared-key signature is first formalized to implement anonymous signature. It overcomes the born inefficiency of ring signature in which the complexity of signature grows with the possible number of ring members. Based on the NP-complete weak independence problem, a concrete scheme is proposed to exemplify the shared-key signature. 4. The fourth aspect is about trusted oblivious encryptions. Based on discrete logarithm problem, adaptive and non-adaptive oblivious transfers are proposed with optimal online complexity. The schemes are the first ones to realized oblivious transfers with optimal online complexity, i.e., there exists no design with more online efficiency than our schemes. The schemes are also improved to meet public verifiability and ensure the outputs of the protocols are trustable. 5. The fifth aspect is about applications of trusted cryptographic computations. Publicly verifiable electronic auctions are proposed to break the trust bottleneck in electronic auction. The first cryptographic bargain is implemented to ensure the output of protocol is trustable. The scheme is efficient and simple to implement. The thesis implements the trustworthiness of the cryptographic primitives and protocols without trusted third parties. Their trustworthiness is based on computational complexity assumptions rather than trust assumptions.更多还原