金鑰演化密碼學之研究

Abstract

在公開金鑰密碼學裡，許多論文已經討論過了金鑰洩露的處理問題，有一些方法被用來處理金鑰洩露的問題，比如分散式的門檻方式、預防的機制以及智慧卡的硬體保護方法等。 在這篇論文中，我們提出第一個金鑰演化的密碼方法去處理這個問題，它如同前向安全的簽章(forward-secure signature)系統一樣，有一個特性:就是私密金鑰會隨著時間而改變，但是公開的金鑰卻是固定不變的。我們將金鑰的生命週期分成小的時間區段，在時間區段 $j$，解密者擁有時間區段 $j$的私密金鑰 $SK_j$；在時間區段 $j+1$，解密者擁有時間區段 $j+1$ 的私密金鑰 $SK_{j+1}$。但是在金鑰的有效期間內，公開金鑰卻是固定不動的。如果一個傳送者要送訊息 $m$ 給解密者，他必須由公開金鑰 $PK$ 計算時間區段 $j$ 的公開金鑰 $PK_j$，再將信息加密成 < j, c >。當時間區段從 $j$ 移轉到 $j+1$， 解密者需要更新他的私密金鑰 $SK_j$ 成為 $SK_{j+1}$，然後立刻刪除 $SK_j$。金鑰演化的密碼系統，即使私密金鑰 $SK_j$遺失或是洩露，不會影響其他時段加密的訊息之安全。 這篇論文主要的結果如下： 1.我們提出三個簡單的金鑰演化公開金鑰加密方法，這些方法具有 $z$-彈性 的性質，使得 $z$ 把私密金鑰被暴露，仍然不影響其他時間區段的加密訊息的安全。和傳統的公開金鑰密碼系統比較，新的加密方法的密文中包含了時間的資訊。為了證明新的密碼方法是安全的，我們假設DDH問題是難的，和random oracle模式成立。我們的新的密碼方法是可以抵檔被動的攻擊(passive attack)和適當的選擇密文攻擊法(adaptive chosen ciphertext attack)。 2. 我們提出解密者如何在TA們的幫助下，使用安全的分散式計算方法，算出新的私密金鑰。然後提出分散式的金鑰演化密碼系統，並且討論如何將分散式的金鑰演化密碼系統，和預防的機制(proactive mechanism)作結合，來加強TA的安全性。 3.我們提出一個分散式門檻的前向安全簽章方法，加強了 Abdalla and Reyzin 的前向安全簽章方法的安全性，主要是藉由兩個技巧，門檻的方式和預防的機制來做到的。這個分散式門檻的前向安全簽章方法組合了多項式秘密分享(polynomial secret sharing)和乘法的(multiplicative)技巧。如果原來的單一使用者(single-user)的簽章方法是安全的，我們可以證明新的分散式的簽章方法是安全的。 金鑰演化加密系統可以應用到以憑證為基礎的認證系統，使得認證協定達到前向安全(forward-secure)和後向安全(backward-secure)，並且可以減少CRL的儲存代價。公開金鑰的憑證被應用在電子商務、存取網際網路資源及個人通訊服務等方面，為了儲存被取消的憑證，網路服務供應者SP(Service Provider)需要額外的儲存空間。而這樣的系統安全是和目前時段的秘密金鑰有關，既然時段$j$ 的私密金鑰$SK_j$將在時段 $j+1$ 時無效，所以時段$j$的CRL，在時段$j+1$可以不需要存著。所以每一個新的時段的開始，CRL的大小就是0，因而可以節省儲存CRL的空間，減少SP對儲存CRL所付出的代價。另外我們討論了"同步時間"的問題，我們假設一個服務供應者存在著同步時間的伺服器。

The key exposure problem of public key encryption schemes has been discussed in the open literature. Threshold cryptosystems, proactive mechanism and smart card are used for many years to handle this problem. In this thesis, we propose the first key-evolving paradigm to deal with the key exposure problem. The key-evolving paradigm is like the one used for forward-secure digital signature schemes. Let the lifetime of the master secret key be divided into time periods such that at time period $j$, the decryptor holds the private key $SK_j$, while the public key PK is fixed during its lifetime. At time period $j$, a sender encrypts a message $m$ as < j, c >, which can be decrypted only with the private key $SK_j$. When the time makes a transit from period $j$ to $j+1$, the decryptor updates its private key from $SK_j$ to $SK_{j+1}$ and deletes $SK_j$ immediately. The key-evolving paradigm assures that compromise of the private key $SK_j$ does not jeopardize the message encrypted at the other time periods. Our results are listed in the following. 1. We propose three simple key-evolving public key encryption schemes with $z$-resilience such that compromise of $z$ private keys does not affect confidentiality of messages encrypted in other time periods. Comparison to the public key cryptosystems, a ciphertext in the new scheme contains time information. Assuming that the decisional Diffie-Hellman (DDH) problem is hard and the random oracle model, we show that our schemes are secure against passive adversaries and against adaptive chosen ciphertext attack. 2. We present how key-evolving with TAs does. The decryptor can evolve the private key by the aid of TAs in a secure distributed way. Then, we consider the case of distributed key-evolving encryption scheme. Furthermore, we combine the distributed methods with proactive mechanism to enhance the security of TAs. 3. We propose a distributed forward-secure signature to enhance the security of Abdalla and Reyzin's forward-secure signature scheme via threshold and proactive mechanisms. Our distributed threshold forward-secure signature scheme combine both multiplicative and polynomial secret sharing tricks. Then, We can prove that our scheme is secure if the single-user scheme is secure.

The key-evolving public key encryption schemes are applied to reduce the storage cost of Certificate Revocation Lists (CRLs) in the encryption certificate-based authentication protocols. Public key certificates have been used in many applications, such as electronic commerce, accessing Internet resources and personal communications services, etc. Let Service Provider (SP) provide some services. The users subscribe the services from SP. While accessing the services, SP authenticates the identity of the user via a certificated authentication protocol based on the key-evolving public key encryption scheme. However, if a user's secret key for the certificate is lost or compromised, SP need additional storage cost for saving CRLs. The security of such certificate-based protocols depends on the secret key of the current time period. Since the disclosed secret key $SK_j$ of time period $j$ is automatically revoked at time period $j+1$, CRLs of time period $j$ does not be maintained at time period $j+1$. That is, in the beginning of a new time period the size of CRLs is reset to zero. Thus, the size of CRLs can be reduced. Finally, we discuss the problem of time synchronization. Our schemes assume that SP should have time server for synchronization among SP and all subscribers.