淺談哈希證明系統

01-25

DENG神已經對零知識證明系統 (Zero Knowledeg Proof) 做了極為精彩的科普, 在這裡我淺談零知識證明系統的一個小弟—哈希證明系統, 回答以下三個問題:

從哪裡來?
究竟是誰?
到哪裡去?

零知識證明系統的一個重要性質是任何驗證者均可快速驗證一個證明是否有效, 即公開可驗證性. 這一強性質恰恰是構造高效零知識證明系統的障礙之一. 一個自然的問題是能否弱化該性質使得高效的構造成為可能, 答案是肯定的.

1、從哪裡來

Ronald Cramer和Victor Shoup在1998年給出了首個標準模型下高效的選擇密文安全的公鑰加密方案, 簡稱CS98方案, 該方案的設計新穎獨特, 結構精巧有如神來之筆, 大家看了均表示不明覺厲.

2002年, Cramer和Shoup將CS98方案的設計思想凝練抽象為哈希證明系統 (Hash Proof System, HPS), 至此密碼學的軍火庫又新添了一個強有力的武器, 其威力和影響遠遠超出最初的選擇密文安全公鑰加密.

2、究竟是誰

哈希證明系統的名字十分酷炫, 它到底是啥呢? 一句話: 是指定驗證者的非互動式零知識證明系統, 因其證明為哈希值, 故名哈希證明系統.

看公式和符號容易頭暈, 所以我把它們畫成了圖

首先介紹語言系統的概念:

令 $X$ 是一個實例集合, $L$ 是 $X$ 中由某二元關係 $R$ 定義的一個真子集, 即 $x in L$ 當且僅當存在 $w in W$ 使得 $(x, w) in R$ , 那麼 $(X, L, W, R)$ 構成了一個語言系統, $L$ 為語言集合, $W$ 為證據集合. $L$ 中的實例常稱為Yes實例, $L$ 之外的實例稱為No實例.

為了有密碼學上的應用, 通常要求語言系統上存在所謂的子集成員不可區分問題(SMP): 一個隨機的Yes實例和一個隨機的No實例是計算不可區分的.

舉個例子

$X$ 好比全體人類的集合

$L$ 是其中所有好人的集合, 每個好人都有一張好人卡(證據)

$X ackslash L$ 是壞人集合, 壞人呢? 沒有卡...

因為好人和壞人頭上都沒寫字, 所以隨便拉一人你很難區分他是好人還是壞人

關於語言系統 $(X,L,W,R)$ 的哈希證明系統由三個演算法組成:

密鑰生成演算法 $mathsf{Gen}$ : 生成一對密鑰 $(pk, sk)$ , $sk$ 與 $pk$ 之間存在多對一的投射關係, 即 $alpha(sk)=pk$ . 每個 $sk$ 都定義了一個哈希函數 $mathsf{H}_{sk}: X ightarrow Pi$ , 其中 $X$ 是實例空間, $Pi$ 是證明空間.

私有求值演算法 $mathsf{Priv}$ : 擁有 $sk$ 時可以高效計算 $mathsf{H}_{sk}(x)$ , 其中 $x$ 是 $X$ 中的任意實例.

公開求值演算法 $mathsf{Pub}$ : 當 $x$ 屬於語言 $L$ 時, 可以在沒有 $sk$ 的情況下根據 $pk$ 和 $x in L$ 的證據 $w$ 計算出哈希值 $mathsf{H}_{sk}(x)$ .

哈希函數 $mathsf{H}_{sk}$ 的以下性質刻畫了其在 $X$ 上的截然不同的兩種行為:

投射性: $forall x in L, mathsf{H}_{sk}(x) = mathsf{Pub}(pk, x, w)$ , $pk = alpha(sk)$

該性質刻畫的是當哈希函數的輸入為語言中的元素時, 其輸出由對應的公鑰和元素本身惟一確定, 與私鑰無關. 可以理解為好人太老實, 總是一根筋, 不管私鑰 $sk$ 是啥, 哈希值都不變.

均勻性: $forall x otin L, mathsf{H}_{sk}(x)$ 在 $Pi$ 上均勻分布

該性質刻畫的是當哈希函數的輸入不在語言中時, 其輸出在 $Pi$ 中隨機分布. 可以理解為壞人花樣百出, 私鑰 $sk$ 不同, 哈希值也不同.

語言系統上的困難問題告訴我們 $L$ 中的隨機元素和 $L$ 外的隨機元素是計算不可區分的, 這一點是聯繫兩大性質的紐帶.

從上面的定義似乎看不出證明系統的影子, 看完下圖就瞭然了:-)

可信第三方運行密鑰生成演算法, 生成一對公私鑰 $(pk, sk)$ ，將 $pk$ 作為公共參考串 $crs$ , $sk$ 作為trapdoor發送給驗證者 $V$

證明者 $P$ 如何向 $V$ 證明 $x in L$ ( $x$ 是一個好人) 呢? 運行公開求值演算法 $mathsf{Pub}(pk, x, w)$ 計算哈希值 $pi leftarrow mathsf{H}_{sk}(x)$ 並發送給 $V$ , 證明本身就是實例的哈希值!

$V$ 如何驗證呢? 利用從可信第三方處獲得的 $sk$ 計算哈希值並與 $P$ 發送過來的進行比對, 相等就接受, 否則拒絕.

上述協議顯然是非交互的, 下面逐一驗證證明系統的性質:

完備性: 當 $x in L$ 時, 哈希函數的投射性保證了 $P$ 給出的證明 $V$ 都會接受
合理性: 當 $x otin L$ 時, 哈希函數的均勻性保證了即使 $P$ 擁有無窮的計算能力, 輸出正確哈希值的概率也是可忽略的.
零知識性: 由於 $V$ 本身擁有 $sk$ , 它看到的證明自己就能夠獨立計算出來, 證明的零知識性是顯然成立的的.
指定驗證者: 只有擁有 $sk$ 才有能力驗證一個證明的真偽.

以上的條分縷析說明哈希證明系統就一個指定驗證者的非互動式零知識證明系統.

3、到哪裡去

花了很長的篇幅說了哈希證明系統究竟是啥, 可能很多小夥伴都暈了, 其實以上僅僅是極其精要的概述, 很多細節已經略去了, 有興趣大家可以讀原文.

當今幹啥都講究有用, 那下面就簡單說說哈希證明系統有哪些神奇的、不可替代的應用.

在此之前, 首先給出哈希證明系統的兩個局限和兩點觀察:

兩個局限

證明不具有公開可驗證性
證明的表達能力有限, 目前僅能對證明群中的子群成員歸屬問題, 尚未知能否延伸到任意的NP語言.

在很多具體的零知識證明應用場合, 公開驗證性和強大的表達能力均不是必須, 因此用標準的零知識證明系統就是高射炮打蚊子—大材小用, 哈希證明系統可以做的更快更好! (效率的優勢恰恰源自局限)

兩點觀察

哈希證明系統中的證明者是高效的, 即證明者在擁有相應的證據 $w$ (好人卡)時, 可以快速計算出證明. 這一點是不僅是哈希證明系統，也是所有證明系統有用的前提條件.
私鑰與實例的無關性: 即使驗證者擁有一個私鑰, 也無法判定給定的實例是否屬於 $L$ . 該性質可以理解為一個人是好人還是壞人和判定的方法無關. 該性質尤為重要.

所有基於哈希證明系統的密碼方案的安全性建立均是三板斧套路:

真實的方案設計選取語言中的實例 $x in L$
想像中的方案設計選取語言外的實例 $x otin L$
我們利用哈希函數的均勻性說明證明中方案的安全性, 再利用語言系統的不可區分性說明敵手無法察覺實例的真偽切換, 最終證明真實的方案是安全的.

特別值得指出的是, 基於哈希證明系統的方案證明集中體現了hybrid argument的論證方式、計算意義下的歸約和資訊理論意義下的證明, 是可證明安全從入門到精通的最佳切入點.

在設計可證明安全的密碼方案特別是公鑰加密方案中的一個主要技術難點是: 私鑰往往嵌入在底層的困難問題中, 因此歸約演算法通常並不掌握私鑰, 但歸約演算法又必須能夠回答敵手關於私鑰的詢問. 一個很好的例子就是難以證明ElGamal類型加密滿足選擇密文安全性, 因為私鑰嵌入在底層Diffie-Hellman困難問題中.

哈希證明系統另闢蹊徑, 直接繞過該難點, 關竅就在於私鑰與實例無關, 歸約演算法始終擁有私鑰，因此可以輕鬆回答關於私鑰的任意詢問.

這一特性使得哈希證明系統成為構造以下密碼方案的利器:

高安全性公鑰加密, 包括選擇密文安全、密鑰泄漏安全、密鑰篡改安全、選擇打開攻擊安全, 特別的, 它幾乎是構造抗泄漏公鑰加密方案的不二法門
密鑰交換協議: 包括基於口令的密鑰交換和認證密鑰交換
不經意傳輸協議

哈希證明系統還有諸多變體, 如:

基於身份的哈希證明系統: 用於構造基於身份的加密
同態的哈希證明系統: 用於構造消息依賴密鑰的公鑰加密方案
可延展的哈希證明系統: 密碼逆向防火牆
可更新的哈希證明系統: 抗持續泄漏的公鑰加密
對偶的哈希證明系統: 這個厲害了, 直接蘊含另一核武器—有損陷門函數

總結

哈希證明系統是零知識證明系統一個小弟, 勝在結構簡潔優美, 實例切換+資訊理論意義下論證的三板斧套路極其有用, 從銅鑼灣砍到尖沙咀. 低配版的小弟都這麼厲害, 那大哥就猛得沒邊了.

預告

以後打算介紹零知識知識證明系統 (Zero-Knowledge Proof of Knowledge) 的小弟—可提取哈希證明系統, 還有各種類型的單向函數.

歡迎大家的意見和反饋:-)

更新

有的朋友想通過一些例子更加形象直觀地理解, 這裡先給出一個我認為最簡單的具體構造 (基於DDH假設的universal HPS, 也稱為Cramer-Shoup Lite HPS).

今後想到更簡單的例子會及時補充.

p.s. 密碼學中的構造通常只會在概念上簡單、構造上簡潔, 一目了然和異常複雜的方案設計多半是不安全的.