兩個適用於機率式單向暗門函式的明文填塞機制及XTR之效率提升

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：76

、訪客IP：3.135.184.255

姓名

江依蒨(I-Chien Chiang) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

兩個適用於機率式單向暗門函式的明文填塞機制及XTR之效率提升
(Efficiency Improvement to XTR and Two Padding Schemes for Probabilistic Trapdoor One-Way Function)

相關論文

★ 多種數位代理簽章之設計	★ 小額電子支付系統之研究
★ 實體密碼攻擊法之研究	★ 商業性金鑰恢復與金鑰託管機制之研究
★ AES資料加密標準之實體密碼分析研究	★ 電子競標系統之研究
★ 針對堆疊滿溢攻擊之動態程式區段保護機制	★ 通用型數域篩選因數分解法之參數探討
★ 於8051單晶片上實作可防禦DPA攻擊之AES加密器	★ 以非確定式軟體與遮罩分割對策防禦能量攻擊之研究
★ 遮罩保護機制防禦差分能量攻擊之研究	★ AES資料加密標準之能量密碼分析研究
★ 小額電子付費系統之設計與密碼分析	★ 公平電子現金系統之研究
★ RSA公開金鑰系統之實體密碼分析研究	★ 保護行動代理人所收集資料之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(英)

In this thesis, two main research directions, efficiency improvement and security enhancement, of public key cryptography are discussed. Firstly, three efficiency improving algorithms for XTR-based cryptographic applications are proposed; then two padding schemes, with CCA2 security, for probabilistic trapdoor one-way functions are presented.
XTR public key system uses a particular way to represent subgroup elements and thus it carries lighter load than systems with tradition element representation in both computational and communicational aspects. In practice, when generating private keys with a specific rule, the communicational overhead can be further reduced. Precisely, only part of the corresponding public key needs to be transmitted and the un-transmitted part can be unambiguously recovered. Along with the same specific rule, a new algorithm which can efficiently deciding suitable private key is proposed as well as an algorithm for fast public key recovery. In computational aspect, a new exponentiation algorithm with some extra outputs is proposed. With those extra outputs, the exponentiated result can be directly exploited in applications, which is not possible in previous methods. Furthermore, the proposed exponentiation algorithm brings considerable computational saving in some applications.
As the adaptive chosen ciphertext (CCA2) security is now the most widely adopted security notion for public key encryption systems, padding schemes for trapdoor one-way permutations are extensively discussed in the decade. However, optimal asymmetric encryption padding (OAEP), the ancestor of this research line, is proved to be not sufficient for CCA2 security. Hence many alternatives are proposed and a particularly important one of them is OAEP 3-round as no redundancy is introduced in the ciphertext. OAEP 3-round is also proved to be secure for using with any probabilistic trapdoor one-way function, but in the sense of relaxed CCA which is a notion weaker than CCA2 security. In this thesis, two new padding schemes for probabilistic trapdoor one-way functions, both keep the advantages of OAEP 3-round, provably to be CCA2-secure in the random oracle model are proposed. In particular, the first scheme retains the ability of pre-computation while the second maintains the randomness space of the underlying probabilistic trapdoor one-way function.

論文目次

1 Introduction 1
1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Overview of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Review of XTR Public Key System 6
2.1 Introduction to XTR . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Parameters and bases . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Computing in GF(p2) or with traces . . . . . . . . . . . . . . 9
2.2 Key Size Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Related Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.1 Security issues of XTR . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2 Speeding up the exponentiation and parameter generation of
XTR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.3 Issues of XTR applications . . . . . . . . . . . . . . . . . . . . 18
3 Review of Padding Schemes and Provable Security 21
3.1 Provable Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.1 Security notion . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.2 Random oracle model . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Padding Schemes for Public Key Encryption System . . . . . . . . . . 26
3.2.1 Optimal asymmetric encryption padding (OAEP) . . . . . . . 27
3.2.2 OAEP+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.3 OAEP 3-round . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.4 Conversion schemes for trapdoor one-way functions . . . . . . 31
4 Improvements to Key Reduction and Multi-Exponentiation for XTR 34
4.1 Improvements to Key Reduction . . . . . . . . . . . . . . . . . . . . . 35
4.1.1 Private key decision . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.2 Public key recovery . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2 Multi-Exponentiation for XTR . . . . . . . . . . . . . . . . . . . . . . 39
4.2.1 An inadequacy of previous XTR exponentiation algorithms . . 39
4.2.2 The proposed multi-exponentiation algorithm . . . . . . . . . 40
4.3 XTR Okamoto-Blind Schnorr Signature . . . . . . . . . . . . . . . . . 43
4.3.1 Review of Okamoto-blind Schnorr signature . . . . . . . . . . 43
4.3.2 XTR Okamoto-blind Schnorr signature . . . . . . . . . . . . . 44
4.3.3 Discussion of efficiency . . . . . . . . . . . . . . . . . . . . . . 46
4.4 XTR Blind Schnorr Signature . . . . . . . . . . . . . . . . . . . . . . 49
4.4.1 Review of XTR blind Schnorr signature . . . . . . . . . . . . . 49
4.4.2 Improvement of XTR blind Schnorr signature . . . . . . . . . 50
5 Two Padding Schemes under the Probabilistic Trapdoor One-Way
Function 53
5.1 Scheme-α and Scheme-F . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.1.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.1.2 Description of scheme-α. . . . . . . . . . . . . . . . . . . . . 55
5.1.3 Description of scheme-F . . . . . . . . . . . . . . . . . . . . . 57
5.1.4 Examples about public key encryption with scheme-α. . . . . 58
5.2 Security Proof of Scheme-αin the CCA2 . . . . . . . . . . . . . . . . 60
5.3 Security Proof of Scheme-F in the CCA2 . . . . . . . . . . . . . . . . 69
6 Conclusions 78
6.1 Brief Review of Main Contributions . . . . . . . . . . . . . . . . . . . 78
6.2 Further Research Topics and Directions . . . . . . . . . . . . . . . . . 79
Bibliography. . . . . . . . . . . . . . . . . 81

參考文獻

[1] Whitfield Diffie and Martin E. Hellman, “New directions in cryptography,” In IEEE Transactions on Information Theory, Val. 22(6), pp. 644–654, November 1976.
[2] Ronald, L. Rivest, Adi Shamir, and Len Adleman, “A Method for Obtaining Digital Signatures and Public Key Cryptosystems,” In Communications of the ACM, pp. 120–126, February 1978.
[3] Michael O. Rabin, “Digitalized signatures and public-key functions as intractable as factorization,” Technical Report MIT/LCS/TR-212, MIT Laboratory for Computer Science, 1979.
[4] Taher El Gamal, “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” In IEEE Transactions on Information Theory, Val. 31(4), pp. 469–472, 1985.
[5] Amos Fiat and Adi Shamir, “How To Prove Yourself: Practical Solutions to Identification and Signature Problems,” In Advances in Cryptology – CRYPTO 1986, Lecture Notes in Computer Science, Vol. 263, pp. 186–194, Springer-Verlag, 1987.
[6] Tatsuaki Okamoto, “Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes,” In Advances in Cryptology – CRYPTO 1992, Lecture Notes in Computer Science, Vol. 740, pp. 31–53, Springer-Verlag, 1992.
[7] Mihir Bellare and Phillip Rogaway, “Random Oracles are Practical: A Paradigm for Designing Efficient Protocols,” In First ACM Conference on Computer and Communications Security, pp. 62–73, 1993.
[8] Mihir Bellare and Phillip Rogaway, “Optimal Asymmetric Encryption - How to Encrypt with RSA,” In Advances in Cryptology - EUROCRYPT 1994, Lecture Notes in Computer Science, Vol. 950, pp. 92–111, Springer-Verlag, 1994.
[9] NIST, “Digital signature standard,” Faderal Information Processing Standards Publication 186, U.S. Department of Commerce, 1994.
[10] Sung Ming Yen, Chi Sung Laih, and Arjen K. Lenstra, “Multi-exponentiation,” In IEE Proceedings: Computers and Digital Techniques, Vol.141, No.6, 1994.
[11] Dan Boneh and Ramarathnam Venkatesan, “Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes,” In Advances in Cryptology - CRYPTO 1996, Lecture Notes in Computer Science, Vol. 1109, pp. 129–142, Springer-Verlag, 1996.
[12] David Pointcheval and Jacques Stern, “Provably Secure Blind Signature Schemes,” In Advances in Cryptology - ASIACRYPT 1996, Lecture Notes in Computer Science, Vol. 1163, pp. 252–265, Springer-Verlag, 1996.
[13] Chae Hoon Lim and Pil Joong Lee, “A Key Recovery Attack on Discrete Logbased Schemes Using a Prime Order Subgroup,” In Advances in Cryptology -CRYPTO 1997, Lecture Notes in Computer Science, Vol. 1294, pp. 249–263, Springer-Verlag, 1997.
[14] Michel Abdalla, Mihir Bellare and Phillip Rogaway, “DHAES: An Encryption Scheme Based on the Diffie-Hellman Problem,” Submission to IEEE P1363a, Available at http://grouper.ieee.org/groups/1363/P1363a/Encryption.html
[15] Mihir Bellare, Anand Desai, David Pointcheval and Phillip Rogaway, “Relations Among Notions of Security for Public-Key Encryption Schemes,” In Advances in Cryptology - CRYPTO 1998, Lecture Notes in Computer Science, Vol. 1462, pp. 26–46, Springer-Verlag, 1998.
[16] Daniel Bleichenbacher, “Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1,” In Advances in Cryptology -CRYPTO 1998, Lecture Notes in Computer Science, Vol. 1462, pp. 1–12, Springer-Verlag, 1998.
[17] Henri Cohen, Atsuko Miyaji and Takatoshi Ono, “Efficient Elliptic Curve Exponentiation Using Mixed Coordinates,” In Advances in Cryptology – ASIACRYPT 1998, Lecture Notes in Computer Science, Vol. 1514, pp. 51–65, Springer-Verlag, 1998.
[18] Jeffrey Hoffistein, Jill Pipher and Joseph H. Silverman, “NTRU: A Ring-Based Public Key Cryptosystem,” In Algorithmic Number Theory, Third International Symposium, ANTS-III, Lecture Notes in Computer Science, Vol. 1423, pp. 267–288, Springer-Verlag, 1998.
[19] Andries E. Brouwer, Ruud Pellikaan and Eric R. Verheul, “Doing More with Fewer Bits,” In Advances in Cryptology - ASIACRYPT 1999, Lecture Notes in Computer Science, Vol. 1716, pp. 321–332, Springer-Verlag, 1999.
[20] Eiichiro Fujisaki and Tatsuaki Okamoto, “How to Enhance the Security of Public-Key Encryption at Minimum Cost,” In Public Key Cryptography – PKC 1999, Lecture Notes in Computer Science, Vol. 1560, pp. 53–68, Springer-Verlag, 1999.
[21] Eiichiro Fujisaki and Tatsuaki Okamoto, “Secure Integration of Asymmetric and Symmetric Encryption Schemes,” In Advances in Cryptology – CRYPTO 1999, Lecture Notes in Computer Science, Vol. 1666, pp. 537–554, Springer-Verlag, 1999.
[22] Joonsang Baek, Byoungcheon Lee and Kwangjo Kim, “Secure Length-saving ElGamal Encryption under the Computational Diffie-Hellman Assumption,” In Information Security and Privacy - ACISP 2000, Lecture Notes in Computer Science, Vol. 1841, pp. 49–58, Springer-Verlag, 2000.
[23] ´Eliane Jaulmes and Antoine Joux, “A Chosen-Ciphertext Attack against NTRU,” In Advances in Cryptology - CRYPTO 2000, Lecture Notes in Computer Science, Vol. 1880, pp. 20–35, Springer-Verlag, 2000.
[24] Arjen K. Lenstra, “The XTR Public Key System,” talk at MSRI, October 2000, slides Available at http://www.msri.org/publications/ln/msri/2002/intersect/kapranov/1/index.html.
[25] Arjen K. Lenstra and Eric R. Verheul, “Key Improvements to XTR,” In Advances in Cryptology - ASIACRYPT 2000, Lecture Notes in Computer Science, Vol. 1976, pp. 220–233, Springer-Verlag, 2000.
[26] Arjen K. Lenstra and Eric R. Verheul, “The XTR Public Key System,” In Advances in Cryptology - CRYPTO 2000, Lecture Notes in Computer Science, Vol. 1880, pp. 1–19, Springer-Verlag, 2000.
[27] David Pointcheval, “Chosen-Ciphertext Security for any One-Way Cryptosystem,” In Public Key Cryptography - PKC 2000, Lecture Notes in Computer Science, Vol. 1751, pp. 129–146, Springer-Verlag, 2000.
[28] Dan Boneh, “Simplified OAEP for the RSA and Rabin Functions,” In Advances in Cryptology - CRYPTO 2001, Lecture Notes in Computer Science, Vol. 2139, pp. 275–291, Springer-Verlag, 2001.
[29] Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval and Jacques Stern, “RSA-OAEP Is Secure under the RSA Assumption,” In Advances in Cryptology - CRYPTO 2001, Lecture Notes in Computer Science, Vol. 2139, pp. 260–274, Springer-Verlag, 2001.
[30] Jae Moon Kim, Ikkwon Yie, Seung Ik Oh, Hyung Don Kim and Jado Ryu, “Fast Generation of Cubic Irreducible Polynomials for XTR,” In Progress in Cryptology - INDOCRYPT 2001, Lecture Notes in Computer Science, Vol. 2247, pp. 73–78, Springer-Verlag, 2001.
[31] Arjen K. Lenstra and Eric R. Verheul, “An Overview of the XTR Public Key System,” In Public-Key Cryptography and Computational Number Theory, pp. 151–181, Walter De Gruyter Inc, 2001. Available at http://www.win.tue.nl/_klenstra/
[32] Arjen K. Lenstra and Eric R. Verheul, “Fast Irreducibility and Subgroup Membership Testing in XTR,” In Public Key Cryptography - PKC 2001, Lecture Notes in Computer Science, Vol. 2001, pp. 73–86, Springer-Verlag, 2001.
[33] Philip MacKenzie, “More Efficient Password-Authenticated Key Exchange,” In Cryptographer’s Track at RSA - CT-RSA 2001, Lecture Notes in Computer Science, Vol. 2020, pp. 361–377, Springer-Verlag, 2001.
[34] Tatsuaki Okamoto and David Pointcheval, “REACT: Rapid Enhanced-security Asymmetric Cryptosystem Transform,” In Cryptographer’s Track at RSA Conference - CT-RSA 2001, Lecture Notes in Computer Science, Vol. 2020, pp. 159–175, Springer-Verlag, 2001.
[35] Victor Shoup, “OAEP Reconsidered,” In Advances in Cryptology – CRYPTO 2001, Lecture Notes in Computer Science, Vol. 2139, pp. 239–259, Springer-Verlag, 2001.
[36] Igor E. Shparlinski, “On the Generalised Hidden Number Problem and Bit Security of XTR,” In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - AAECC, Lecture Notes in Computer Science, Vol. 2227, pp. 268–277, Springer-Verlag, 2001.
[37] Martijn Stam and Arjen K. Lenstra, “Speeding Up XTR,” In Advances in Cryptology - ASIACRYPT 2001, Lecture Notes in Computer Science, Vol. 2248, pp. 125–143, Springer-Verlag, 2001.
[38] Jee Hea An, Yevgeni Dodis and Tal Rabin “On the Security of Joint Signature and Encryption,” In Advances in Cryptology - EUROCRYPT 2002, Lecture Notes in Computer Science, Vol. 2332, pp. 83–107, Springer-Verlag, 2002.
[39] Wieb Bosma, James Hutton, and Eric R. Verheul, “Looking beyond XTR,” In Advances in Cryptology - ASIACRYPT 2002, Lecture Notes in Computer Science, Vol. 2501, pp. 46–63, Springer-Verlag, 2002.
[40] Jakob Jonsson, “An OAEP Variant with a Tight Security Proof,” Available at http://eprint.iacr.org/2002/034/
[41] Arjen K. Lenstra, “Computational Methods in Public Key Cryptology,” Available at http://www.win.tue.nl/_klenstra/notes.pdf.
[42] Wen-Ching W. Li, Mats N¨aslund and Igor E. Shparlinski, “Hidden Number Problem with the Trace and Bit Security of XTR and LUC,” In Advances in Cryptology - CRYPTO 2002, Lecture Notes in Computer Science, Vol. 2442, pp. 433–448, Springer-Verlag, 2002.
[43] Phong Q. Nguyen and David Pointcheval, “Analysis and Improvements of NTRU Encryption Paddings,” In Advances in Cryptology - CRYPTO 2002, Lecture Notes in Computer Science, Vol. 2442, pp. 210–225, Springer-Verlag, 2002.
[44] Jean-S´ebastien, Helena Handschuh, Marc Joye, Pascal Paillier, David Pointcheval and Christophe Tymen, “GEM: A Generic Chosen-Ciphertext Secure Encryption Method,” In Cryptographer’s Track at RSA Conference - CT-RSA 2002, Lecture Notes in Computer Science, Vol. 2271, pp. 263–276, Springer-Verlag, 2002.
[45] Ran Canetti, Hugo Krawczyk and Jesper Buus Nielsen, “Relaxing Chosen-Ciphertext Security,” In Advances in Cryptology - CRYPTO 2003, Lecture Notes in Computer Science, Vol. 2729, pp. 565–582, Springer-Verlag, 2003.
[46] Xiaofeng Chen, Fei Feng and Yumin Wang, “New Key Improvements and Its Application to XTR System,” Proceedings of Advanced Information Networking and Applications - AINA 2003, pp. 561–564, IEEE Computer Society, 2003.
[47] Duong Hieu Phan and David Pointcheval, “Chosen-Ciphertext Security without Redundancy,” In Advances in Cryptology - ASIACRYPT 2003, Lecture Notes in Computer Science, Vol. 2894, pp. 1–18, Springer-Verlag, 2003.
[48] Kaoru Kurosawa and Toshihiko Matsuo, “How to Remove MAC from DHIES,” In Information Security and Privacy - ACISP 2004, Lecture Notes in Computer Science, Vol. 3108, pp. 236–247, Springer-Verlag, 2004.
[49] Eric Peeters, Michael Neve and Mathieu Ciet, “XTR Implementation on econfigurable Hardware,” In Cryptographic Hardware and Embedded Systems - CHES 2004, Lecture Notes in Computer Science, Vol. 3156, pp. 386–399, Springer-Verlag, 2004.
[50] Duong Hieu Phan and David Pointcheval, “OAEP 3-Round A Generic and Secure Asymmetric Encryption Padding,” In Advances in Cryptology – ASIACRYPT 2004, Lecture Notes in Computer Science, Vol. 3329, pp. 63–77, Springer-Verlag, 2004.
[51] Duong Hieu Phan and David Pointcheval, “On the Security Notions for Public-Key Encryption Schemes,” In Security in Communication Networks 2004, Lecture Notes in Computer Science, Vol. 3352, pp. 33–47, Springer-Verlag, 2004.

指導教授

顏嵩銘(Sung-Ming Yen)

審核日期

2005-7-13

推文