簡易檢索 / 詳目顯示

研究生: 林祚儀
Tzuoh-Yi Lin
論文名稱: 動態門檻式機密共享機制
Dynamic Threshold Secret Sharing Schemes
指導教授: 吳宗成
Tzong-Chen Wu
口試委員: 楊維寧
none
楊中皇
none
雷欽隆
none
賴溪松
none
學位類別: 博士
Doctor
系所名稱: 管理學院 - 資訊管理系
Department of Information Management
論文出版年: 2009
畢業學年度: 97
語文別: 英文
論文頁數: 80
中文關鍵詞: 資訊安全秘密分享密鑰管理金鑰託管群體導向電子公文電子投票密碼系統金鑰交換協定多方安全計算安全廣播數位簽章密碼學
外文關鍵詞: cryptography, threshold cryptography, secret sharing, group-oriented, cheater identification, key escrow, electronic voting, key agreement, secure multi party computation
相關次數: 點閱:330下載:1
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 機密共享(secret sharing)是一種允許分派者(dealer)將秘密(secret)分割成若干個次秘密(share)給予多個互相不信任的參與者共享來進行機密共享的安全機制。只有在這些參與者提出足夠的次秘密後才可重建共享的秘密。機密共享的主要應用包括:(一)、密鑰管理(key management),例如:金鑰託管(key escrow)、金鑰備份(key backup);(二)、資料或文件的安全保存(secure storage);(三)、群體控管(collective control),例如:群體導向系統(group-oriented)、電子公文(electronic documents)等;(四)、密碼元件(cryptographic primitives)的應用,例如:電子投票(electronic voting)、安全廣播(secure broadcasting)、金鑰交換協定(key agreement protocol)、多方安全計算(secure multi party computation, SMPC)等等。
    本論文針對機密共享應用所可能面臨的動態門檻(dynamic threshold)、機密可驗證性(verifiable)以及解密公平性(fairness)相關議題,提出安全且有效率的多種機密共享機制:動態機密共享機制(DTSS)、可驗證動態機密共享機制(VDTSS)、以及公平的動態機密共享機制(FVDTSS)。
    在本論文提出的動態機密共享機制(DTSS)中,參與者僅握有一把次密鑰(secret share)即可重覆使用來共享多個秘密,並且可根據不同的共享策略(sharing policy)來調整機密共享的門檻值(threshold),而不需更動參與者的次秘密(share),非常適用於需要常常需要變動門檻的群體決策以及電子公投等應用。
    可驗證動態機密共享(VDTSS)機制則提出了一個有效率的非交談式驗證機制(non-interactive verification),用以解決次秘密(share)與子次秘密(sub-share)的驗證問題,將可有效的防止資料傳輸時的遭受篡改、分派者欺騙(cheating by the dealer)以及參與者欺騙(cheating by the participants)等安全問題。
    公平的動態機密共享(FVDTSS)機制則提出了一個公平且有效率的秘密重建協定,有效地解決了最後參與者佔有優勢的秘密分享問題,亦即,在秘密重建過程中,即使存在V個欺騙者,其中V<門檻值/2,每個參與重建的參與者仍有一樣的機會取得分享的秘密。
    此外,本論文亦分別針對VDTSS與FVDTSS機制提出在動態門檻密碼系統(cryptosystem)與動態門檻數位簽章系統(digital signature)的應用實例。


    A (t, n) threshold secret sharing scheme enables the secret dealer to decompose the secret into n shares which are separately distributed to participants of the same size. Any t or more participants can reconstruct the shared secret, where the threshold value t is predefined according to the sharing policy. However, if there is a cheater releasing a false share in the secret reconstruction, he can obtain the secret alone. Many applications of secret sharing were presented, such as group decision, electronic documents, electronic voting, secure broadcasting, key management, and key escrow, key agreement, and secure multi party computation (SMPC), …, etc.
    In this thesis, we have presented three dynamic threshold secret sharing schemes: basic dynamic threshold secret sharing scheme (DTSS), verifiable dynamic threshold secret sharing (VDTSS), and fairness verifiable dynamic threshold secret sharing (FVDTSS).
    In the proposed DTSS scheme, each participant only holds a reusable share for multiple secrets. That is, the share held by each participant remains unchanged even if a new shared secret is derived. Moreover, each shared secret can be assigned to a different threshold value by the dealer in accordance with the adopted sharing policy. In VDTSS scheme, the secret share distributed by the dealer can be verified by a non-interactive algorithm, and the sub-shares generated by the participants during secret reconstruction are verifiable. Any participant can identify the cheater without running additional interactive verification protocols. In FVDTSS scheme, all participants have an equal probability to recover the shared secret, even if there might be some cheaters among the participants. Furthermore, the proposed scheme has the advantage that the public information published in the secret distribution is independent of the threshold value and the number of participants. That is, the public information remains constant.

    Chapter 1 Introduction 1 Chapter 2 Review of Secret Sharing Schemes 6 2.1 Shamir’s (t, n) Threshold Scheme 6 2.2 Cheaters Detection and Identification 8 2.3 Fairness (t, n) Secret Sharing Scheme 10 2.4 Threshold Multiple Secret Sharing Scheme 13 2.5 Dynamic Threshold Secret Sharing Scheme 16 Chapter 3 Dynamic Threshold Secret Sharing Scheme 21 3.1 System Model 21 3.2 The Proposed Scheme 22 3.3 Security analyses 29 3.4 Performance Evaluation 30 Chapter 4 Verifiable Dynamic Threshold Secret Sharing Scheme 32 4.1 System Model 33 4.2 Signature of Knowledge 34 4.3 The Proposed Scheme 36 4.4 Security analyses 40 4.5 Performance Evaluation 43 Chapter 5 Fairness Verifiable Dynamic Threshold Secret Sharing Scheme 45 5.1 System Model 45 5.2 The Proposed Scheme 48 5.3 Security analyses 53 5.4 Achievement of Properties 56 5.5 Performance Evaluation 57 Chapter 6 Extentions to Cryptoschemes 58 6.1 Dynamic Threshold RSA Signature 58 6.2 Fairness Dynamic Threshold Pailler’s Cryptosystem 63 Chapter 7 Conclusions 70 7.1 Contributions 70 7.2 Further Work 71 Bibliography 72 Biography 78

    [AM94] L. M. Adleman and K. S. Mccurley, “Open problems in number theoretic complexity,” Proceedings of the 1994 Algorithmic Number Theory Symposium, pp.291-322, 1994.
    [Be86] J. C. Benaloh, “Secret sharing homomorphisms: keeping shares of a secret secret,” Advances in Cryptology - CRYPTO’86, Springer-Verlag, Berlin, pp.251-260, 1986.
    [Bl79] G. R. Blakley, “Safeguarding cryptographic keys,” Proceedings of AFIPS 1979 National Computer Conference, vol.48, pp.313-317, 1979.
    [Br89] E. F. Brickell. “Some ideal secret sharing schemes,” Journal of Combinatorial Mathematics and Combinatorial Computing, vol.9, pp.105-113, 1989.
    [BS88] E. F. Brickell and D. R. Stinson, “The detection of cheaters in threshold schemes,” Advances in Cryptology - CRYPTO’88, Springer-Verlag, Berlin, pp.564-577, 1988.
    [Ca95] M. Carpentieri, “A perfect threshold secret sharing scheme to identify cheaters,” Designs, Codes and Cryptography, vol.5, no.3, pp.183-187, 1995.
    [CC08] W. F. Chang and C. C. Chang, “Robust t-out-of-n proxy signature based on RSA cryptosystem,” International Journal of Innovative Computing, Information and Control (IJICIC), vol.4, no.2, pp.425-431, 2008.
    [CGMA85] B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch, “Verifiable secret sharing and achieving simultaneity in the presence of faults,” Proceedings of 26th IEEE Symposium on Foundations of Computer Science, pp.251-260, 1985.
    [CH97] C. C. Chang and R. J.Hwang, “Efficient cheater identification method for threshold schemes,” IEE Proceedings Computers and Digital Techniques, vol.144, no.1, 1997, pp. 23-27.
    [CLBG07] W. Chen, X. Long, Y. Bai, and X. Gao, “A new dynamic threshold secret sharing scheme from biliner maps,” Proceedings of International Conference on Parallel Processing Workshops (ICPPW 2007), pp.19-22, 2007.
    [CM98a] J. Camenishch and M. Michels, “A group signature scheme with improved efficiency,” Advances in ASIACRYPT’98, Springer-Verlag, pp.160-174, 1998.
    [CM98b] J. Camenishch and M. Michels, “A group signature scheme based on an RSA-variant,” Technical Report RS-98-27, BRICS, University of Aarhus, 1998.
    [DJ01] I. Damgard and M. Jurik, “A Generalisation, a simplification and some applications of paillier's probabilistic public-key system,” Public Key Cryptography – PKC 2001, pp.119-136, 2001.
    [Fe87] P. Feldman, “A practical scheme for non-interaceive verifiable secret sharing,” Proceedings of 28th FOCS, IEEE, pp.427-437, 1987.
    [FO98] E. Fujisaki and T. Okamoto, “A practical and provably secure scheme for publicly verifiable secret sharing and its applications,” Advances in Cryptology - EUROCRYPT’98, Springer-Verlag, pp.32-46, 1998.
    [GIKR01] R. Gennaro, Y. Ishai, E. Kushilevitz, T. Rabin, “The round complexity of verifiable secret sharing and secure multicast,” Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp.580-589, 2001.
    [GKP94] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Second Edition, Addison-Wesley, 1994.
    [GM95] R. Gennaro and S. Micali, “Verifiable secret sharing as secure computation,” Advances in Cryptology - EUROCRYPT’95, Springer-Verlag, Berlin, pp.168-182, 1995.
    [Ha95] L. Harn, “Efficient sharing (broadcasting) of multiple secrets,” IEE Proceedings Computers and Digital Techniques, vol.142, no.3, pp.237-240, 1995.
    [HCY96] S. J. Hwang, C. C. Chang, and W. P. Yang, “An efficient dynamic threshold scheme,” IEICE Trans. on Information and Systems, vol.E79-D, no.7, pp.936-942, 1996.
    [HD94] J. He and E. Dawson, “Multistage secret sharing based on one-way function,” Electronics Letters, vol.30, no.19, pp.1591-1592, 1994.
    [HLHL90] T. Hwang, J. Y. Lee, L. Harn, and C. S. Laih, “Dynamic threshold scheme based on the definition of cross-product in an N-dimensional linear space,” Advances in Cryptology – CRYPTO’89, Springer-Verlag, New York, pp.286-298, 1990.
    [HWW01] C. L. Hsu, T. S. Wu, and T. C. Wu, “New nonrepudiable threshold proxy signature scheme with known signers,” The Journal of Systems and Software, vol.58, pp.119-124, 2001.
    [HWW04] C. L. Hsu, T. S. Wu, and T. C. Wu, “Group-oriented signature scheme with distinguished signing authorities,” Future Generation Computer Systems, vol.20, pp.865-873, 2004.
    [JMK93] W. A. Jackson, K. M. Martin, and M. O’Keefe, “Multisecret threshold schemes,” Advances in Cryptology - CRYPTO’93, Springer-Verlag, Berlin, pp.126-135, 1993.
    [KGH83] E. D. Karnin, J. W. Greene, and M. E. Hellman, “On secret sharing systems,” IEEE Trans. on Information Theory, vol.IT-29, no.1, pp.35-41, 1983.
    [LC98] W. B. Lee and C. C. Chang, “A dynamic secret sharing scheme based on the factoring and Diffie-Hellman problems,” IEICE Transactions on Fundamentals, vol.E81-A, no.8, pp.1733-1738, 1998.
    [LH95] H. Y. Lin and L. Harn, “Fair reconstruction of a secret,” Information Processing Letters, vol.55, pp.45-47, 1995.
    [LHLH90] C. S. Laih, L. Harn, J. Y. Lee, and T. Hwang, “Dynamic threshold scheme based on the definition of cross-product in an N-dimensional linear space,” Advances in Cryptology – CRYPTO’ 89, Springer-Verlag, New York, pp.286-298, 1990.
    [LL97] C. S. Laih and Y. C. Lee, “V-fairness (t, n) secret sharing scheme,” IEE Proceedings Computers and Digital Techniques, vol.144, no.4, pp.245-247, 1997.
    [LW98] T.Y. Lin and T. C. Wu, “Undeniable (t, n)-threshold signature scheme with cheater identification,” Journal of the Chinese Institute of Engineers, vol.21, no.6, pp.775-780, 1998.
    [LW99] T.Y. Lin and T. C. Wu, “(t, n)-threshold verifiable multisecret sharing scheme based on the factorisation and the discrete logarithm modulo a composite problems,” IEE Proceedings Computers and Digital Techniques, vol.146, no.5, pp.264-268, 1999.
    [MS81] R. J. Mceliece and D. V. Sarwate, “On sharing secrets and Reed-Soloman codes,” Communications of the ACM, vol.24, pp.583-584, 1981.
    [NL03] C. Ning, K. Y. Lam, “On identification secret sharing schemes,” Information and Computation, vol. 184, pp.298-310, 2003
    [Pa99] P. Paillier, ‘Public-key cryptosystems based on composite degree residuosity classes,” Advances in Cryptology - EUROCRYPT’99, Springer-Verlag, Berlin, pp223-238, 1999.
    [Pe92] T. P. Pedersen, “Non-interactive and information-theoretic verifiable secret sharing,” Advances in Cryptology - CRYPTO’91, Springer-Verlag, Berlin, pp.129-140, 1992.
    [PZ02] J. Pieprzyk and X. M. Zhang, “Cheating prevention in linear secret sharing,” Australasian Conference on Information Security and Privacy - ACISP 2002, pp.121-135, 2002.
    [RB89] T. Rabin and M. Ben-Or, “Verifiable secret sharing and multi-party protocols with honest majority,” Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp.73-85, 1989.
    [RSA78] R. L. Rivest, A. Shamir, 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.
    [Sc90] M. R. Schroeder, Number Theory in Science and Communication, Second Edition, Springer-Verlag, Berlin, 1990.
    [Sc99] B. Schoenmakers, “A simple publicly verifiable secret sharing scheme and its application to electronic voting,” Advances in Cryptology - Crypto’99, Springer-Verlag, Berlin, pp.148-164, 1999.
    [Sh79] A. Shamir, “How to share a secret,” Communications of the ACM, vol.22, pp.612-613, 1979.
    [Si88] G. Simmons, “An introduction to shared secret schemes and their applications,” Sandia report SAND88-2298, 1988.
    [SS95] H. M. Sun and S. P. Shieh, “Construction of dynamic threshold schemes,” Electronics Letters, vol.30, no.24, pp.2023-2024, 1995.
    [St96] M. Stadler, “Publicly verifiable secret sharing,” Advances in Cryptology - EUROCRYPT’96, Springer-Verlag, Berlin, pp.190-199, 1996.
    [TW88] M. Tompa and H. Woll, “How to share a secret with cheaters,” Journal of Cryptology, vol.1, no.1, pp.133-138, 1988.
    [WH95] T. C. Wu and W. H. He, “A geometric approach for sharing secrets,” Computers & Security, vol.14, no.2, pp.135-145, 1995.
    [WLLH00] T. C. Wu, C. Y. Lin, T. Y. Lin, J. J. Hwang, “A generalized secret sharing scheme realizing ordered access structure,” 2000 International Computer Symposium (ICS’00) Proceedings of Workshop on Cryptology and Information Security, pp.81-83, 2000.
    [WW95] T. C. Wu and T. S. Wu, “Cheating detection and cheater identification in secret sharing schemes,” IEE Proceedings Computers and Digital Techniques, vol.142, no.5, pp.367-369, 1995.
    [ZHS94] Y. Zheng, T. Hardjono, and J. Seberry, “Reusing shares in secret sharing schemes,” The Computer Journal, vol.37, no.3, pp.199-205, 1994.

    無法下載圖示
    全文公開日期 本全文未授權公開 (校外網路)

    QR CODE