可分段共享之暗門數列及其應用

Abstract

有鑑於密碼系統為犯罪組織所濫用，美國政府在1993年公佈了一套新的密 碼系統─信託金鑰密碼系統 (Key Escrow System)。在這個系統□，警方 可以透過合法的程序對犯罪嫌疑犯的通訊內容進行監聽。Micali也在 Crypto *92上提出一個不同的方法─fairpublic key cryptosystem─解 決相同的問題。Lenstra等在Crypto *95上則更進一步提出一套方法 (LWY scheme) 使的警方在監聽對象上更有彈性。然而這些系統都潛在地存在一 些不方便的地方。在本篇論文□頭，我們將提出三種方法設計一個新穎的 數列，我們將它稱之為“可分段共享的暗門數列” (trap-door segment- sharable sequence, TSS)。此數列擁有一個特殊的性質，那就是在給定 固定量的資訊之情況下，我們可以將任何一小段的數列與他人分享並且不 會洩漏其他數列元素的資訊。我們將它應用到信託金鑰密碼系統的設計上 。由於TSS的應用，我們的系統避免了像KES、Micali系統、及LWY系統上 所出現的缺點。除此之外我們還將TSS應用到“金匙備份系統”(key backup system) 上，並完成多階層金匙備份系統”的設計。這篇論文的 主要貢獻在於一個新穎數列─TSS─的提出以及信託金鑰系統與金匙備份 系統的設計。 The U.S. goverment announced the Key Escrow System (KES) to resolve the abuse of cryptosystems and to protect sessitive but unclassified data. In KES, the law enforcement (the police) can line-tap the suspect's communications under legal process. In 1992, Micali also proposed an alternative scheme (fair public- key cryptosystem) to construct key escrow systems. In 1995, Lenstra et.~al.~presented another scheme to extend the flexibility of the target surveillance of Micali's. However, drawbacks exist within all of them. In this thesis, we create a novel sequence -- trap-door segment-sharable sequence (TSS). A TSS is a number (or number pair) sequence whose segment can be made sharable without revealing other elements. Under standard cryptographic assumptions, three schemes are proposed to construct TSS -- one uses modular exponentiation, the other uses elliptic curves, and another uses Lucas sequences. We apply TSS to design key escrow systems. In our key escrow systems, the drawbacks which appears in KES, Micali's system and LWY's system are avoided. Besides, we find that our TSS has nice properties. We also apply it to create key backup systems. With TSS, we construct multi-level key backup systems. The major contribution of this thesis is the proposed TSS and its applications in key escrow systems and key backup systems.