随机预言机模型下可证明安全性关键问题研究
|
摘要
随着电子商务、政务等网络应用的蓬勃开展,设计安全并且高效的密码学方案成为密码学的一个重要课题。可证明安全理论(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困难问题之上,没有使用分叉引理规约方法。
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.
虽然基于随机预言机模型设计方案具有高效率优势,该模型自身的安全性问题也不容忽视,许多负面例子说明现有广泛使用的伪随机函数、散列函数等并不能替换方案证明中所使用的随机预言机,甚至有研究结果表明替换后的方案会失去可证安全性。如何设计一个实际的,安全的散列函数,来替换模型中所使用的随机预言机,成为了近年来该领域的研究热点问题。我们对随机预言机模型的已有成果及其存在的安全性问题进行了总结和分析。首先我们针对基于分组密码的散列函数给出了相应的与随机预言机的白盒不可区分性(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困难问题之上,没有使用分叉引理规约方法。
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.
引文
[1] R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures andpublic-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978.
[2] M. Rabin. Digitized signatures and public-key functions as intractible as factoriza-tion. Technical report, Technical Report LCS/TR-212, MIT Laboratory for ComputerScience, 1979.
[3] R. Merkle and M. Hellman. Hiding information and signatures in trapdoor knapsacks.IEEE Transaction on Information Theory, 24:525–530, 1978.
[4] Wenbo Mao. Modern Cryptography: Theory and Practice. Publishing house of Elec-tronic Industry, 2004.
[5] H.Y. Chien, J.K. Jan, and Y.M. Tseng. Rsa-based partially blind signature with lowcomputation. In Proceedings of the eighth international conference on parallel anddistributed systems, pages 385–389, 2001.
[6] M.S Kwon and Y.K Cho. Randomization enhanced blind signature schemes based onrsa. IEICE A Fundam, E86-A(3):730–733, 2003.
[7] H.F. Huang and C.C Chang. A new design of efficient partially blind signaturescheme. Journal of Systems and Software, 73(3):pp.397–403, 2003.
[8] C.I. Fan and C.L. Lei. Low-computation partially blind signatures for electronic cash.IEICE Transaction on Fundamentals of Electronics, Communications and ComputerSciences, E81-A(5):818–824, 1998.
[9] C.I. Fan. Improved low-computation partially blind signatures. Applied Mathematicsand Computation, Vol. 145, Issue:2-3:853–867, 2003.
[10] N. Koblitz and J. Menezes. Another look at”provable security”. Technical report,Research Report. Waterloo University., 2004.
[11] N. Koblitz and J. Menezes. Another look at”provable security”. ii. Technical report,Research Report. Waterloo University., 2006.
[12] C. Shannon. Communication theory of secrecy systems. Bell Systems Technical Jour-nal, 28(4):656–715, 1949.
[13] R. Cramer and V. Shoup. A practical public key cryptosystem provably secure againstadaptive chosen ciphertext attack. In Advances in Cryptology-Crypto’98, volumeLNCS 1462, pages 13–25, 1998.
[14] R. Cramer and V. Shoup. Signature schemes based on the strong rsa assumption. ACMTransactions on Information and System Security, 3(3):161–185, 2000. extendedabstract in Proc. 6th ACM Conf. on Computer and Communications Security, 1999.
[15] M. Bellare. Practice-oriented provable-security. In I. Damgard, editor, Lectures onData Security, volume LNCS 1561, pages 1–15, 1999.
[16] J. Stern. Why provable security matters. In E. Biham, editor, EUROCRYPT 2003,volume LNCS 2656, page 449–461, 2003.
[17] M. Bellare and P. Rogaway. Random oracles are practical-a paradigm for designingefficient protocols. In Proceedings of the First ACM Conference on Computer andCommunications Security, pages 62–73, 1993.
[18] M. Bellare and P. Rogaway. The exact security of digital signatures - how to signwith rsa and rabin. In U. Maurer, editor, Advances in Cryptology - Proceedings ofEUROCRYPT’96, volume LNCS 1070, pages 399–416, 1996.
[19] M. Bellare and P. Rogaway. Optimal asymmetric encryption—how to encrypt withrsa. In Advances in Cryptology– EUROCRYPT’94, volume LNCS 950, pages 92–111. Springer-Verlag, 1995.
[20] E. Fujisaki and T. Okamoto. Secure integration of asymmetric and symmetric en-cryption schemes. In Advances in Cryptology-Crypto’99, volume LNCS 1666, pages537–554, 1999.
[21] Y. Watanabe, J. Shikata, and H. Imai. Equivalence between semantic security andindistinguishability against chosen ciphertext attacks. In PKC 2003, volume LNCS2567 of 71-84, 2003.
[22] D. Bernstein. Proving tight security for standard rabin-williams signatures, preprint.2003.
[12] C. Shannon. Communication theory of secrecy systems. Bell Systems Technical Jour-nal, 28(4):656–715, 1949.
[13] R. Cramer and V. Shoup. A practical public key cryptosystem provably secure againstadaptive chosen ciphertext attack. In Advances in Cryptology-Crypto’98, volumeLNCS 1462, pages 13–25, 1998.
[14] R. Cramer and V. Shoup. Signature schemes based on the strong rsa assumption. ACMTransactions on Information and System Security, 3(3):161–185, 2000. extendedabstract in Proc. 6th ACM Conf. on Computer and Communications Security, 1999.
[15] M. Bellare. Practice-oriented provable-security. In I. Damgard, editor, Lectures onData Security, volume LNCS 1561, pages 1–15, 1999.
[16] J. Stern. Why provable security matters. In E. Biham, editor, EUROCRYPT 2003,volume LNCS 2656, page 449–461, 2003.
[17] M. Bellare and P. Rogaway. Random oracles are practical-a paradigm for designingefficient protocols. In Proceedings of the First ACM Conference on Computer andCommunications Security, pages 62–73, 1993.
[18] M. Bellare and P. Rogaway. The exact security of digital signatures - how to signwith rsa and rabin. In U. Maurer, editor, Advances in Cryptology - Proceedings ofEUROCRYPT’96, volume LNCS 1070, pages 399–416, 1996.
[19] M. Bellare and P. Rogaway. Optimal asymmetric encryption—how to encrypt withrsa. In Advances in Cryptology– EUROCRYPT’94, volume LNCS 950, pages 92–111. Springer-Verlag, 1995.
[20] E. Fujisaki and T. Okamoto. Secure integration of asymmetric and symmetric en-cryption schemes. In Advances in Cryptology-Crypto’99, volume LNCS 1666, pages537–554, 1999.
[21] Y. Watanabe, J. Shikata, and H. Imai. Equivalence between semantic security andindistinguishability against chosen ciphertext attacks. In PKC 2003, volume LNCS2567 of 71-84, 2003.
[22] D. Bernstein. Proving tight security for standard rabin-williams signatures, preprint.2003.
[35] D. N. Duc, J. H. Cheon, and K. Kim. A forward-secure blind signature scheme basedon the strong rsa assumption. In Information and Communications Security 2003,volume LNCS 2836, pages 11–21, 2003.
[36] Sherman S.M. Chow, Siu-Ming Yiu, and Lucas C.K. Hui. Efficient identity based ringsignature. In Applied Cryptography and Network Security 2005, volume LNCS 3531,pages 499–512, 2005.
[37] K. Shim. An identity-based proxy signature scheme from pairings. In Informationand Communications Security 2006, volume LNCS 4307, pages 60–71, 2006.
[38] J. C. Cha and J. H. Cheon. An identity-based signature from gap diffie-hellmangroups. availiable online:http://eprint.iacr.org/2002/018.ps. 2002.
[39] X. Yi. An identity-based signature scheme from the weil pairing. IEEE COMMUNI-CATIONS LETTERS, VOL. 7, NO. 2, 2003.
[40] Z. Shao. Self-certified signature scheme from pairings. Journal of Systems and Soft-ware, Volume 80, Issue 3:388–395, 2007.
[41] U. Feige, A. Fiat, and A. Shamir. Zero-knowledge proofs of identity. In ACMSIGACT, pages 210–217, 1987.
[42] A. Fiat and A. Shamir. How to prove yourself. practical solutions to identificaion andsignature problems. In Advances in Cryptology - CRYPTO’86, volume LNCS 263,pages 186–189, 1986.
[43] K. Ohta and T. Okamoto. On concrete security treatment of signatures derived fromidentification. In Advances in Cryptology - Proceedings of CRYPTO’98, volumeLNCS 1462, pages 345–370, 1998.
[44] PKCS 1 v2.1, RSA Cryptography Standard (draft), document availiable athttp://www.rsa.com/rsalabs/pkcs/.
[45] J. S. Coron. On the exact security of full domain hash. In Advances in Cryptography- Crypto 2000, volume LNCS 1880, pages 229–235, 2000.
[46] J. S. Coron. Optimal security proofs for pss and other signature schemes. In Advancesin Cryptography - Eurocrypt 2002, volume LNCS 2332, pages 272–287, 2002.
[47] J. S. Coron. Security proof for partial-domain hash signature schemes. In Advancesin Cryptography - CRYPTO 2002, volume LNCS 2442, pages 613–626, 2002.
[48] W. Ogata and K. Kurosawa. The security of the fdh variant of chaum’s undeniablesignature scheme. IEEE Transaction on Information Theory, Vol. 52, NO. 5, 2006.
[49] D. Chaum and H. van Antwerpen. Undeniable signatures. In Advances in Cryptology- Crypto’89, volume LNCS 435, pages 212–216, 1989.
[50] A. Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd An-nual Symposium on Foundations of Computer Science, pages 80–91. IEEE ComputerSociety Press, 1982.
[51] M. Blum and S. Micali. How to generate cryptographically strong sequences ofpseudo-random bits. SIAM J. Comput, 13:850–864, 1984.
[52] O. Goldreich, S. Goldwasser, and S. Micali. 210-217. How to construct random func-tions. Journal of ACM, 4:210–217, 1986.
[53] R. C. Merkle. One way hash functions and des. In Advances in Cryptology -Crypto’89, volume LNCS 435, pages 428–446, 1989.
[54] I. Damgard. A design principle for hash functions. In Advances in Cryptology -Crypto’89, volume LNCS 435, pages 416–427, 1989.
[55] D. R. Stinson. Some observations on the theory of cryptographic hash functions,research report. Technical report, Waterloo University, 2001.
[56] NIST. FIPS 180-1, Secure hash standard, Federal Information Processing StandardsPublication 180-1. NIST, April 1995.
[57] R. L. Rivest. RFC 1321, The MD5 message-digest algorithm, Internet Request forComments., 2002.
[58] X. Wang and H. Yu. How to break md5 and other hash functions. In Advances inCryptology - EUROCRYPT 2005, volume LNCS 3494, pages 19–35, 2005.
[59] X. Wang, Y. L. Yin, and H. Yu. Finding collisions in the full sha-1. In Advances inCryptology - CRYPTO 2005, volume LNCS 3621, pages 17–36, 2005.
[60] X. Wang, H. Yu, and Y. L. Yin. Efficient collision search attacks on sha-0. In Advancesin Cryptology - CRYPTO 2005, volume LNCS 3621, pages 1–16, 2005.
[61] R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited.In STOC’98. ACM, 1998.
[62] R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revis-ited.(full version). Journal of ACM, Vol. 51, NO.4:557–594, July 2004.
[63] R. Canetti, O. Goldreich, and S. Halevi. On the random oracle methodology as ap-plied to length-restricted signature schemes. In Proceedings of Theory of CryptologyConference, volume LNCS 2951, pages 40–57, 2002.
[64] S. Goldwasser and Y. Tauman. On the (in)security of the fiat-shamir paradigm. InFOCS 2003, pages 102–114, 2003.
[65] J. B. Nielsen. Separating random oracle proofs from complexity theoretic proofs: Thenon-committing encryption case. In Advances in Cryptology - Crypto 2002, volumeLNCS 2442, pages 111–126, 2002.
[66] M. Bellare, A. Boldyreva, and A. Palacio. An uninstantiable random-oracle-modelscheme for a hybrid-encryption problem. In Advances in Cryptology - Eurocrypt2004, 2004.
[67] A. Boldyreva and M. Fischlin. Analysis of random oracle instantiation scenarios foroaep and other practical schemes. In V. Shoup, editor, Advances in Cryptology -Crypto 2005, volume LNCS 3621, pages 412–429, 2005.
[68] Y. Dodis, R. Oliveira, and K. Pietrzak. On the generic insecurity of the full domainhash. In Advances in Cryptology - Crypto 2005, 2005.
[69] I. Mironov. Collision-resistant no more:hash-and-sign paradigm revisited. In M. Yunget al., editor, PKC 2006, volume LNCS 3958, pages 140–156, 2006.
[70] S. Halevi and H. Krawczyk. Strengthening digital signatures via randomized hashing.internet-draft, crypto forum research group. May 2005.
[71] S. Halevi and H. Krawczyk. Strengthening digital signatures via randomized hashing.talk at cryptographic hash workshop(nist). Oct31-Nov 1 2005.
[72] V. Shoup. Using hash functions as a hedge against chosen ciphertext attack. In Ad-vances in Cryptology - EUROCRYPT 2000, volume LNCS 1807, pages 275–288,2000.
[73] B. Barak. Constant-round coin-tossing with a man in the middle or realizing the sharedrandom string model. In Proccedings of the 43rd Annual Symposium on Foundationsof Computer Science, pages 345–355. IEEE Computer Society Press, 2002.
[74] R. Canetti. Towards realizing random oracles: Hash functions that hide all partialinformation. In Advances in Cryptology - CRYPTO’97, volume LNCS 1294, pages455–469, 1997.
[75] R. Canetti, D. Micciancio, and O. Reingold. Perfectly one-way probabilistic hashing.In Proceedings of the 30th Annual ACM Symposium on the Theory of Computing,pages 131–140. ACM, 1998.
[76] U. Maurer, R. Renner, and C. Holenstein. Indifferentiability, impossibility results onreductions, and applications to the random oracle methodology. In M. Naor, editor,TCC 2004, volume LNCS 2951, pages 21–39, 2004.
[77] J. S. Coron, Y. Dodis, C. Malinaud, and P. Puniya. Merkle-damgard revisited: Howto construct a hash function. In Advances in Cryptology - Crypto’05, volume LNCS3621, pages 21–39, 2005.
[78] D. Chang, S. Lee, M. Nandi, and M. Yung. Indifferentiable security analysis of pop-ular hash functions with prefix-free padding. In X. Lai and K. Chen, editors, ASI-ACRYPT 2006, volume LNCS 4284, pages 283–298, 2006.
[79] B. Preneel, R. Govaerts, and J. Vandewalle. Hash functions based on block ciphers:A synthetic approach. In Advances in Cryptology-Crypto’1993, volume LNCS 773,pages 368–378, 1994.
[80] M. Bellare and T. Ristenpart. Multi-property-preserving hash domain extension andthe emd transform. In X. Lai and K. Chen, editors, ASIACRYPT 2006, volume LNCS4284, pages 299–314, 2006.
[81] J. Black, P. Rogaway, and T. Shrimpton. Black-box analysis of the block-cipher-basedhash-function constructions from pgv. In Advances in Cryptology - CRYPTO’02, vol-ume LNCS 2442, pages 320–335, 2002.
[82] B. Preneel, Bosselaers A, R. Govaerts, and J. Vandewalle. Collision-free hash-functions based on blockcipher algorithms. In Proceeding of 1989 International Car-nahan Conference on Security Technology, pages 203–210, 1989.
[83] B.O. Brachtl, D. Coppersmith, M.M. Hyden, S.M.Matyas, C.H. Meyer, J. Oseas, S.Pilpel, and M. Schilling. Data Authentication Using Modification Detection CodesBased on a Publick One Way Encryption Function. U.S. Patent Number 4,908,861,March 13 1990.
[84] S. Lucks. A failure-friendly design principle for hash functions. In ASIACRYPT 2005,volume LNCS 3788, pages 474–494, 2005.
[85] S. Hirose. Some plausible constructions of double-block-length hash functions. InFSE 2006, volume LNCS 4047, pages 210–225, 2006.
[86] D. Brown. Generic groups, collision resistance, and ecdsa. Preprint, Available athttp://eprint.iacr.org/2002/026, 2002.
[87] P. Paillier and D. Vergnaud. Discrete-log-based signatures may not be equivalent todiscrete log. In ASIACRYPT 2005, volume LNCS 3788, pages 1–20, 2005.
[88] A. Dent. Adapting the weakness of the random oracle to the generic model. In ASI-ACRYPT 2002, volume LNCS 2501, pages 101–109, 2002.
[89] L.R. Knudsen, X. Lai, and B. Preneel. Attacks on fast double block length hashfunctions. Journal of Cryptology, 11:59–72, 1998.
[90] X. Lai and J. L. Massey. Hash functions based on block ciphers. In Advances inCryptology-Eurocrypt’92, volume LNCS 658, pages 55–70, 1993.
[91] P. Rogaway and T. Shrimpton. Cryptographic hash-function basics: Definitions, im-plications, and separations for preimage resistance, second-preimage resistance andcollision resistance. In FSE 2004, volume LNCS 3017, pages 371–388, 2004.
[92] L. Brown, J. Pieprzyk, and J. Seberry. Loki-a cryptographic primitive for authenti-cation and secrecy applications. In J. Seberry and J. Pieprzyk, editors, Advances inCryptology-Proc. AusCrypt’90, volume LNCS 453, pages 229–236. Springer-Verlag,Berlin, 1990.
[93] W. Hohl, X. Lai, T. Meier, and C. Waldvogel. Security of iterated hash function basedon block ciphers. In CRYPTO’93, volume LNCS 773, pages 379–390, 1993.
[94] X. Yi and K.Y. Lam. A new hash function based on block cipher. In ACISP’97Information Security and Privacy, volume LNCS 1270, pages 139–146. Springer-Verlag, 1997.
[95] M. Nandi. Design of Iteration on Hash Functions and Its Cryptanalysis. PhD thesis,Indian Statistical Institute, 2005.
[96] M. Nandi. Towards optimal double-length hash functions. In INDOCRYPT 2005,volume LNCS 3797, page 77–89, 2005.
[97] T. Satoh, M. Haga, and K. Kurosawa. Towards secure and fast hash functions. IEICETrans. Fundamentals, Vol. E82-A, NO.1:55–62, 1999.
[98] S. Hirose. A security analysis of double-block-length hash functions with the rate 1.IEICE Trans. Fundamentals, Vol. E89-A, NO.10:2575–2582, 2006.
[99] J. Black. The ideal-cipher model, revisited: An uninstantiable blockcipher-based hashfunction. In FSE 2006, volume LNCS 4047, pages 328–340, 2006.
[100] L.R. Knudsen. Block Ciphers-Analysis, Design and Applications. PhD thesis, AarthusUniversity, 1994.
[101] Zheng Gong, Xuejia Lai, and Kefei Chen. A synthetic indifferentiability analysis ofsome block-cipher-based hash functions. Designs, Codes and Cryptography, 2008.
[102] A. Joux. Multicollisions in iterated hash functions, application to cascaded construc-tions. In Crypto’04, volume LNCS 3152, page 306–316, 2004.
[103] J. Kelsey and B. Schneier. Second preimages on n-bit hash functions for much lessthan 2n work. In EUROCRYPT’05, volume LNCS 3494, pages 474–490, 2005.
[104] D. Chaum. Blind signature for untraceable payments. In Advances in Cryptology -Crypto’82, pages 199–203, 1983.
[105] M. Abe and E. Fujisaki. How to date blind signatures. In Advances in Cryptology -ASIACRYPT’96, volume LNCS 1163, pages 244–251, 1996.
[106] T.J. Cao, L.D. Dai, and R. Xue. A randomized rsa-based partially blind signaturescheme for electronic cash. Computer & Security, 24:(1):44–49, 2005.
[107] M. Abe and T. Okamoto. Provable secure partially blind signatures. In Advances inCryptology - Crypto’00, volume LNCS 1880, pages 271–286, 2000.
[108] G. Maitland and C. Boyd. A provably secure restrictive partially blind signaturescheme. In PKC 2002, volume LNCS 2274, pages 99–114, 2002.
[109] F.G Zhang, R. Safavi-Naini, and W. Susilo. Efficient verifiably encrypted signatureand partially blind signature from bilinear pairings. In INDOCRYTP 2003, volumeLNCS 2904, pages 191–204, 2003.
[110] S.M. Sherman, Lucas C.K. Hui, S.M. Yiu, and K.P. Chow. Two improved partiallyblind signature schemes from bilinear pairings. In ACISP 2005, volume LNCS 3574,pages 316–328, 2005.
[111] Q. Wu, W. Susilo, and et al. Efficient partially blind signatures with provable security.In ICCSA 2006, volume LNCS 3982, page 345–354, 2006.
[112] T. Okamoto. Efficient blind and partially blind signatures without random oracles. InTCC 2006, volume LNCS 3876, page 80–99, 2006.
[113] K.C. Barr and K. Asanovic. Energy aware lossless data compression. In Proc. ofMobisys, 2005.
[114] K.J. Giulian and G. Gong. New lfsr-based cryptosystems and the trace discrete logproblem (trace-dlp). In SETA 2004, volume LNCS 3486, pages 298–312, 2004.
[115] G. Gong and L. Harn. Public-key cryptosystems based on cubic finite field extensions.IEEE Trans. IT, 24:2601–2605, 1999.
[116] A. Lenstra and E. Verheul. The xtr public key system. In Advances in Cryptology-Crypto’00, volume LNCS 1880, pages 1–19, 2000.
[117] P. Smith and C. Skinner. A public-key cryptosystem and a digital signature sys-tem based on the lucas function analogue to discrete logarithms. In Advances inCryptopogy-Asiacrypt’94, volume LNCS 917, pages 357–364, 1994.
[118] H. Niederreiter. Finite fields and cryptology. In M.Dekker, editor, Finite Fields,Coding Theory, and Advances in Communications and Computing, pages 359–373,New York (1993), 1993.
[119] C. Tan, X. Yi, and C. Siew. On the n-th order shift register based discrete logarithm.IEICE Trans. Fundamentals, E86-A:1213–1216, 2003.
[120] S. Golomb. Shift Register Sequences. Laguna Hills,, 1982.
[121] C.M. Fiduccia. An efficient formula for linear recurrences. SIAM J. Comput, 14:106–112, 1985.
[122] X. Li, Dong Zheng, and Kefei Chen. Lfsr-based signatures with message recovery.International Journal of Network Security, 4(3):266–270, 2007.
[123] S. Sin. Gh-pkc software implementation. Technical report, Waterloo University,http://comsec.uwaterloo.ca/projects.html#gh.
[124] A. Shamir. Identity-based cryptosystems and signature schemes. In Advances inCryptology-Crypto’84, volume LNCS 196, pages 47–53, 1985.
[125] S. S. Al-Riyami and K. G. Paterson. Certificateless public key cryptography. InAdvances in Cryptography-Asiacrypt’03, volume LNCS 2894, pages 452–473, 2003.
[126] M. Girault. Self-certified public keys. In D.W. Davies., editor, EUROCRYPT 1991,volume LNCS 547, page 490–497, 1992.
[127] D. H. Yum and P. J. Lee. Generic construction of certificateless signature. In In-formation Security and Privacy, ACISP 2004, volume LNCS 3108, pages 200–211,2004.
[128] X. Huang, W. Susilo, Y. Mu, and F. Zhang. On the security of certificateless signatureschemes from asiacrypt 2003. In CANS 2005, volume LNCS 3810, pages 13–25,2005.
[129] D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably en-crypted signatures from blinear maps. In E. Biham, editor, Advances in Cryptology-EUROCRYPT’03, volume LNCS 2656, pages 416–432, 2003.
[130] D. Boneh, B. Lynn, and H. Shacham. Short signatures from weil pairing. In C. Boyd,editor, Advances in Cryptology-ASIACRYPT’01, volume LNCS 2248, pages 514–532,2001.
[131] D. Boneh, C. Gentry, and H. Shacham. A survey of two signature aggregationtechiques. RSA’s CryptoBytes, 6(2), 2003.
[132] X. G. Cheng, J. M. Liu, and X. M. Wang. Identity-based aggregate and verifiablyencrypted signatures from bilinear pairing. In ICCSA 2005, volume LNCS 3483,pages 1046–1054, 2005.
[133] Z.H. Shao. Enhanced aggregate signatures from pairings. In D. Feng, D. Lin, and M.Yung, editors, CISC 2005, volume LNCS 3822, pages 140–149, 2005.
[134] J. Xu, Z. F. Zhang, and D. G. Feng. Id-based aggregate signatures from bilinearpairings. In CANS 2005, volume LNCS 3810, pages 110–119, 2005.
[135] M. Bellare, C. Namprempre, and G. Neven. Unrestricted aggregate signatures. InICALP’07, volume LNCS 4596, pages 411–422, 2007.
[136] C. Gentry and Z. Ramzan. Identity-based aggregate signatures. In PKC 2006, volumeLNCS 3958, pages 257–273, 2006.
[137] S. Goldwasser, S. Micali, and R.L. Rivest. A digital signature scheme secure againstadaptive chosen-message attacks. SIAM J. Computing, 17(2):281–308, 1988.
[2] M. Rabin. Digitized signatures and public-key functions as intractible as factoriza-tion. Technical report, Technical Report LCS/TR-212, MIT Laboratory for ComputerScience, 1979.
[3] R. Merkle and M. Hellman. Hiding information and signatures in trapdoor knapsacks.IEEE Transaction on Information Theory, 24:525–530, 1978.
[4] Wenbo Mao. Modern Cryptography: Theory and Practice. Publishing house of Elec-tronic Industry, 2004.
[5] H.Y. Chien, J.K. Jan, and Y.M. Tseng. Rsa-based partially blind signature with lowcomputation. In Proceedings of the eighth international conference on parallel anddistributed systems, pages 385–389, 2001.
[6] M.S Kwon and Y.K Cho. Randomization enhanced blind signature schemes based onrsa. IEICE A Fundam, E86-A(3):730–733, 2003.
[7] H.F. Huang and C.C Chang. A new design of efficient partially blind signaturescheme. Journal of Systems and Software, 73(3):pp.397–403, 2003.
[8] C.I. Fan and C.L. Lei. Low-computation partially blind signatures for electronic cash.IEICE Transaction on Fundamentals of Electronics, Communications and ComputerSciences, E81-A(5):818–824, 1998.
[9] C.I. Fan. Improved low-computation partially blind signatures. Applied Mathematicsand Computation, Vol. 145, Issue:2-3:853–867, 2003.
[10] N. Koblitz and J. Menezes. Another look at”provable security”. Technical report,Research Report. Waterloo University., 2004.
[11] N. Koblitz and J. Menezes. Another look at”provable security”. ii. Technical report,Research Report. Waterloo University., 2006.
[12] C. Shannon. Communication theory of secrecy systems. Bell Systems Technical Jour-nal, 28(4):656–715, 1949.
[13] R. Cramer and V. Shoup. A practical public key cryptosystem provably secure againstadaptive chosen ciphertext attack. In Advances in Cryptology-Crypto’98, volumeLNCS 1462, pages 13–25, 1998.
[14] R. Cramer and V. Shoup. Signature schemes based on the strong rsa assumption. ACMTransactions on Information and System Security, 3(3):161–185, 2000. extendedabstract in Proc. 6th ACM Conf. on Computer and Communications Security, 1999.
[15] M. Bellare. Practice-oriented provable-security. In I. Damgard, editor, Lectures onData Security, volume LNCS 1561, pages 1–15, 1999.
[16] J. Stern. Why provable security matters. In E. Biham, editor, EUROCRYPT 2003,volume LNCS 2656, page 449–461, 2003.
[17] M. Bellare and P. Rogaway. Random oracles are practical-a paradigm for designingefficient protocols. In Proceedings of the First ACM Conference on Computer andCommunications Security, pages 62–73, 1993.
[18] M. Bellare and P. Rogaway. The exact security of digital signatures - how to signwith rsa and rabin. In U. Maurer, editor, Advances in Cryptology - Proceedings ofEUROCRYPT’96, volume LNCS 1070, pages 399–416, 1996.
[19] M. Bellare and P. Rogaway. Optimal asymmetric encryption—how to encrypt withrsa. In Advances in Cryptology– EUROCRYPT’94, volume LNCS 950, pages 92–111. Springer-Verlag, 1995.
[20] E. Fujisaki and T. Okamoto. Secure integration of asymmetric and symmetric en-cryption schemes. In Advances in Cryptology-Crypto’99, volume LNCS 1666, pages537–554, 1999.
[21] Y. Watanabe, J. Shikata, and H. Imai. Equivalence between semantic security andindistinguishability against chosen ciphertext attacks. In PKC 2003, volume LNCS2567 of 71-84, 2003.
[22] D. Bernstein. Proving tight security for standard rabin-williams signatures, preprint.2003.
[12] C. Shannon. Communication theory of secrecy systems. Bell Systems Technical Jour-nal, 28(4):656–715, 1949.
[13] R. Cramer and V. Shoup. A practical public key cryptosystem provably secure againstadaptive chosen ciphertext attack. In Advances in Cryptology-Crypto’98, volumeLNCS 1462, pages 13–25, 1998.
[14] R. Cramer and V. Shoup. Signature schemes based on the strong rsa assumption. ACMTransactions on Information and System Security, 3(3):161–185, 2000. extendedabstract in Proc. 6th ACM Conf. on Computer and Communications Security, 1999.
[15] M. Bellare. Practice-oriented provable-security. In I. Damgard, editor, Lectures onData Security, volume LNCS 1561, pages 1–15, 1999.
[16] J. Stern. Why provable security matters. In E. Biham, editor, EUROCRYPT 2003,volume LNCS 2656, page 449–461, 2003.
[17] M. Bellare and P. Rogaway. Random oracles are practical-a paradigm for designingefficient protocols. In Proceedings of the First ACM Conference on Computer andCommunications Security, pages 62–73, 1993.
[18] M. Bellare and P. Rogaway. The exact security of digital signatures - how to signwith rsa and rabin. In U. Maurer, editor, Advances in Cryptology - Proceedings ofEUROCRYPT’96, volume LNCS 1070, pages 399–416, 1996.
[19] M. Bellare and P. Rogaway. Optimal asymmetric encryption—how to encrypt withrsa. In Advances in Cryptology– EUROCRYPT’94, volume LNCS 950, pages 92–111. Springer-Verlag, 1995.
[20] E. Fujisaki and T. Okamoto. Secure integration of asymmetric and symmetric en-cryption schemes. In Advances in Cryptology-Crypto’99, volume LNCS 1666, pages537–554, 1999.
[21] Y. Watanabe, J. Shikata, and H. Imai. Equivalence between semantic security andindistinguishability against chosen ciphertext attacks. In PKC 2003, volume LNCS2567 of 71-84, 2003.
[22] D. Bernstein. Proving tight security for standard rabin-williams signatures, preprint.2003.
[35] D. N. Duc, J. H. Cheon, and K. Kim. A forward-secure blind signature scheme basedon the strong rsa assumption. In Information and Communications Security 2003,volume LNCS 2836, pages 11–21, 2003.
[36] Sherman S.M. Chow, Siu-Ming Yiu, and Lucas C.K. Hui. Efficient identity based ringsignature. In Applied Cryptography and Network Security 2005, volume LNCS 3531,pages 499–512, 2005.
[37] K. Shim. An identity-based proxy signature scheme from pairings. In Informationand Communications Security 2006, volume LNCS 4307, pages 60–71, 2006.
[38] J. C. Cha and J. H. Cheon. An identity-based signature from gap diffie-hellmangroups. availiable online:http://eprint.iacr.org/2002/018.ps. 2002.
[39] X. Yi. An identity-based signature scheme from the weil pairing. IEEE COMMUNI-CATIONS LETTERS, VOL. 7, NO. 2, 2003.
[40] Z. Shao. Self-certified signature scheme from pairings. Journal of Systems and Soft-ware, Volume 80, Issue 3:388–395, 2007.
[41] U. Feige, A. Fiat, and A. Shamir. Zero-knowledge proofs of identity. In ACMSIGACT, pages 210–217, 1987.
[42] A. Fiat and A. Shamir. How to prove yourself. practical solutions to identificaion andsignature problems. In Advances in Cryptology - CRYPTO’86, volume LNCS 263,pages 186–189, 1986.
[43] K. Ohta and T. Okamoto. On concrete security treatment of signatures derived fromidentification. In Advances in Cryptology - Proceedings of CRYPTO’98, volumeLNCS 1462, pages 345–370, 1998.
[44] PKCS 1 v2.1, RSA Cryptography Standard (draft), document availiable athttp://www.rsa.com/rsalabs/pkcs/.
[45] J. S. Coron. On the exact security of full domain hash. In Advances in Cryptography- Crypto 2000, volume LNCS 1880, pages 229–235, 2000.
[46] J. S. Coron. Optimal security proofs for pss and other signature schemes. In Advancesin Cryptography - Eurocrypt 2002, volume LNCS 2332, pages 272–287, 2002.
[47] J. S. Coron. Security proof for partial-domain hash signature schemes. In Advancesin Cryptography - CRYPTO 2002, volume LNCS 2442, pages 613–626, 2002.
[48] W. Ogata and K. Kurosawa. The security of the fdh variant of chaum’s undeniablesignature scheme. IEEE Transaction on Information Theory, Vol. 52, NO. 5, 2006.
[49] D. Chaum and H. van Antwerpen. Undeniable signatures. In Advances in Cryptology- Crypto’89, volume LNCS 435, pages 212–216, 1989.
[50] A. Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd An-nual Symposium on Foundations of Computer Science, pages 80–91. IEEE ComputerSociety Press, 1982.
[51] M. Blum and S. Micali. How to generate cryptographically strong sequences ofpseudo-random bits. SIAM J. Comput, 13:850–864, 1984.
[52] O. Goldreich, S. Goldwasser, and S. Micali. 210-217. How to construct random func-tions. Journal of ACM, 4:210–217, 1986.
[53] R. C. Merkle. One way hash functions and des. In Advances in Cryptology -Crypto’89, volume LNCS 435, pages 428–446, 1989.
[54] I. Damgard. A design principle for hash functions. In Advances in Cryptology -Crypto’89, volume LNCS 435, pages 416–427, 1989.
[55] D. R. Stinson. Some observations on the theory of cryptographic hash functions,research report. Technical report, Waterloo University, 2001.
[56] NIST. FIPS 180-1, Secure hash standard, Federal Information Processing StandardsPublication 180-1. NIST, April 1995.
[57] R. L. Rivest. RFC 1321, The MD5 message-digest algorithm, Internet Request forComments., 2002.
[58] X. Wang and H. Yu. How to break md5 and other hash functions. In Advances inCryptology - EUROCRYPT 2005, volume LNCS 3494, pages 19–35, 2005.
[59] X. Wang, Y. L. Yin, and H. Yu. Finding collisions in the full sha-1. In Advances inCryptology - CRYPTO 2005, volume LNCS 3621, pages 17–36, 2005.
[60] X. Wang, H. Yu, and Y. L. Yin. Efficient collision search attacks on sha-0. In Advancesin Cryptology - CRYPTO 2005, volume LNCS 3621, pages 1–16, 2005.
[61] R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited.In STOC’98. ACM, 1998.
[62] R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revis-ited.(full version). Journal of ACM, Vol. 51, NO.4:557–594, July 2004.
[63] R. Canetti, O. Goldreich, and S. Halevi. On the random oracle methodology as ap-plied to length-restricted signature schemes. In Proceedings of Theory of CryptologyConference, volume LNCS 2951, pages 40–57, 2002.
[64] S. Goldwasser and Y. Tauman. On the (in)security of the fiat-shamir paradigm. InFOCS 2003, pages 102–114, 2003.
[65] J. B. Nielsen. Separating random oracle proofs from complexity theoretic proofs: Thenon-committing encryption case. In Advances in Cryptology - Crypto 2002, volumeLNCS 2442, pages 111–126, 2002.
[66] M. Bellare, A. Boldyreva, and A. Palacio. An uninstantiable random-oracle-modelscheme for a hybrid-encryption problem. In Advances in Cryptology - Eurocrypt2004, 2004.
[67] A. Boldyreva and M. Fischlin. Analysis of random oracle instantiation scenarios foroaep and other practical schemes. In V. Shoup, editor, Advances in Cryptology -Crypto 2005, volume LNCS 3621, pages 412–429, 2005.
[68] Y. Dodis, R. Oliveira, and K. Pietrzak. On the generic insecurity of the full domainhash. In Advances in Cryptology - Crypto 2005, 2005.
[69] I. Mironov. Collision-resistant no more:hash-and-sign paradigm revisited. In M. Yunget al., editor, PKC 2006, volume LNCS 3958, pages 140–156, 2006.
[70] S. Halevi and H. Krawczyk. Strengthening digital signatures via randomized hashing.internet-draft, crypto forum research group. May 2005.
[71] S. Halevi and H. Krawczyk. Strengthening digital signatures via randomized hashing.talk at cryptographic hash workshop(nist). Oct31-Nov 1 2005.
[72] V. Shoup. Using hash functions as a hedge against chosen ciphertext attack. In Ad-vances in Cryptology - EUROCRYPT 2000, volume LNCS 1807, pages 275–288,2000.
[73] B. Barak. Constant-round coin-tossing with a man in the middle or realizing the sharedrandom string model. In Proccedings of the 43rd Annual Symposium on Foundationsof Computer Science, pages 345–355. IEEE Computer Society Press, 2002.
[74] R. Canetti. Towards realizing random oracles: Hash functions that hide all partialinformation. In Advances in Cryptology - CRYPTO’97, volume LNCS 1294, pages455–469, 1997.
[75] R. Canetti, D. Micciancio, and O. Reingold. Perfectly one-way probabilistic hashing.In Proceedings of the 30th Annual ACM Symposium on the Theory of Computing,pages 131–140. ACM, 1998.
[76] U. Maurer, R. Renner, and C. Holenstein. Indifferentiability, impossibility results onreductions, and applications to the random oracle methodology. In M. Naor, editor,TCC 2004, volume LNCS 2951, pages 21–39, 2004.
[77] J. S. Coron, Y. Dodis, C. Malinaud, and P. Puniya. Merkle-damgard revisited: Howto construct a hash function. In Advances in Cryptology - Crypto’05, volume LNCS3621, pages 21–39, 2005.
[78] D. Chang, S. Lee, M. Nandi, and M. Yung. Indifferentiable security analysis of pop-ular hash functions with prefix-free padding. In X. Lai and K. Chen, editors, ASI-ACRYPT 2006, volume LNCS 4284, pages 283–298, 2006.
[79] B. Preneel, R. Govaerts, and J. Vandewalle. Hash functions based on block ciphers:A synthetic approach. In Advances in Cryptology-Crypto’1993, volume LNCS 773,pages 368–378, 1994.
[80] M. Bellare and T. Ristenpart. Multi-property-preserving hash domain extension andthe emd transform. In X. Lai and K. Chen, editors, ASIACRYPT 2006, volume LNCS4284, pages 299–314, 2006.
[81] J. Black, P. Rogaway, and T. Shrimpton. Black-box analysis of the block-cipher-basedhash-function constructions from pgv. In Advances in Cryptology - CRYPTO’02, vol-ume LNCS 2442, pages 320–335, 2002.
[82] B. Preneel, Bosselaers A, R. Govaerts, and J. Vandewalle. Collision-free hash-functions based on blockcipher algorithms. In Proceeding of 1989 International Car-nahan Conference on Security Technology, pages 203–210, 1989.
[83] B.O. Brachtl, D. Coppersmith, M.M. Hyden, S.M.Matyas, C.H. Meyer, J. Oseas, S.Pilpel, and M. Schilling. Data Authentication Using Modification Detection CodesBased on a Publick One Way Encryption Function. U.S. Patent Number 4,908,861,March 13 1990.
[84] S. Lucks. A failure-friendly design principle for hash functions. In ASIACRYPT 2005,volume LNCS 3788, pages 474–494, 2005.
[85] S. Hirose. Some plausible constructions of double-block-length hash functions. InFSE 2006, volume LNCS 4047, pages 210–225, 2006.
[86] D. Brown. Generic groups, collision resistance, and ecdsa. Preprint, Available athttp://eprint.iacr.org/2002/026, 2002.
[87] P. Paillier and D. Vergnaud. Discrete-log-based signatures may not be equivalent todiscrete log. In ASIACRYPT 2005, volume LNCS 3788, pages 1–20, 2005.
[88] A. Dent. Adapting the weakness of the random oracle to the generic model. In ASI-ACRYPT 2002, volume LNCS 2501, pages 101–109, 2002.
[89] L.R. Knudsen, X. Lai, and B. Preneel. Attacks on fast double block length hashfunctions. Journal of Cryptology, 11:59–72, 1998.
[90] X. Lai and J. L. Massey. Hash functions based on block ciphers. In Advances inCryptology-Eurocrypt’92, volume LNCS 658, pages 55–70, 1993.
[91] P. Rogaway and T. Shrimpton. Cryptographic hash-function basics: Definitions, im-plications, and separations for preimage resistance, second-preimage resistance andcollision resistance. In FSE 2004, volume LNCS 3017, pages 371–388, 2004.
[92] L. Brown, J. Pieprzyk, and J. Seberry. Loki-a cryptographic primitive for authenti-cation and secrecy applications. In J. Seberry and J. Pieprzyk, editors, Advances inCryptology-Proc. AusCrypt’90, volume LNCS 453, pages 229–236. Springer-Verlag,Berlin, 1990.
[93] W. Hohl, X. Lai, T. Meier, and C. Waldvogel. Security of iterated hash function basedon block ciphers. In CRYPTO’93, volume LNCS 773, pages 379–390, 1993.
[94] X. Yi and K.Y. Lam. A new hash function based on block cipher. In ACISP’97Information Security and Privacy, volume LNCS 1270, pages 139–146. Springer-Verlag, 1997.
[95] M. Nandi. Design of Iteration on Hash Functions and Its Cryptanalysis. PhD thesis,Indian Statistical Institute, 2005.
[96] M. Nandi. Towards optimal double-length hash functions. In INDOCRYPT 2005,volume LNCS 3797, page 77–89, 2005.
[97] T. Satoh, M. Haga, and K. Kurosawa. Towards secure and fast hash functions. IEICETrans. Fundamentals, Vol. E82-A, NO.1:55–62, 1999.
[98] S. Hirose. A security analysis of double-block-length hash functions with the rate 1.IEICE Trans. Fundamentals, Vol. E89-A, NO.10:2575–2582, 2006.
[99] J. Black. The ideal-cipher model, revisited: An uninstantiable blockcipher-based hashfunction. In FSE 2006, volume LNCS 4047, pages 328–340, 2006.
[100] L.R. Knudsen. Block Ciphers-Analysis, Design and Applications. PhD thesis, AarthusUniversity, 1994.
[101] Zheng Gong, Xuejia Lai, and Kefei Chen. A synthetic indifferentiability analysis ofsome block-cipher-based hash functions. Designs, Codes and Cryptography, 2008.
[102] A. Joux. Multicollisions in iterated hash functions, application to cascaded construc-tions. In Crypto’04, volume LNCS 3152, page 306–316, 2004.
[103] J. Kelsey and B. Schneier. Second preimages on n-bit hash functions for much lessthan 2n work. In EUROCRYPT’05, volume LNCS 3494, pages 474–490, 2005.
[104] D. Chaum. Blind signature for untraceable payments. In Advances in Cryptology -Crypto’82, pages 199–203, 1983.
[105] M. Abe and E. Fujisaki. How to date blind signatures. In Advances in Cryptology -ASIACRYPT’96, volume LNCS 1163, pages 244–251, 1996.
[106] T.J. Cao, L.D. Dai, and R. Xue. A randomized rsa-based partially blind signaturescheme for electronic cash. Computer & Security, 24:(1):44–49, 2005.
[107] M. Abe and T. Okamoto. Provable secure partially blind signatures. In Advances inCryptology - Crypto’00, volume LNCS 1880, pages 271–286, 2000.
[108] G. Maitland and C. Boyd. A provably secure restrictive partially blind signaturescheme. In PKC 2002, volume LNCS 2274, pages 99–114, 2002.
[109] F.G Zhang, R. Safavi-Naini, and W. Susilo. Efficient verifiably encrypted signatureand partially blind signature from bilinear pairings. In INDOCRYTP 2003, volumeLNCS 2904, pages 191–204, 2003.
[110] S.M. Sherman, Lucas C.K. Hui, S.M. Yiu, and K.P. Chow. Two improved partiallyblind signature schemes from bilinear pairings. In ACISP 2005, volume LNCS 3574,pages 316–328, 2005.
[111] Q. Wu, W. Susilo, and et al. Efficient partially blind signatures with provable security.In ICCSA 2006, volume LNCS 3982, page 345–354, 2006.
[112] T. Okamoto. Efficient blind and partially blind signatures without random oracles. InTCC 2006, volume LNCS 3876, page 80–99, 2006.
[113] K.C. Barr and K. Asanovic. Energy aware lossless data compression. In Proc. ofMobisys, 2005.
[114] K.J. Giulian and G. Gong. New lfsr-based cryptosystems and the trace discrete logproblem (trace-dlp). In SETA 2004, volume LNCS 3486, pages 298–312, 2004.
[115] G. Gong and L. Harn. Public-key cryptosystems based on cubic finite field extensions.IEEE Trans. IT, 24:2601–2605, 1999.
[116] A. Lenstra and E. Verheul. The xtr public key system. In Advances in Cryptology-Crypto’00, volume LNCS 1880, pages 1–19, 2000.
[117] P. Smith and C. Skinner. A public-key cryptosystem and a digital signature sys-tem based on the lucas function analogue to discrete logarithms. In Advances inCryptopogy-Asiacrypt’94, volume LNCS 917, pages 357–364, 1994.
[118] H. Niederreiter. Finite fields and cryptology. In M.Dekker, editor, Finite Fields,Coding Theory, and Advances in Communications and Computing, pages 359–373,New York (1993), 1993.
[119] C. Tan, X. Yi, and C. Siew. On the n-th order shift register based discrete logarithm.IEICE Trans. Fundamentals, E86-A:1213–1216, 2003.
[120] S. Golomb. Shift Register Sequences. Laguna Hills,, 1982.
[121] C.M. Fiduccia. An efficient formula for linear recurrences. SIAM J. Comput, 14:106–112, 1985.
[122] X. Li, Dong Zheng, and Kefei Chen. Lfsr-based signatures with message recovery.International Journal of Network Security, 4(3):266–270, 2007.
[123] S. Sin. Gh-pkc software implementation. Technical report, Waterloo University,http://comsec.uwaterloo.ca/projects.html#gh.
[124] A. Shamir. Identity-based cryptosystems and signature schemes. In Advances inCryptology-Crypto’84, volume LNCS 196, pages 47–53, 1985.
[125] S. S. Al-Riyami and K. G. Paterson. Certificateless public key cryptography. InAdvances in Cryptography-Asiacrypt’03, volume LNCS 2894, pages 452–473, 2003.
[126] M. Girault. Self-certified public keys. In D.W. Davies., editor, EUROCRYPT 1991,volume LNCS 547, page 490–497, 1992.
[127] D. H. Yum and P. J. Lee. Generic construction of certificateless signature. In In-formation Security and Privacy, ACISP 2004, volume LNCS 3108, pages 200–211,2004.
[128] X. Huang, W. Susilo, Y. Mu, and F. Zhang. On the security of certificateless signatureschemes from asiacrypt 2003. In CANS 2005, volume LNCS 3810, pages 13–25,2005.
[129] D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably en-crypted signatures from blinear maps. In E. Biham, editor, Advances in Cryptology-EUROCRYPT’03, volume LNCS 2656, pages 416–432, 2003.
[130] D. Boneh, B. Lynn, and H. Shacham. Short signatures from weil pairing. In C. Boyd,editor, Advances in Cryptology-ASIACRYPT’01, volume LNCS 2248, pages 514–532,2001.
[131] D. Boneh, C. Gentry, and H. Shacham. A survey of two signature aggregationtechiques. RSA’s CryptoBytes, 6(2), 2003.
[132] X. G. Cheng, J. M. Liu, and X. M. Wang. Identity-based aggregate and verifiablyencrypted signatures from bilinear pairing. In ICCSA 2005, volume LNCS 3483,pages 1046–1054, 2005.
[133] Z.H. Shao. Enhanced aggregate signatures from pairings. In D. Feng, D. Lin, and M.Yung, editors, CISC 2005, volume LNCS 3822, pages 140–149, 2005.
[134] J. Xu, Z. F. Zhang, and D. G. Feng. Id-based aggregate signatures from bilinearpairings. In CANS 2005, volume LNCS 3810, pages 110–119, 2005.
[135] M. Bellare, C. Namprempre, and G. Neven. Unrestricted aggregate signatures. InICALP’07, volume LNCS 4596, pages 411–422, 2007.
[136] C. Gentry and Z. Ramzan. Identity-based aggregate signatures. In PKC 2006, volumeLNCS 3958, pages 257–273, 2006.
[137] S. Goldwasser, S. Micali, and R.L. Rivest. A digital signature scheme secure againstadaptive chosen-message attacks. SIAM J. Computing, 17(2):281–308, 1988.