跳到主要內容

臺灣博碩士論文加值系統

(44.210.99.209) 您好!臺灣時間:2024/04/16 02:32
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:張智超
研究生(外文):Chi-Chao Chang
論文名稱:環狀公開金鑰密碼系統
論文名稱(外文):Ring Cryptography - How to Perform Secure Communications Anonymously
指導教授:黃宗立黃宗立引用關係
指導教授(外文):Tzonelih Hwang
學位類別:博士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:英文
論文頁數:72
中文關鍵詞:環狀簽章密碼學
外文關鍵詞:Ring SignatureCryptography
相關次數:
  • 被引用被引用:0
  • 點閱點閱:181
  • 評分評分:
  • 下載下載:20
  • 收藏至我的研究室書目清單書目收藏:1
  在2001年,Rivest, Shamir和Tauman等學者提出了環的概念,並實作出第一個植基於RSA數位簽章的環狀簽章系統。環狀簽章具有許多群組導向簽章的特點,例如簽章可由單一成員產生、簽章的效力及於整個群組、驗證者確知簽署者必然為群組之成員、驗證者無法指出確定的簽署人等。但相較於其他以群組為導向的簽章系統,環狀簽章系統又有其完全不同的特色:也就是環狀群組的設立不需要可信賴的第三者或其他成員的協助,單一成員即可自行發起一個群組。因為這個特色,近年來不斷有學者提出新的環狀簽章,或者在現有的環狀簽章系統上加入新的功能。目前已有各種環狀簽章系統分別植基於分解因式、離散對數和雙曲線等三大難題,對此,本論文提出一個將現存的環狀簽章系統依照環的產生方式而分類的方法,並將所有現存系統一一納入。
  本論文之主要貢獻在於提出一個植基於El Gamal數位簽章的環狀簽章系統,並由此衍生出一個全新的環狀公開金鑰密碼系統的概念。環狀公開金鑰密碼系統利用類似於環狀簽章的方式產生一組公開金鑰,因此系統的使用者可以很方便地產生公開金鑰,用來做密碼交換並建立安全的通訊管道;通訊的對方只能確信金鑰的擁有者必然是環狀群組的成員而無法確定是群組成員中的哪一位。環狀公開金鑰密碼系統對於想要在網際網路中使用各項服務,卻又不希望身分洩漏的使用者提出了一個良好的解決方案:使用者可以在匿名的情況下完成系統登入並且建立安全的溝通管道;這個特性使得環狀公開金鑰系統在隱私權越來越受到重視的未來有很大的應用範圍。
  為了說明我們所提出的環狀公開金鑰系統的重要性,本論文對於環狀公開金鑰系統與應用環狀簽章系統簽署一組獨立產生的公開金鑰提出詳細的比較並列出使用後者所可能衍生的安全威脅。另外,針對環狀公開金鑰系統衍生的技術是否能夠普遍地應用於每一種環狀簽章系統的問題,文中也提出我們認為此種衍生技術並不適用於其他環狀簽章系統的理由。
  由於近年來可證明的安全度分析已經成為評估密碼系統安全性的主要方法,為了保證本論文中所提系統的安全性,我們特別對Pointcheval和Stern等兩位學者所提出的數位簽章系統證明法(Forking lemmas)加以研究並分別對文中所提之環狀簽章與環狀公開金鑰系統提供了安全性的証明。
 Ring signature is one of the latest cryptographic primitives that have attracted great research attention for its unique property: The idea that one user can generate a group signature without help from anyone else. In essence, a ring signature scheme is a group-oriented digital signature protocol with the property of individuality. The notion of ring was first introduced by Rivest et al. [1] as a tool for leaking a secret without revealing one's identity. A ring is an ad hoc collection of n identities and their public keys which involves one signer and n - 1 innocent members. The signer is responsible for generating the signature so that other cannot identify him. The features of ring signatures are closely related to group signatures. One signature represents the whole group and the signer must be one of the group members. However, the two approaches are different in some aspects: First of all, in group signature schemes, there exists a group manager who is in charge of the joining and leaving of members in the group. Therefore, users in a group signature scheme have no control over the composition of the group.
Secondly, the group manager can recover the real identity of the signer from a group signature, which may be useful in the case of dispute. And finally, additional secrets (group key) must be kept by users in a group signature scheme while in ring signature schemes, only certified public keys from the PKI and the signer's private key are needed.

 The original ring signature scheme is partly RSA signature/encryption scheme and partly secret key encryption/decryption. Nowadays, various types of ring signature scheme already cover the three major problems in public key cryptosystems, namely the factoring problem, discrete logarithm problem and elliptic curves.

 The major contributions in this dissertation is to design a new ring signature scheme based on the discrete logarithm problem, namely the El Gamal signature scheme and an extended ring public key generating algorithm which is capable of setting up secure communication channels anonymously. In order to do so, we analyze most, if not all, of the ring signature scheme currently available and categorize them for the sake of understanding how far has the idea of ring been applied to building cryptographic primitives and applications.
1 Introduction 4
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Ring Signature Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Ring Public Key Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Motivations & Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Preliminaries 13
2.1 Digital Signature Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Attacks on Digital Signature Schemes . . . . . . . . . . . . . . . . . . 14
2.2 Security Proofs for Digital Signatures . . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 The Random Oracle Model . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Oracle Replay Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.3 Forking Lemmas for Ring Signature Schemes . . . . . . . . . . . . . . 21
3 Ring Signatures 24
3.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.1 Security Notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Forking Lemmas for Generic Ring Signatures . . . . . . . . . . . . . . . . . . 25
3.3 Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3.1 El Gamal Digital Signature Scheme . . . . . . . . . . . . . . . . . . . 27
3.3.2 Existential Forgeability of El Gamal Signatures . . . . . . . . . . . . 28
3.3.3 Modified El Gamal Signature Scheme . . . . . . . . . . . . . . . . . . 28
3.4 El Gamal-Based Ring Signature Scheme . . . . . . . . . . . . . . . . . . . . 29
3.5 Security Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.5.1 Unforgeability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.5.2 Anonymity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.6 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.7 Extended Schemes and Applications . . . . . . . . . . . . . . . . . . . . . . . 36
3.7.1 Threshold Ring Signature Scheme . . . . . . . . . . . . . . . . . . . . 36
3.7.2 Combinatorial Ring Signature Scheme . . . . . . . . . . . . . . . . . 39
4 Privacy Protection and Ring Public Key Cryptosystem 42
4.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 Applications for Ring Public Key Cryptosystems . . . . . . . . . . . . . . . . 46
4.3 Ring Public Keys vs. Ring Signatures of Public Keys . . . . . . . . . . . . . 47
4.4 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.4.1 Security Notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.5 Ring Public Key Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.6 El Gamal-Based Ring PKC . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.6.1 The Ring Public Key Generation . . . . . . . . . . . . . . . . . . . . 51
Phase 1: Public Key Setup . . . . . . . . . . . . . . . . . . . . . . . . 52
Phase 2: Private Key Recovery . . . . . . . . . . . . . . . . . . . . . 53
4.6.2 Ring Public Key Verification . . . . . . . . . . . . . . . . . . . . . . . 53
4.7 Security Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.7.1 Unforgeability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.7.2 Anonymity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5 Conclusions 63
[Aso94] N. Asokan. Anonymity in a mobile computing environment. In Proceedings
of the Workshop on Mobile Computing Systems and Applications, Santa Cruz,
USA, December 1994. IEEE.
[BCJ+05] Eli Biham, Rafi Chen, Antoine Joux, Patrick Carribault, Christophe Lemuet,
and William Jalby. Collisions of sha-0 and reduced sha-1. In Ronald Cramer,
editor, Advances in Cryptology - EUROCRYPT 2005, volume 3494 of Lecture
Notes in Computer Science, pages 36–57. Springer-Verlag, 2005.
[BFK00] Oliver Berthold, Hannes Federrath, and Stefan Kぴopsell. Web mixes: A system
for anonymous and unobservable internet access. In Hannes Federrath, editor,
Designing Privacy Enhancing Technologies, International Workshop on Design
Issues in Anonymity and Unobservability, volume 2009 of Lecture Notes in Com-
puter Science, pages 115–129, Berkeley, CA, USA, July 2000. Springer-Verlag.
[BGLS03] Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and encrypted
signatures from bilinear maps. In Eli Biham, editor, Advanced in Cryp-
tology – EUROCRYPT 03, volume 2656 of Lecture Notes in Computer Science,
pages 416–432, Warsaw, Poland, May 2003. Springer-Verlag.
[BR93] Mihir Bellare and Philip Rogaway. Random oracles are practical: A paradigm
for designing efficient protocols. In Proceedings of the 1st ACM Conference on
Computer and Communications Security, pages 62–73. ACM Press, November
1993.
[BSS02] Emmanuel Bresson, Jacques Stern, and Michael Szydlo. Threshold ring signatures
and applications to ad-hoc groups. In Moti Yung, editor, Advances in
Cryptology (CRYPTO 2002), volume 2442 of Lecture Notes in Computer Science,
pages 465–480, Santa Barbara, California, USA, August 2002. Springer-Verlag.
[CGH98] Ran Canetti, Oded Goldreich, and Shai Halevi. The random oracle mothodology,
revisited. In Proceedings of the 30th ACM Symposium on Theory of Computing
(STOC 98), pages 209–218. ACM Press, 1998.
[CH02] Jan Camenisch and Els Van Herreweghen. Design and implementation of the
idemix anonymous credential system. In Vijayalakshmi Atluri, editor, Proceed-
ings of the 9th ACM Conference on Computer and Communications Security
(CCS 2002), pages 21–30, Washingtion, DC, USA, November 2002. ACM.
[CH04] Chi-Chao Chang and Tzonelih Hwang. El gamal-based threshold and aggregated
ring signature schemes. Submitted to Computer & Security, October 2004.
[CH05a] Chi-Chao Chang and Tzonelih Hwang. Anonymous proof of memberships with
ring signatures. In IEEE Electro/Information Conference 2005 (EIT 2005), May
2005.
[CH05b] Chi-Chao Chang and Tzonelih Hwang. Provacy protection in the internet. In
Proceedings of the First International Conference on Information Management
and Business (IMB 2005), March 2005.
[Cha88] David Chaum. The dining cryptographers problem: Unconditional sender and
recipient untraceability. Journal of Cryptology, 1(1):65–75, January 1988.
[CHY04] Sherman S. M. Chow, Lucas Chi Kwong Hui, and Siu-Ming Yiu. Identity based
threshold ring signature. In Choonsik Park and Seongtaek Chee, editors, 7th
International Conference on Information Security and Cryptology (ICISC 2004),
volume 2009 of Lecture Notes in Computer Science, pages 218–232, Seoul, Korea,
December 2004. Springer-Verlag.
[DF89] Yvo Desmedt and Yair Frankel. Threshold cryptosystems. In Gilles Brassard,
editor, Advances in Cryptology - CRYPTO ’89, volume 435 of Lecture Notes
in Computer Science, pages 307–315, Santa Barbara, California, USA, August
1989. Springer-Verlag.
[DZ94] Chengthurvasan Duraiappan and Yuliang Zheng. Enhancing security in gsm. In
International Computer Symposium ’94, Taiwan, December 1994.
[FS86] Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification
and signature problems. In Andrew M. Odlyzko, editor, Advances in
Cryptology - CRYPTO ’86, volume 263 of Lecture Notes in Computer Science,
pages 186–194, Santa Barbara, California, USA, 1986. Springer-Verlag.
[Gam85] Taher El Gamal. A public key cryptosystem and a signature scheme based on
discrete logarithms. In G. R. Blakley and David Chaum, editors, Advances in
Cryptology - CRYPTO ’84, volume 196 of Lecture Notes in Computer Science,
pages 10–18, Santa Barbara, California, USA, August 1985. Springer-Verlag.
[GK01] Jaeseung Go and Kwangjo Kim. Wireless authentication protocols preserving
user anonymity. In SCIS 2001, volume 1/2, pages 159–164, Oiso, Japan, January
2001.
[GRS99] David M. Goldschlag, Michael G. Reed, and Paul F. Syverson. Onion routing.
Communications of the ACM, 42(2):39–41, February 1999.
[GYL03] Chong-Zhi Gao, Zheng-An Yao, and Lei Li. A ring signature scheme based on
the nyberg-ruppel signature scheme. In Yongfei Han Jianying Zhou, Moti Yung,
editor, First International Conference on Applied Cryptography and Network
Security (ACNS 2003), volume 2846 of Lecture Notes in Computer Science, pages
169–175, Kunming, China, October 2003. Springer-Verlag.
[HS03] Javier Herranz and Germ´a S´aez. Forking lemmas for ring signature schemes.
In Thomas Johansson and Subhamoy Maitra, editors, Advances in Cryptology -
INDOCRYPT 2003, volume 2904 of Lecture Notes in Computer Science, pages
266–279, New Delhi, India, December 2003. Springer-Verlag.
[KT03] Hidenori Kuwakado and Hatsukazu Tanaka. Threshold ring signature scheme
based on the curve. In Proceedings of the IEEE International Symposium on
Information Theory 2003 (ISIT 2003), pages 139–139. IEEE, June 2003.
[LHC01] Zhi Li, John Higgins, and Mark Clement. Performance of finite field arithmetic
in an elliptic curve cryptosystem. In Proceedings of the Ninth IEEE International
Symposium on Modeling, Analysis, and Simulation of Computer and Telecom-
munications Systems (MASCOTS’01), pages 249–256. IEEE, August 2001.
[LW04] Chin-Yin Lin and Tzone-Chen Wu. An identity-based ring signature scheme
from bilinear pairings. In 18th International Conference on Advanced Informa-
tion Networking and Applications (AINA 2004), pages 182–186, Fukuoka, Japan,
March 2004. IEEE Computer Sciety.
[LWW04] Joseph K. Liu, Victor K. Wei, and Duncan S. Wong. Linkable spontaneous
anonymous group signature for ad hoc groups (extended abstract). In Informa-
tion Security and Privacy: 9th Australasian Conference (ACISP 2004), volume
3108 of Lecture Notes in Computer Science, pages 325–335, Sydney, Australia,
July 2004. Springer-Verlag.
[Mit01] Chris J. Mitchell. The security of the gsm air interface protocol. Technical
Report RHUL-MA-2001-3, Dept. Mathematics, Royal Halloway, University of
London, Surrey, England, August 2001.
[PS96a] David Pointcheval and Jacques Stern. Provably secure blind signature schemes.
In Kwangjo Kim and Tsutomu Matsumoto, editors, Advances in Cryptology -
ASIACRYPT ’96, volume 1163 of Lecture Notes in Computer Science, pages
252–265, Kyongju, Korea, 1996. Springer-Verlag.
[PS96b] David Pointcheval and Jacques Stern. Security proofs for signature schemes. In
Ueli M. Maurer, editor, Advances in Cryptology - EUROCRYPT ’96, volume
1070 of Lecture Notes in Computer Science, pages 387–398, Saragossa, Spain,
1996. Springer-Verlag.
[PS00] David Pointcheval and Jacques Stern. Security arguments for digital signatures
and blind signatures. Journal of Cryptology, 13(3):361–396, Summer 2000.
[RST01] Ronald Rivest, Adi Shamir, and Yael Tauman. How to leak a secret. In Colin
Boyd, editor, Advances in Cryptology, ASIACRYPT 2001, volume 2248 of Lec-
ture Notes in Computer Science, pages 552–565, Gold Coast, Australia, December
2001. Springer-Verlag.
[SGR85] Silvio Micali Shaffi Goldwasser and Charles Rackoff. The knowledge complexity
of interactive proof systems (extended abstract). In Proceedings of the 17th
STOC, pages 291–304. ACM Press, 1985.
[SGR88] Silvio Micali Shaffi Goldwasser and Ronald Rivest. A digital signature scheme
secure against adaptive chosen-message attacks. SIAM Journal on Computing,
17(2):281–308, April 1988.
[SGR89] Silvio Micali Shaffi Goldwasser and Charles Rackoff. The knowledge complexity
of interactive proof systems. SIAM Journal on Computing, 18(2):186–208, April
1989.
[Sha79] Adi Shamir. How to share a secret. Communications of the ACM (CACM),
22(11):612–613, November 1979.
[SMA95] Didier Samfat, Refik Molva, and N. Asokan. Untraceability in mobile networks.
In Proceedings of the ACM International Conference on Mobile Computing and
Networking, Berkeley CA, USA, November 1995. ACM Press.
[TM03] Yuko Tamura and Atsuko Miyaji. Anonymity-enhanced pseudonym system. In
Jianying Zhou, Moti Yung, and Yongfei Han, editors, Proceedings of the First
International Conference on Applied Cryptography and Network Security (ACNS
2003), volume 2846 of Lecture Notes in Computer Science, pages 33–47, Kunming,
China, October 2003. Springer-Verlag.
[TWC+04] Patrick P. Tsang, Victor K. Wei, Tony K. Chan, Man Ho Au, Joseph K.
Liu, and Duncan S. Wong. Separable linkable threshold ring signatures. In
Kapalee Viswanathan Anne Canteaut, editor, Progress in Cryptology - IN-
DOCRYPT 2004, 5th International Conference on Cryptology in India, volume
3348 of Lecture Notes in Computer Science, pages 384–398, Chennai, India, December
2004. Springer-Verlag.
[WFLW03] Duncan S. Wong, Karyn Fung, Joseph K. Liu, and Victor K. Wei. On the
rs-code construction of ring signature schemes and a threshold setting of rst.
In Sihan Qing, Dieter Gollmann, and Jianying Zhou, editors, Information and
Communications Security, 5th International Conference, ICICS 2003, volume
2836 of Lecture Notes in Computer Science, pages 34–46, Huhehaote, China,
October 2003. Springer-Verlag.
[WLF+05] Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, and Xiuyuan Yu. Cryptanalysis
of the hash functions md4 and ripemd. In Ronald Cramer, editor,
Advances in Cryptology - EUROCRYPT 2005, volume 3494 of Lecture Notes in
Computer Science, pages 1–18. Springer-Verlag, 2005.
[WY05] Xiaoyun Wang and Hongbo Yu. How to break md5 and other hash functions. In
Ronald Cramer, editor, Advances in Cryptology - EUROCRYPT 2005, volume
3494 of Lecture Notes in Computer Science, pages 19–35. Springer-Verlag, 2005.
[ZK02] Fangguo Zhang and Kwangjo Kim. Id-based blind signature and ring signature
from pairings. In Yuliang Zheng, editor, Advances in Cryptology - ASIACRYPT
2002, volume 2501 of Lecture Notes in Computer Science, pages 533–547, Queenstown,
New Zealand, December 2002. Springer-Verlag.
[ZSNL03] Fangguo Zhang, Reihaneh Safavi-Naini, and Chin-Yin Lin. New proxy signature,
proxy blind signature and proxy ring signature schemes from bilinear pairing.
Cryptology ePrint Archive, Report 2003/104, May 2003. Available through
“http://eprint.iacr.org/”.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top