臺灣博碩士論文加值系統

本論文提出一個能在標準模型下基於Φ-hiding假設 [13] 證明安全的EUF-CMA簽章機制，同時我們也發現RSA簽章系統在Φ-hiding假設 [13] 下具有損耗性質，此發現和Kiltz等人在 [39] 不謀而合。此外，自從Shamir和Tauman提出了OnLine/OffLine簽章機制 [39]：OffLine先決定好要簽署訊息的雜湊值，等到OnLine的時候再利用暗門雜湊函數(Trapdoor hash function)的暗門計算OffLine所決定的雜湊值所對應前像之碰撞，利用此概念以及暗門雜湊函數，許多在標準模型下的數位簽章機制應運而生 [5]、[9]、[10]、[11]、[12]、[17]、[23]、[26]、[29]、[32]、[33]、[41]。
利用上述兩個概念，我們嘗試將一直都在隨機智者模型下證明的RSA密碼系統，希望在標準模型下證明其安全性也滿足主動選擇式明文攻擊，以提升其安全性。

We propose an EUF-CMA signature scheme based on Φ-hiding assumption [13] in the standard model. At the mean time, we found the RSA cryptosystem has lossy property [35]. This discovery also found by Kiltz et al [27]. On the orher side, Shamir and Tauman has proposed OnLine/OffLine signature scheme [39]: When OffLine phase, decide the trapdoor hash value until OnLine phase compute the correspond preimage by trapdoor key. Using this primitive, many EUF-CMA signature scheme has been proposed such as [5]、[9]、[10]、[11]、[12]、[17]、[23]、[26]、[29]、[32]、[33]、[41]. We using the two general ideas and try to prove the security of RSA cryptosystem satisfy the EUF-CMA property in the standard model.

摘要 I
Abstract II
目錄 III
圖目錄 V
第一章、 緒論 1
1.1 數位簽章 1
1.2 暗門雜湊函數的介紹 2
1.3 具有資訊損耗的暗門函數 4
1.4 研究動機與貢獻 5
1.5 章節介紹 6
第二章、 基本定義與假設 7
2.1 不可偽造性與可抵抗主動選擇訊息攻擊的不可偽造性 7
2.2 證明技巧 8
2.3 RSA簽章系統 9
2.4 RSA的資訊損耗性質 10
2.5 基於RSA假設的暗門雜湊函數 13
第三章、 標準模型下EUF-CMA安全的簽章機制 17
3.1 機制 17
第四章、 安全性證明 19
4.1 可抵抗主動選擇訊息攻擊的不可偽造性 19
4.2 機率分析 23
第五章、 結論 27
參考文獻 28

[1] G. Ateniese and B. de Medeiros, “On the key-exposure problem in the chamel
eon hashes,” Proc. of the Fourth Conference on Security in Communication N-
etworks(SCN 2004), LNCS, Vol. 3352. Springer, 2005. http://eprint.iacr.org/2004/243
[2] G. Ateniese and B. de Medeiros, “Identity-based chameleon hash and applica-
tions,” Proc. of Financial Cryptography (FC 2004), LNCS, Vol. 3110, pp. 164
-180. Springer, 2004, http://eprint.iacr.org/2003/167
[3] M. Bellare and P. Rogaway, “Random oracles are practical: A paradigm for des-
igning efficient protocols,” Proceedings of the First Annual Conference on Com-
puter and Communication Security, ACM, 1993.
[4] M. Bellare and P. Rogaway, “The exact security of digital signatures - How to si-
gn with RSA and Rabin,” Advances in Cryptology – Eurocrypt’96, LNCS, Vol. 1070, pp.399–416, Springer, 1996.
[5] Dan Boneh and Xavier Boyen, “Short signatures without random oracles,” Adva-
nce in Cryptology Eurocrypt04, LNCS, Vol. 3027 ,Springer pp. 56-73, 2004.
[6] G. Brassard, D. Chaum, and C. Crepeau, “Minimum disclosure proofs of knowle-
dge, ” JCSS, Vol.37,No.2, pp. 156-189, 1988.
[7] X. Chen, F. Zhang, W. Susilo, H. Tian, J. Li, and Kim. K, “Identity-based cham-
eleon hash csheme without key exposure, ” ACISP 2010, LNCS, Vol. 6168, pp. 200–215, Springer, 2010.
[8] J.-S. Coron, “On the exact security of full-domain hash,” Advances in Cryptolo-
gy – Crypto’00, LNCS, Vol. 1880, pp.229–235, Springer, 2000.
[9] B. Chevallier-Mames, “An efficient CDH-based signature scheme with a tight s-
ecurity reduction,” Advances in Cryptology – Crypto’05, LNCS, Vol. 3621, pp.511–526, Springer, 2005.
[10] Cramer and Shoup, “Signature schemes based on the strong RSA assumption,” ACM Trans. Inf. Syst. Secur., Vol. 3, No.3 pp. 161-185, 2000.
[11] J.-S Coron and D. Naccache, “Security analysis of the Gennaro-Halevi-Rabin si-
gnature scheme,” Advances in Cryptology –Eurocrypt’00,LNCS, Vol. 1807, pp. 91-101, 2000.
[12] J. Camenisch and A. Lysyanskaya, “A signature scheme with efficient protocol-
ls,” Security in Communication Networks, Third International International Co-
nference, SCN 2002, LNCS, Vol. 2576, pp. 268 – 289, Springer, 2003.
[13] C. Cachin, “ Efficient private bidding and auctions with an oblivious third par-
ty,” Proc. 6th ACM Conf. on Computer and Communications Security, pp. 1999.
[14] NIST, Digital Signature Standard (DSS), FIPS 186-3, June 2009.
[15] T. ElGamal, “A public key cryptosystem and a signature scheme based on discr-
ete logarithms,” Advances in Cryptology –Crypto’84, LNCS, Vol. 196, pp.10–18, Springer, 1984.
[16] A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identific-
ation and signature problems,” Advances in Cryptology – Crypto’86, LNCS, Vol. 263, pp.186–194, Springer,1986.
[17] M. Fischlin, “The Cramer-Shoup strong-RSA signature scheme revisited,” Publi-
c Key Cryptography,PKC’03, LNCS, Vol. 2567 Springer, pp. 116-129, 2002.
[18] L. C. Guillou and J. J. Quisquater, “A paradoxical identity-based signature sche-
me resulting from zero-knowledge,” Advances in Cryptology – Crypto’88, LNCS, Vol. 403, pp.216-231,Springer 1988.
[19] E.-J. Goh and S. Jarecki, “A signature scheme as secure as the Diffie-Hellman p-
roblem,” Advances in Cryptology - Eurocrypt’03, LNCS, Vol. 2656, pp.401–415, Springer, 2003.
[20] S. Goldwasser, S. Micali, and R. Rivest, “A digital signature scheme secure aga-
inst adaptive chosen-message attacks,” SIAM J. Computing, Vol. 17, No. 2, pp.281–308, 1988.
[21] R. Gennaro, S. Halevi, and T. Rabin, “Secure hash-and-sign signatures without t-
he random oracle,” Advances in Cryptology –Eurocrypt’99, LNCS, Vol. 1592, p
p.123–139, Springer, 1999.
[22] F. Guo, Y. Mu, and W. Susilo, “How to prove security of a signature with a ti-
ghter security reduction,” ProvSec’09, LNCS, Vol. 5848,pp. 90–103, Springer, 2009.
[23] S. Hohenberger and B. Waters, “Short and stateless signatures from the RSA as-
sumption,” Advances in Cryptology –Crypto’09, LNCS, Vol. 5677, pp.654–670, Springer, 2009.
[24] S. Hohenberger and B. Waters, “Realizing hash-and-sign signatures under stand-
ard assumptions,”Advances in Cryptology- Eurocrypt’09. LNCS, Vol. 5479. pp. 333-350, Springer, 2009.
[25] D. Hofheinz, E. Kiltz, “Programmable hash functions and their applications.” A-
dvances in Cryptology-CRYPTO’08, LNCS, Vol. 5157, pp. 21–38. Springer, 20-
08.
[26] M. Joye, : How (Not) to Design Strong-RSA Signatures,” In DESIGNS, CODES AND CRYPTOGRAPHY Volum 59, Numbers1-3, 169-182, DOI: 10.1007/s1062
3-010-9453-1 DCC’11
[27] Kiltz, A. O'Neill, and A. Smith, “Instantiability of RSA-OAEP under chosen pl-
aintext attack,” Advances in Cryptology-CRYPTO’09, Vol 6223, LNCS, pp. 295-313, 2010.
[28] H. Krawczyk and T. Rabin, “Chameleon hashing and signatures,” Proceeding of Network and Distributed System Security 2000, pp.143-154, 2000.
[29] K. Kurosawa and K. Schmidt-Samoa, “New on-line/off-line signature schemes without random oracles,” Proceeding of the 9th International Conference on Th-
eory and Practice in Public-Key Cryptography, PKC’06, Vol 3958, LNCS, pp.3
30-346, Springer, 2006.
[30] J. Katz and N. Wang, “Efficiency improvements for signature schemes with tight security reductions,” ACM Conference on Computer and Communications Secu-
rity, CCS’03, pp.155–164 ACM Press, 2003.
[31] P. Mohassel,“ One-time signatures and chameleon hash functions,” Selected Ar-
eas in Cryptography, SAC’10, Vol6544, LNCS, pp. 302-319, 2010.
[32] D. Naccache, D. Pointcheval, and J. Stern,“ Twin signatures: an alternative to the hash-and-sign paradigm,” Proc. of the 8th CCS, pp. ,ACM Press, 2001.
[33] T. Okamoto,“ Efficient blind and partially blind signatures without random orac-
les,”TCC’06, LNCS, Vol 3876, pp. 80–99, Springer, 2006.
[34] P. Paillier, “Public-key cryptosystems based on composite degree residuosity cla-
sses,” Advances in Cryptology – Eurocrypt’99, LNCS, Vol. 1592, pp.223–238, Springer, 1999.
[35] C. Peikert and B. Waters, “Lossy trapdoor functions and their applications,” Pro-
ceedings of the 40th annual ACM Symposium on Theory of Computing, STOC’
08, pp.187–196,Springer, 2008.
[36] D. Pointcheval and J. Stern, “Security Proofs for Signature schemes”, Advances in Cryptology–Eurocrypt’96, pp.387–398, 1992.
[37] R. Rivest, A. Shami and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM Vol 21, No 2, pp. 120–126, 1978.
[38] C. P. Schnorr, “Efficient signature generation by smart cards,” Journal of Crypt-
ology, Vol. 4, No. 3, pp.161–174, Springer, 1991.
[39] A. Shamir and Y. Tauman,“ Improved online/offline signature schemes,” Adva-
nces in Cryptology-Crypto’01, LNCS, Vol 2139, pp 355–367, Springer, 2001.
[40] S. Schage, “Tight proofs for signature schemes without random oracles,” Adva-
nces in Cryptology-Eurocrypt’11, LNCS, Vol 6632, pp. 189–206, 2011.
[41] B. Waters, “Efficient identity-based encryption without random oracles,” Adva-
nces in Cryptology – Eurocrypt’05, LNCS, Vol. 3494, pp.320–329, Springer, 20
05.