【作者】 龚征；

【导师】 陈克非；

【作者基本信息】 上海交通大学 ， 计算机系统结构， 2008， 博士

【摘要】 随着电子商务、政务等网络应用的蓬勃开展,设计安全并且高效的密码学方案成为密码学的一个重要课题。可证明安全理论(Provable Security)是在预先精确设定的安全模型下,用来验证一个设计好的密码学方案是否能抵御现实中自适应攻击者的形式化分析方法。早期的可证明安全体制一般是基于标准模型(StandardModel)下,将攻击者成功破解方案的概率可转化为攻破某已知困难问题的优势。但基于标准模型的密码学方案往往需要大量的计算,难以实用。随机预言机模型(Random Oracle Model)一经提出,便成为了平衡密码学方案的可证安全性和实用性的重要途径。在随机预言机模型当中,基于一个公共可访问的随机预言机,攻击者的能力仍然可以规约到某个困难问题,同时方案的计算开销也会因为随机预言机模型下许多紧规约技巧而大大降低。实际中,广泛使用的密码学方案和标准大都是基于随机预言机模型下可证安全的。虽然基于随机预言机模型设计方案具有高效率优势,该模型自身的安全性问题也不容忽视,许多负面例子说明现有广泛使用的伪随机函数、散列函数等并不能替换方案证明中所使用的随机预言机,甚至有研究结果表明替换后的方案会失去可证安全性。如何设计一个实际的,安全的散列函数,来替换模型中所使用的随机预言机,成为了近年来该领域的研究热点问题。我们对随机预言机模型的已有成果及其存在的安全性问题进行了总结和分析。首先我们针对基于分组密码的散列函数给出了相应的与随机预言机的白盒不可区分性(Indifferentiability)。1.我们给出了对基于分组密码的散列函数的白盒不可区分性的进一步分析,并给出了一个更加精确的对应基于分组密码的散列函数的白盒不可区分性攻击者的形式化定义。白盒不可区分性的优势对应于散列函数是否keyed的情况加以了区分。我们指出了Chang等人对于4种PGV和PBGV方案给出可区分性攻击存在缺陷,而且给出对应的形式化证明来表明4种PGV和PBGV构造实际上在使用Prefix-Free Padding、HMAC/NMAC和Chop Construction等改进型MD构造后,并同样基于压缩函数满足限定长度的随机预言机的性质,那么这些散列函数与随机预言机是满足白盒不可区分性的。2.基于密钥长度是分组长度两倍情况的分组密码,我们更进一步地对速率(Rate)为1的双倍分组长度散列函数的构造方法和安全性加以研究。研究工作可分为以下三个方面:首先,我们给出了针对Hirose提出的两个作为公开问题的例子的攻击,该攻击证实Hirose给出的例子并不能达到最优化抵抗原像和二次原像攻击,同时给出三个反例证明Hirose给出的最优化抗碰撞的两个必要条件并不完善。其次,基于上述攻击和反例,我们形式化的分析了由Satoh等人在文献中定义的速率为1的双倍分组长度散列函数,来找寻是否存在速率为1并且达到最优化安全的双倍分组长度散列函数。在上述分析之后,我们进一步给出了该类型下速率为1的双倍分组长度散列函数达到最优化安全的必要条件。特别地是,我们针对两个基于新的必要条件下的有代表性的例子给出了白盒不可区分性的形式化证明。其次,对于随机预言机模型下的可证明安全性,选择合适的紧致规约证明技巧来达到安全性与效率的平衡,在方案设计中也是十分重要的。将协议中使用的散列函数理想化为随机预言机,同时基于若干实用性签名方案的设计与规约证明,我们通过这些签名方案的可证明安全来介绍随机预言机模型下最有效的几种证明技巧。这些技巧都具有推广性和启发性,因而被广泛用在其他协议的设计、证明过程中。1.我们首先介绍了部分盲签名的基本概念及其安全性定义,随后基于离散对数问题给出了一种高效率的部分盲签名的方案(DLP-PBS)的设计与安全性分析,与以往若干方案相比,DLP-PBS方案的计算和存储开销均有降低。由于LFSR序列在替换表示有限域元素上的优势,我们基于n阶LFSR序列和DLP-PBS方案给出了另一种高效率的部分盲签名方案。我们所给出的两种部分盲签名方案均是在随机预言机模型下证明了其安全性。与有限域上的方案相比,基于LFSR的部分盲签名长度有所减少。特别的是,两种方案证明中都使用分叉引理作为安全性规约方法。2.我们给出了两种无证书公钥体制下的聚集签名方案。两种方案具有不同的优势,我们能根据实际应用场景的不同加以选择合适的方案。在随机预言机模型下,两种无证书聚集签名方案都通过全域散列规约方法将方案的安全性规约到了椭圆曲线上的计算Diffie-Hellman困难问题之上,没有使用分叉引理规约方法。更多还原

【Abstract】 With the broad implementations of the electronic business and government applications,how to design a secure and feasible cryptosystem becomes more and more significant in theresearch of cryptology. The theory of provable security is a formal analysis technique forwhich the designer defines a precise adversary model in advance, and then proves whether awell-designed cryptosystems can resist the adversary in reality. The classical provable secu-rity is usually based on the standard model, such that the probability of a successful attackcan be reduced to the advantage of resolving a well-known computationally hard problem.Commonly, the schemes that are proven secure in the standard model are less efficient, whichmakes them less practical. The formal analysis under the random oracle model becomes animportant way to balance the provable security and the efficiency in the design of cryptosys-tems. In the random oracle model, by implementing a publicly accessible random oracle,the probability of the successful attack can be reduced to a computationally hard problem aswell. Simultaneously, by using the tight reduction techniques in the random oracle model,the schemes’computational costs will also be remarkably reduced. In fact, many widely-accepted cryptographic schemes and standards had been proven secure under the randomoracle model.Although we enjoy the efficiency of the schemes that are provably secure in the randomoracle model, this model has security problems itself. Many negative results disclosed thatpseudorandom functions and hash functions in reality cannot instantiate the random oraclemanipulated in the simulations. It becomes a red hot topic in this research field on howto design a cryptographic hash function to replace the random oracle in the schemes thatare proven secure under the random oracle model. In this thesis, we summarize the knownresults and trace the security problems in the random oracle model:1. A synthetic indifferentiability analysis of some block-cipher-based hash functions isconsidered. First, a more precise definition is proposed on the indifferentiability adver-sary in block-cipher-based hash functions. Next, the advantage of indifferentiability isseparately analyzed by considering whether the hash function is keyed or not. Finally,a limitation is observed in Chang et al.’s indifferentiable attacks on the four PGV andthe PBGV hash functions. The formal proofs show the fact that those hash functions are indifferentiable from a random oracle in the ideal cipher model with the prefix-freepadding, the NMAC/HMAC and the chop construction.2. The security of the rate-1 double block length hash functions, which based on a blockcipher with a block length of n-bit and a key length of 2n-bit, is reconsidered. Preim-age and second preimage attacks are designed to break Hirose’s two examples whichwere left as an open problem. Counter-examples and new attacks are presented on ageneral class of double block length hash functions with rate 1, which disclose thereexist uncovered ?aws in the former analysis by Satoh et al. and Hirose. Some refinedconditions are proposed for ensuring this general class of the rate-1 hash functions tobe optimally secure against the collision attack. In particular, two typical examples,which designed under the proposed conditions, are proven to be indifferentiable fromthe random oracle in the ideal cipher model.For the provable security under the random oracle model, the other key problem is tochoose a tight reduction technique to balance the security and the efficiency in practice. Bysimulating the underlying hash function as a random oracle, we present some well-designedsignature schemes which are efficiently given the reduction proofs in the random oraclemodel. All these reduction proofs can be easily extended to the provable security on similarsignature schemes in the random oracle model.1. Based on the discrete logarithm problem and the Schnorr’s blind signature scheme,we propose a new efficient partially blind signature scheme. The computation andcommunication costs are both reduced in our scheme. We also provide a new partiallyblind signature scheme which is based on n-th order characteristic sequences gener-ated by LFSR. By using the forking lemma reduction technique, their securities areproven in the random oracle model. Compares with the finite field based schemes, ourscheme shows advantages on the computation and storage since the reduced represen-tation of finite field elements by LFSR. Both of the schemes can make privacy-orientedapplications, which are based on partially blind signatures, become more practical forhardware-limited environment, such as smart phones and PDAs.2. We propose two certificateless aggregate signature schemes, which are the first aggre-gate signature schemes in the certificateless cryptosystems. The first scheme reducesthe costs of communication and signer-side computation but loses on storage, whilethe second scheme minimizes the storage but sacrifices the communication. We can choose one of the above schemes by considering the implementation circumstance.In advance, our schemes do not need the public key certificate anymore and achievethe Trust Level 3, which is the same level in the traditional PKI. Both of the schemesare provably secure in the random oracle model by assuming the intractability of thecomputational Diffie-Hellman problem over the groups with bilinear maps.更多还原