動機
知道一個秘密與洩露一個秘密是不同的行為。持有離散對數的用戶可以在不發送該對數的情況下證明自己知道它:先承諾一個隨機群元素,再回答一個新的挑戰。隨機承諾使見證(witness)在回應中被隱藏,而對同一承諾回答兩個不同的挑戰則會暴露見證。理解這兩面,就能明白為甚麼臨時隨機數與長期密鑰同樣敏感。
由此得到的三訊息協議是簽名的數學起點。把驗證者的挑戰替換為訊息與承諾的雜湊值,便得到一種非交互的簽名規則,但僅有正確性並不能確立不可偽造性。我們將證明確切的交互性質並給出具體的失效例子;完整的隨機預言機模型歸約既不被假設,也不被悄悄地聲稱。
定義:交互記錄及各自的角色
見證是滿足公開關係的值;這裏的關係是 。驗證者看到公鑰與對話中的訊息,誠實證明者還知道一個見證。交互記錄按次序保存一次對話,包括挑戰。被接受的記錄指驗證者規定的檢驗通過。這些詞描述數學角色,不自動保證軟件實現具備相應性質。
均勻選擇純量時,概率空間給每個域元素賦予 的概率。誠實執行中的挑戰分佈與證明者隨機數相互獨立。惡意參與者可以按別的規則選擇;各定理會明確指出何處需要誠實分佈,何處適用於任意被接受的記錄。看清這些量詞,才能避免把分佈模擬誤當成對一般攻擊的防禦保證。
群、見證與交互
設 為質數,設 為恰有 個元素的循環群,採用乘法記法。指數是域 中的元素;單位元記為 。公鑰為 ,其中秘密 。群、其元素的規範編碼以及 都是公開的。在實際實現中, 中的成員判定與相等判定必須可以高效檢查;在下面的協議中,它們都是數學運算。
證明者從 中均勻地抽取 ,並發送 。驗證者從 中均勻且獨立地抽取挑戰 。證明者返回
驗證者當且僅當收到的各個值都是合法的群元素或純量,並且 時才接受。值 構成一份交互記錄(transcript)。因為兩次使用同一隨機數而重用 ,並非對兩次交互的無害壓縮:其後果將被顯式計算。
常見錯誤
(用錯誤的模數約化回應)
回應 是 的指數,所以只有它模群的階 的剩餘類才有意義;它並不是外層模數下的元素。取模 下由 生成、階為 的群,並設 、、、、。則 。模 約化得 ,而 ,所以記錄通過驗證。若改為模 約化,得到 ,而 :誠實的證明者反而被拒絕。不約化 並無害處,因為 ;但以不是 的倍數的數取模就會出錯。
定理 4.4.1
(完備性與特殊可靠性)
誠實的證明者總能通過驗證。從任意兩份接受的交互記錄 與 (承諾相同、挑戰不同)出發,可以高效地恢復滿足 的見證 :
該結論針對的是同一公鑰、同一承諾下的兩份接受記錄;僅有一份接受記錄不足以使用這一提取公式。
證明
(把兩個驗證等式相除)
對於誠實的回應,。對於提取,將兩個被接受的等式相除,得到 。因為 在域中非零,所以它有逆元。把等式兩邊同時取該逆元次冪,得到 。這一代數推導並不要求我們事先知道離散對數。 為質數很關鍵:在合數模的指數環中,非零的挑戰之差不一定可逆。
證明透視
重複的承諾就是公共方程
兩個回應包含同一見證的不同倍數,以及完全相同的未知隨機數。相減即消去該隨機數。若兩個承諾不同,則兩個回應相減後仍留下兩個未知隨機數,此提取論證便不再適用。若兩個挑戰相同,則所需的逆元不存在。這些都是假設條件,而不是記賬式的裝飾。
模擬誠實驗證者
一份交互記錄可以看起來真實可信,卻並非利用見證生成。這一觀察是關於誠實抽樣的挑戰的精確分佈陳述;它還不是關於每一種交互式驗證者的陳述。
定理 4.4.2
(誠實驗證者交互記錄的精確模擬)
對於合法的公鑰 ,在 中獨立且均勻地選取 ,並令 。所得的交互記錄與帶有獨立均勻挑戰的誠實執行具有完全相同的分佈,並且總能通過驗證。
證明
(隨機數與回應之間的雙射)
寫 。在誠實執行中,數對 在 上均勻分佈。映射 是雙射,因為 。因此 同樣均勻分佈。此時承諾為 ,這恰好就是模擬器的輸出。驗證成立由 的定義直接得出。模擬器並不計算 ;證明只是為了比較分佈而用到 在數學上的存在性。
各個值的生成順序至關重要。在真實交互中,證明者在看到驗證者的挑戰之前就發送 。若模擬器在選定 之後才選擇 ,它能重現最終的誠實交互記錄分佈,但這本身並不能模擬任意的驗證者,因為這種驗證者的挑戰可以依賴於 及其自身狀態。更強的零知識定義及其證明需要額外的工作。
概念視角結構
存在性、知識與分佈
因為 生成 ,所以 中每個元素都有某個指數。這一存在性事實並不提供找出該指數的高效算法。特殊可靠性從兩份具有特定關係的接受記錄中給出這樣一個算法。誠實驗證者模擬則在沒有見證的情況下給出一個不可區分的交互記錄分佈。這些陳述單獨來看都不是計算困難性定理。
例題 4.4.3
(一份完整的小規模交互記錄)
在模 的乘法群中,元素 的階為 :,而其階既不是 ,也不是質數 的其他任何因數。取 ,則 。取 ,則 。若挑戰為 ,則回應為 。驗證等式兩邊在模 下都等於 :,且 。這裏的算術有意取得很小,便於手算檢查;這樣的群不提供任何實際安全性。
例題 4.4.4
(模擬同一份公開交互記錄)
保持 、、。直接選取 與 。模擬器計算 。所得交互記錄與前一個例子完全相同,而模擬器並不需要找出 。單個吻合的例子只是說明該公式;證明整個分佈相等的是上面的雙射,而不是這個例子。
一種簽名規則及其邊界
設 為一個指定的公開函數,它把 的規範編碼映射到 。為訊息 簽名時,抽取一個新的均勻隨機數 ,計算 ,令 ,並輸出 ,其中 。驗證時,根據所給的承諾與訊息重新計算 ,檢查所有編碼與成員資格,並當且僅當 時接受。正確性由前面的等式得出。
雜湊輸入必須有無歧義的編碼。在真實協議中,不同的群元素與訊息不得意外地序列化為相同的輸入,並且域分隔符與算法標識符需要有約定的格式。對於格式錯誤的元素或超出範圍的純量,應當拒絕,而不是把它們的位元表示當作自動合法的成員。這些檢查是「被簽名之物」這一定義的一部分;僅僅寫出群上的等式並不能提供它們。
常見錯誤
(只對訊息雜湊而不包括承諾)
若挑戰取為 ,偽造者在選擇承諾之前就已知道挑戰。對任意訊息,它任選 並令 ;於是 ,驗證在不知道 的情況下就會接受。這正是以 為挑戰運行的誠實驗證者模擬器。在模 的小群中取 ,若某訊息滿足 並選 ,則 ,即上面模擬例子中的交互記錄。把 納入雜湊輸入,就迫使承諾在挑戰為人所知之前已經固定。
定理 4.4.5
(兩個共用一個隨機數的簽名會洩露密鑰)
假設同一公鑰下的兩個有效簽名使用同一個隨機數 ,其挑戰滿足 ,回應分別為 。則公開的交互記錄決定秘密剩餘類
若 本身從一個有效回應中被獲知,且 ,則 。無論 是否具有任何密碼學安全性質,這些陳述都成立。
證明
(特殊可靠性,以及已知的隨機數)
第一個結論就是特殊可靠性:重複的隨機數給出相同的 。對於第二個結論,將 整理,並對非零挑戰取逆。若兩個挑戰相同,則上面所寫的逆元不存在;不能由這些公式推斷出秘密。隨機數重用在其他方面仍可能是危險的,但那是另一個需要獨立論證的命題。
例題 4.4.6
(恢復被重用隨機數所保護的秘密)
繼續上面的小群例子。用同一個 回答第二個挑戰 ,得到 。挑戰之差為 ,其逆元為 。因此 ,恢復出了秘密。這裏並不假設一個現實的雜湊函數可以被迫輸出所選的那一對挑戰;該計算以兩個實際存在的不同挑戰為條件。
例題 4.4.7
(為甚麼看似隨機的密鑰並不足夠)
假設簽名者只一次性均勻隨機地選取秘密 ,但一個軟件故障使同一個隨機數被用於兩條挑戰不同的訊息。提取公式恰好返回最初那個隨機的 。良好的初始密鑰分佈並不能彌補隨機數重用。反過來,若用帶有隱藏偏差或洩露的過程產生不同的隨機數,則需要作超出「檢查所觀察到的兩個承諾不同」的分析。
反例模式
驗證正確並不蘊含不可偽造性
取公開函數 ,對一切輸入都成立。一個從未請求過簽名的攻擊者任選 ,令 ,並對任意訊息輸出 。驗證會接受,因為 。誠實的簽名等式仍然正確,但簽名是可偽造的。這個例子排除了僅憑該等式就得出安全性結論的做法;它並不是說每一個非常數雜湊函數都是安全的。
證明確立了甚麼,又沒有確立甚麼
該交互具有完美完備性、上述的兩份記錄提取性質,以及精確的誠實驗證者交互記錄模擬器。這些都沒有說明多項式時間的攻擊者無法偽造簽名。這樣的定理需要精確的攻擊實驗、對群的計算性假設,以及對挑戰函數適當的模型或具體性質,並配以計入查詢次數與概率損失的歸約。上面的模擬器不能簡單地對一個普通的固定雜湊函數進行編程。我們在此不證明這一更強的定理。
均勻性指的是在每次執行中都從整個 中獨立抽樣。特別地,這一數學版本允許取零;具體的標準可能規定不同的隨機數取值域和抽樣過程。避免模偏差、保護瞬時狀態、防止崩潰後重複使用隨機數,以及綁定正確的協議上下文,都是抽象證明所不能擔保的實現問題。重放一個舊的有效簽名,也不同於對新訊息偽造簽名:應用可能需要自己的重放策略。
練習
快速檢查
(當 時驗證一份誠實的交互記錄。這一次執行是否揭示 ?)
比較回應與隨機數。
解答
回應為 ,且 ,所以驗證成功。由於 ,這份記錄的回應等於隨機數,不含 的任何代數倍數。已知隨機數時的提取公式要求 ;這裏不能使用。這並不分析跨其他交互的洩露。
快速檢查
(對上面模 的群,模擬一份 、 的交互記錄。在不使用 的情況下檢查驗證。)
使用 。
解答
模擬器取 (模 )。交互記錄 通過驗證,因為 。它由公開資訊構造而成,而模擬器的完整分佈是由雙射證明的,並非由這一個樣本證明。
快速檢查
(兩份接受的交互記錄共用 ,在 中回應為 、,挑戰為 、。恢復指數,並指出公開的群元素。)
套用特殊可靠性的公式,再計算 模 。
解答
回應之差為 ,挑戰之差為 ,其模 的逆元為 。因此恢復的指數為 ,且 。兩份記錄確實以同一 與同一公鑰通過驗證,這一假設是必要的;任意的數值對未必是交互記錄。這裏兩者是一致的:兩份記錄都給出隨機數 。
快速檢查
(說明當兩個挑戰相等時,兩回應提取公式究竟在哪裏失效。它們之差的逆元是否存在?)
看看驗證等式對 與 有甚麼要求。
解答
若 ,則 ,而零在 中沒有乘法逆元。對於同一承諾、同一挑戰下的兩個有效回應,驗證等式迫使 (模群的階),因此相減只得到 。這並不給出 的任何值。
快速檢查
(在常數零雜湊的反例中,在小群裏取 。給出偽造的簽名,並驗證它對任意訊息都滿足驗證等式。)
當 時,驗證等式化為 。
解答
取 ,輸出 。驗證者得到 ,並檢查 (模 )。該簽名對每條訊息都能通過驗證,既不需要任何簽名查詢,也不需要知道秘密指數。