時間鎖定謎題

最近工作上事情比較少，摸魚的時候看了很多有意思的東西，找 VDF 相關資料的時候講到一個問題：如何設計一個只能在指定的時間 $T$ 後才能解出來的 puzzle 我先想了一下但是沒想明白，怎麼把時間這種抽象的概念在一個 puzzle 裡面給量化出來。🤔

然後就翻到了這篇引用的論文 Time-lock puzzles and timed-release Crypto

看了文章才發現實際上這個問題可以等效於：設計一個演算法，只有在經過 $P$ 次計算後才能夠得到正確的結果，且這個演算法的計算過程不能被並行計算加速。這樣只能使用一台機器解密，假設其每秒最高算力為 $S$ 則一定要經過 $T = P / S$ 秒後才能解出正確的結果，達到了 time-lock 的目的。

文章裡介紹了兩種 time-lock puzzle 的實現方式。

第一種 time-lock puzzle 設計#

假設 Alice 有一個資訊 $M$ 要傳遞給 Bob 但是需要加密 (鎖定) $T$ 秒鐘的時間。(這裡有一個前提是 Alice 需要事先知道 Bob 的算力情況)

加密#

第一步，隨機選擇兩個大質數 $p$ 和 $q$ 將他們相乘得到 $n = p*q$ 同時計算 $\phi(n) = (p-1)*(q-1)$

第二步，計算 $t = T*S$ 其中 $S$ 是 Bob 單機每秒能夠進行的對 $n$ 平方取模的次數 (也就是所謂算力)

第三步，隨機生成一個足夠安全的，用於加密的密鑰 $K$ 和一個加密演算法比如 RC5

第四步，使用密鑰和加密演算法加原始資訊得到 $C_m = RC5(K, M)$

第五步，選擇一個隨機數 $a\ (1 < a < n)$ 然後加密 $K$ 得到 $C_k = a^{2^{t}}\ (mod\ n)$

這一步可以通過以下步驟進行加速：首先計算 $e = 2^{t}\ (mod\ \phi(n) )$ 然後計算 $b = a^{e}\ (mod\ n)$

最後 Alice 將 $(n, a, t, C_k, C_m)$ 公佈給 Bob

解密#

對於 Bob 來說獲取 $M$ 需要用密鑰 $K$ 解密 $C_m$ 但是加密時已經保證 $K$ 本身是足夠安全的 Bob 只能通過 $C_k$ 計算得到 $K = C_k - a^{2^{t}}\ (mod\ n)$

這裡只剩下 $t$ 一個未知數，對於 Bob 來說除了暴力遍歷所有 $t$ 沒有其他更好的辦法。

這樣則需要經過 $a^{2}, a^{4}, a^{8},a^{16},...a^{x} (t = 1,2,3,...)$ 這樣一個序列的計算，可以觀察到在這個序列裡，每一項的計算都依賴前一項的計算結果 $a^{4} = (a^{2})^{2}, a^{8} = (a^{4})^{2}, ...$ 即無法提前計算後面的值，也不能並行加速計算。只能通過 $t$ 次計算得到結果，而根據之前設定的 $t = T*S$ 所需要計算的時間就是 $T = t/S$ 也即達了 Alice 將消息鎖定 $T$ 時間的目的。

（至於 Bob 如何判斷自己找到了正確的 $K$ 就不屬於這個演算法裡面的問題了。一種方式是加密者可以給出 $sha256(K)$ 讓 Bob 自己校驗。）

第二種 time-lock puzzle 設計#

第二部分沒仔細看，直接在 Claude2 上面上傳論文讓後讓 AI 幫忙總結的 (沒有 GPT-4 可以用的情況下非常推薦用 Claude2)

ME: 介紹下第二種方法如何實現

文章提出的第二種使用受信任代理的方法大致如下:

設置多個受信任的代理，每個代理定期公佈一個密鑰。

用戶將消息用一個隨機密鑰加密，得到密文。

用戶將該隨機密鑰通過密鑰分享方案分成多個份，分別給不同的代理。

每個代理使用在未來時間 t 公佈的密鑰，加密自己持有的那一份子密鑰。

在時間 t, 足夠多的代理公佈了他們在 t 時刻的密鑰。

用戶可以用這些密鑰解密出子密鑰份，然後重構出原始的隨機密鑰。

最後用這個隨機密鑰解密出原始消息。

這種方法的安全性依賴於受信任代理不提前洩露未來的密鑰。同時設置多個代理，可以通過密鑰分享和閾值檢驗來實現一定的容錯性。即使個別代理被攻破或失效，只要有足夠的代理仍正常工作，信息仍能在預定時間解密出來。