基於中國餘數定理之階層式祕密分享

Abstract

門檻密碼系統或屬性加密等功能分享密碼系統，大多基於Shamir或Asmuth-Bloom加權門檻秘密分享機制。秘密的存取結構在大部分的情形下皆以階層式為主，即成員可切割為若干群組，在同一群組中的人在存取結構上有同等地位。在本文中，我們尋找適當的加權門檻秘密分享系統來實現階層式存取結構。

首先，我們分析基於中國餘數定理之秘密分享系統之安全性，包含Mignotte系統、Asmuth-Bloom系統、與其他兩個Asmuth-Bloom的加強版。根據上述安全分析，並考量安全等級與分享秘密之長度，我們提出一安全秘密分享系統。基於中國餘數定理之秘密分享系統，在建構上都需要滿足特定條件且兩兩互質的整數序列，因此，我們依據質數定理，提出產生此整數序列的演算法。實驗也顯示提出的演算法改善了建構的時間效率，並維持持有秘密的空間效率。此安全秘密分享系統及整數序列生成演算法也可應用於其他地方。

接著，我們提出將階層式存取結構轉成整數規劃問題的方法。藉由整數規劃之最佳解，可進一步利用加權門檻秘密分享系統來實現階層式存取結構。從實驗得知，上述提出的加權門檻秘密分享系統比Shamir的系統在重建秘密時更有效率。此方法能讓功能分享密碼系統也支援階層式存取結構。

Function sharing cryptosystems, such as threshold cryptosystems and attribute-based encryption (ABE), are largely based on Shamir and Asmuth-Bloom weighted threshold secret sharing (WTSS) schemes. This thesis focuses on constructing WTSS schemes to realize hierarchical access structures (HAS), in which the participants can be partitioned into multiple levels so that the me mbers in the same level are equally important.

We first analyze the security of recent secret sharing schemes based on the Chinese Remainder Theorem, including Mignotte scheme, Asmuth-Bloom scheme and two modifications of the latter scheme. Taking the security level and the size of the set of secrets into consideration, we propose a provably asymptotically perfect CRT-based weighted threshold secret sharing scheme. Since all the CRT-based secret sharing schemes use special increasing sequences of pairwise coprime integers, we propose an algorithm to generate the sequences of primes along with the correctness proof based on the prime number theory. We also provide experimental result to show that our algorithm is effective and it is space efficient to adopt generated sequences of integers in CRT-based secret sharing schemes. Our scheme with the parameter generation algorithm can be used in many other applications.

We next propose a novel approach which formulates a hierarchical access structure into the constraints of the integer programming problem for security and efficiency consideration. The solution to the problem leads to a weighted threshold access structure, which is a medium for the original HAS to be realized by weighted threshold secret sharing schemes. We provide the numerical examples to demonstrate the effectiveness of our approach. The computation time of the secret recovery shows that our WTSS scheme is more time efficient than Shamir scheme. Our approach can also enable function sharing cryptosystems for hierarchical access structures.