針對NP斷言的3-輪證據不可區分證明協議
我們希望能夠對一般性的NP斷言構造零知識或證據不可區分證明系統。幸運的是，對於任意的NP斷言「x是正確的」（如「G0和G1是同構的」，「圖G中存在一個簡單的圈經過所有的頂點」等），或者，任何有關多項式時間演算法正確性的斷言，我們都有一個3-輪的證明協議同時具有上述兩個性質：證據不可區分與（具有可忽略可靠性錯誤）知識的證明性質。
Blum在1986年的國際數學家大會上[Blum, ICM86]報告了一個對漢密爾頓圖（上述帶有一個經過所有點的簡單圈的圖）的3-輪可靠性錯誤為1/2的零知識證明。由於漢密爾頓圖集合為NP-完全集合，任何其他NP問題都可以歸約到一個漢密爾頓圖的問題，Blum的構造實際給出了對任意NP斷言的零知識證明。透過並行Blum協議後我們得到了針對任意NP斷言的3-輪 （具有可忽略可靠性錯誤和知識的證明性質）證據不可區分證明協議。 Goldreich等人[GMW, FOCS 86]針對另一個NP-斷言（圖的三著色問題）給出了另一個類似的構造。
Feige-Shamir的構造
目前為止, 我們透過並行犧牲了零知識性，但得到了可忽略的可靠性錯誤和證據不可區分的性質。我們能夠構造一個具有可忽略可靠性錯誤的常數輪零知識證明協議嗎？答案是肯定的。Feige和Shamir[FS, STOC 90]給出了一個有著廣泛影響的優雅構造[3] 。給定一個NP斷言「x 是正確的」， P持有這一斷言的證據（如圖同構中的n）向V進行如下兩階段的證明：
利用第一階段的證據不可區分性（為什麼V需要生成兩個原像？）和第二階段的知識的證明的性質，我們可以證明，如果函式f是單向的，那麼Feige-Shamir協議的（可抗多項式時間惡意證明者的）可靠性錯誤仍是可忽略的；利用第一階段的知識的證明性質（模擬器可以透過呼叫上述抽取器，透過重置驗證者來抽取到一個原像）和第二階段的證據不可區分性，我們可以證明 Feige-Shamir協議是零知識的。此外，透過合理安排兩階段的訊息順序，我們可以得到一個4-輪的具有可忽略可靠性錯誤的零知識協議。
注意到Feige-Shamir協議需要假定存在單向函式，這與無需任何假設的圖同構的零知識證明有著本質的區別。事實上，只有很少的斷言具有像圖同構那樣的完美零知識證明[Fortnow, CCC 87]。
黑盒模擬/歸約的侷限性
注意到如果相對化的證明技巧如果能解決 NP vs P問題，那麼相對於任意的oracle結論都應該一致。BGR意味著我們無法僅僅利用相對化證明技術來證明或否定NP=P。在研究互動證明的威力過程中，Nissan發現的非相對化的證明技術——算術化（arithmetization）——打破了之前相對化技術的壁壘，導致了一系列像IP=PSPAC和PCP定理這樣影響深遠的非相對化；結果。然而，對於這些非相對化結果的解讀依然存在著分歧。感興趣的讀者可以參考Fortnow和Arora, Impagliazzo, Vazirani寫的一些未發表的文章[5] 。
絕大多數密碼學中歸約（安全性證明）都是相對化的，也就是我們常說的黑盒歸約。Impagliazzo和Rudich [IR, STOC 89]發現了第一個黑盒歸約的分離（我們有時也稱黑盒下界）結果：我們無法將公鑰加密透過黑盒歸約的方時建立在抽象的單向函式上。通常，欲證明一個密碼原語P無法透過黑盒歸約的方式建立在困難假設Q上，我們只需去構造一個oracle，在提供這個oracle介面的世界裡，存在著高效的演算法打破P的安全性，但不存在高效的演算法打破Q的困難性。
Impagliazzo和Rudich提供的證明黑盒分離/下界的正規化對密碼學影響巨大，後來研究人員發現了許許多多這樣的負面的結果。
Reingold, Trevisan和Vadhan [RTV, TCC 04]對於這些黑盒分離/下界提供了一些較為清晰的解讀。
零知識證明中的黑盒下界通常指黑盒模擬（模擬器只允許以黑盒方式呼叫驗證者，對應的零知識稱為黑盒零知識）下的輪複雜度下界。注意到像前面提到IP=PSPACE一樣，零知識證明中許多結果也是非相對化的，我們在證明它的黑盒輪複雜度下界時通常用到一個不同的證明策略：低輪複雜度的零知識證明所帶有的黑盒模擬器通常可以用來直接判定被證明斷言的真偽，這表明被證明斷言本身就是平凡的。
Goldreich和Krawczyk [GK, SIAMCOMP 96]證明了不存在針對非平凡斷言的3-輪黑盒零知識證明（這說明Feige-Shamir協議是輪數最優的黑盒零知識證明協議），也不存在針對非平凡斷言的（任意）常數輪公開擲幣（public-coin）的黑盒零知識證明，這裡公開擲幣指的是每個來自誠實驗證者的訊息都是透過隨機擲幣生成的真隨機數，如上面的圖同構協議。公開擲幣的協議通常有著更為廣泛的應用。
分散式環境下的併發性：巢狀難題與遞迴的Feige-Shamir模擬器
在網際網路這種非同步的分散式環境下，一個協議可能被成千上萬的彼此都不知道對方存在的使用者在執行。Dwork，Naor和Sahai[DNS, STOC 98]針對這種環境定義了併發零知識這一概念。在這一定義中，一個惡意的V*被允許控制許多個獨立的驗證者，每個驗證者與一個獨立的誠實證明者互動執行一次協議，但所有的這些協議的執行進度被V*統一控制和排程。併發零知識性就是指協議在這種環境下被併發執行時，對任意的惡意併發驗證者V*，存在模擬器S能夠輸出一個與真實併發互動中V*的檢視不可區分的副本。
前面提到的Feige-Shamir協議在這種環境下被併發多次執行時，它的零知識性受到了巨大的挑戰。模擬器在重置每個會話（即，協議的單次執行）的第一階段時，這一重置動作會導致後續已經解決了的會話（即，模擬器拿到了該會話中某個y的一個原像）作廢，需要透過進一步重置來解決它。這就是所謂的巢狀效應（nest effect）。
在上圖中，一個黑盒模擬器將在第n個會話的第三步時第一次嘗試重置V*至這個會話第二步時的狀態，進而期望得到一個新的第一階段3-輪子協議副本來抽取某個y的原像。注意到第n個會話完全巢狀在第n-1個會話的第二步和第三步之間，所以當模擬器去重置第n-1個會話修改第二步的訊息時，整個第n個會話都受到影響，需要進一步重置才能成功模擬，這將最終導致模擬器需要指數時間才能完成模擬。
這一模擬器時間呈指數膨脹的問題在隨後的一年被Richardson和Kilian解決了。他們提出的構造——Richardson-Kilian協議——本質上就是一個帶有多個slot（一個slot對模擬器而言可以看成一個重置的機會）的Feige-Shamir協議[6]：
注意到對於上述協議，我們稱第一階段的單個3-輪子協議[7]為一個重置機會（slot）。模擬器這時有了k個重置的機會，只要在第一階段k個3-輪子協議中透過重置驗證者成功抽取到一個原像，它便可以模擬整個會話Richardson和Kilian開發了一種非常聰明的遞迴模擬方法。
在模擬中，模擬器遞迴地「look-ahead」策略，看看當前會話第一階段的當前3-輪子協議中第二個訊息和第三個訊息之間是否覆蓋「太多」的新的會話（即，在這之間出現了很多會話的初始階段出現了），如果是，則放棄重置當前3-輪子協議；如果不是，則重置當前子協議來獲取一個原像。如果k比較大，這一模擬器執行時間則為多項式，因為對於單個會話不可能所有k都覆蓋「太多」的新會話。
隨後的Kilian和Rosen等人先後[KP, STOC 01; PRS, FOCS 02]改進了這個遞迴模擬器，最終上述協議中k值為安全引數的對數級別時模擬器的執行時間可以保證在多項式時間內。幾乎同一時間，Canetti[CKPR, STOC 01]等人也證明，如果想取得併發的黑盒零知識，k至少為安全引數的對數級，這表明Rosen等人的併發黑盒零知識協議在輪數上是最優的。
Hada-Tanaka與Barak: 利用計算路徑突破黑盒下界
每次在講到Barak的突破之前，我總習慣性地提到Hada，他在2000年左右在零知識和程式混淆方面都做出了非常具有啟發性的工作。這些工作都不幸地被淹沒在後面更大的突破當中而被忽略了（至少從引用上來看是這樣），我個人覺得並沒有得到他應得的credit。
Hada和Tanaka在1998年發表了一篇3-輪零知識協議構造的文章[HT，Crypto 98]，這看起來直接與上面提到的不存在3-輪黑盒零知識這一下界衝突。
從目前的一些資訊來看，Hada-Tanaka應該在當時（尤其在魏茨曼）引起了較大的反響。Barak在隨後的一年跟隨Goldreich念博士，應該也受到了Hada和Tanaka的想法的影響和啟發，兩年後誕生了一個巨大的突破。我這裡說的啟發是比較廣義的啟發，它並不見得是技術技巧上的影響與啟發，有時它可能是一個單位元的啟發。當大家都擁擠在一條路上躊躇不前時，如果有個oracle告訴你「還有另一條路」，雖然它沒有指出路在哪裡，但這個單位元資訊會強烈刺激一些人去找。這是我為什麼認為儘管Hada-Tanaka的構造建立在一個不可證偽的假設之上，它仍是一個非常具有啟發性的構造。
Barak在2001[Barak, FOCS 01]取得的一個突破性的構造就是基於標準假設的常數輪公開擲幣的零知識協議，它同時還可以具有有界的併發安全性。此外，他的構造對應的模擬器是嚴格多項式時間的。這同時突破了之前有關黑盒零知識的幾個下界。從外形上看，它基本上遵循了Feige-Shamir框架：在協議的第一階段，證明者P與驗證者V共同產生一個困難問題例項；在第二階段，P向V證明「給定的斷言x是正確的 或 我知道第一階段產生的問題例項的答案」。在上面的Feige-Shamir協議裡，第一階段的困難問題例項由V獨自生成，然後V向P證明它知道這一問題例項的答案。這一階段通常需要保證兩點：
· 真實世界中的P無法獲取該問題例項的答案
· 模擬器在擁有驗證者完整程式碼（包括它使用的隨機數）的情況下能夠抽取到該例項的答案。
Barak協議的第一階段也需要滿足這兩點。與Feige-Shamir不同的是，Barak協議的第一階段是公開擲幣的，即驗證者傳送的訊息都是隨機數。這是Barak協議最令人驚訝的地方。
看起來完成了第一階段的設計，但這裡還存在一些問題。首先我們需要指定k的具體值和r的長度。對於後者，設定r的長度為安全引數n的線性或某個固定的多項式(在考慮協議併發執行時需要適當拉長)都可以。
Barak（和Goldreich）利用Babai，Levin，Fortnow和Szegedy在1991年提出的PCP機制（後來被 Kilian 和 Micali 等人應用到密碼領域），構造了一個證據不可區分的普適論證系統（witness indistinguishable universal argument,WIUA）。
由底層PCP的可以scale down的特性，這一協議可以用來證明NP之外的一般性斷言，同時具有一個優異的性質：證明者的執行時間不依賴於上面定義的集合r，而只依賴於集合中具體的例項(h，c， r)。如果被承諾在c中的程式Π的具體執行時間為某個特定的多項式，那麼模擬器（在獲得該例項的證據情況下）執行WIUA對這個例項進行證明所需的時間為這個特定程式N（即，惡意驗證者的程式碼）具體執行時間的一個多項式。
根據這些改動，給定一個NP斷言「x是正確的」，Barak協議的最終版本如下：
如果在併發環境中可以預先固定Barak協議被執行的次數，我們可以讓誠實驗證者選擇一個充分長的r來實現這種有界的併發零知識性。但取得完全的併發安全性，我們需要重複第一階段多項式次，這極大地增加了輪複雜度；或者，如果底層的PCP證明可以變得更短更輕（或假設存在這樣的PCP），我們或許不用增加輪複雜度來取得完全的併發安全性。是否存在在標準的假設下針對非平凡NP語言的完全併發零知識協議目前還不清楚。
理論研究往往充滿了意外。PCP定理的誕生於對互動證明的研究之中，後來它給予了密碼學巨大的回饋。我們可以透過遞迴呼叫PCP機制，將Barak協議改造成為一個具有可重置（resettable）的零知識協議；Micali基於PCP構造的cs proof在威力強大的可抽取單向函式構造上扮演了關鍵的角色；此外，PCP證明以及它的遞迴版本也間接或直接影響了今天非互動簡潔零知識證明的構造。
程式碼，它所計算的函式以及結構
當年看到Barak協議後便有了遞迴呼叫模擬器（本質上是遞迴呼叫PCP）來取得併發安全性的想法。雖然不久便發現這一幼稚的想法受制於PCP的長度和計算時間，遞迴深度非常受限而無法成功，但幾年後還是利用了它（和一些其他的工具）構造一個輪複雜度非常高的可重置的零知識協議。
這一構造比較複雜，2009年投完稿我才慢慢從許多技術細節的泥沼中恢復過來。後面有一段完全放空的時間，開始糾結於一個簡單問題：為什麼每次新的模擬/歸約技術（雖然在某些方面取得了進展）都會帶來更為複雜的構造？對於一些密碼學早期的經典而簡單密碼構造，如Schnorr身份認證和上面的Feige-Shamir協議等，當考慮它們是否具有後來定義的（更強的）安全性--如證據隱藏性，併發零知識性--時，你會發現一個非常混亂現狀：
· 好訊息（the good）：沒有發現有效的攻擊；
· 壞訊息（the bad）: 沒有找到安全性證明；
· 難以解讀的訊息（the ugly）：已經證明「目前的黑盒歸約無法證明它們的安全性」
這一現狀翻譯過來就是：我們無法排除 "將來能夠找到新的歸約方法來證明它們的安全性" 這一可能。這些觀察使我漸漸意識到了目前已知的歸約/模擬方法與證明安全性所要求的歸約/模擬之間的巨大鴻溝：
在字面上，個體化歸約的強大之處在於，給定的敵手A對於歸約/模擬演算法而言是完全透明的：它的程式碼，所使用的隨機數，程式碼所計算的函式（functionality） 以及這一函式可能具有的結構/特徵（如果有比較短的描述的話）等等，都可以被一個存在性的歸約/模擬演算法利用，或者，我們可以直接假定這些特徵/結構資訊被直接嵌入（hardwired）到了存在性的歸約演算法中。這是普適歸約/模擬所無法做到的，因為單個普適歸約/模擬演算法需要應付所有可能的敵手，它被給定的只有敵手的程式碼，而一個多項式時間的演算法是沒有辦法從（可能被混淆的）敵手程式碼中解構出有意義的（即使存在）特徵或結構的，它最多隻能觀察程式碼的一些計算路徑。
因此，即使一個給定的敵手程式碼所計算的函式非常簡單和具有特定的結構，普適歸約/模擬演算法也只能透過觀察它的輸入輸出（如黑盒歸約）或它的具體計算路徑（如Barak的非黑盒歸約）來進行歸約/模擬。
Canetti等人在證明併發零知識輪複雜性下界時所構造的一個惡意驗證者V∗就是一個很好的例子：如果將這一惡意驗證者V∗看成黑盒，那麼模擬器無法模擬V∗的檢視；如果知道V∗的具體計算結構和隨機帶，那麼一個個體化的模擬器很容易模擬它的檢視。如果我們從一個密碼歸約的觀點去看待1978年Adleman的「BPP屬於P/poly」的證明，這也是一個歸約演算法利用「敵手」 隨機帶結構的很好的例子。
實現個體化歸約看起來第一步就需要去證明對任意一個成功攻擊給定密碼構造的敵手都（在合理的假設下）具有某種很好的「結構」。這當然無比困難。在我腦子裡有限的幾個例子中，對於其中一些我們似乎可以取得雙贏：如果敵手演算法有很好的結構，我們固然可以對它進行歸約/模擬；如果沒有的話，我們似乎也有另一種更為簡單的策略對它進行歸約/模擬。
當時腦子裡從CPA到CCA的構造就屬於這一種，但這一切都非常抽象而模糊不清。當年去UCL時，Jens Groth給我的第一個題目就是從單位元CCA安全的加密構造多位元CCA安全的加密，不巧（幸運？）的是討論沒幾天後，這個題目便出現在當年FOCS09接受論文列表裡了。後來我給他講了一下我腦子裡有關CPA到CCA構造的模糊想法，當然，那時候不可能給他講清楚我自己都不理解的東西。
現在想起來有些後悔的是在接下來的幾年幾乎很少去讀文章了。如果那時候接觸到CDS（conditional disclosure of secrets）或者認真琢磨一下那些需要很強假設的證據加密（witness encryption）的話，或許會更早啟發我寫一些東西。
直到7年後，才對Feige-Shamir協議的併發安全性和個體化歸約有了稍微清晰一點的認識，獲得一個win-win的結果：要麼Feige-Shamir協議具有併發安全性，要麼可以將公鑰加密建立在抽象的單向函式上（即，Impagliazzo[I, CCC95]的第四個世界Minicryp不存在）。注意到無論是Feige-Shamir協議的併發零知識性，還是建立在抽象單向函式上的公鑰加密，都已被證明在黑盒歸約下是不可能實現的。這表明確實存在著能夠突破黑盒下界的新歸約方法。
依賴區分器的歸約/模擬
在通常的模擬安全性定義中，我們要對任意的敵手，存在一個模擬器使得對任何多項式時間區分器都無法區分真實世界與模擬世界。
2017年Jain等人[BPK,Eurocrypt 17]提出了一個區分器依賴的模擬方法，他們本質上是將模擬器和區分器前面的量詞調換了：如果先給定一個區分器，那麼我們可以構造一個模擬器（將此區分器作為子程式呼叫）使得預先給定的區分器無法區分它的輸出與真實的互動。依賴區分器的模擬方法本質上依然是黑盒模擬：所有的子程式都被模擬器當成黑盒來呼叫。
在這種模擬方式下，他們給出了3-輪弱零知識構造（下面我們籠統地稱為區分器依賴的零知識證明）。兩年後Bitansky等人[BPK, STOC19]利用這個依賴區分器模擬的想法，引入了同態模擬的技術，對Jain等人構造的3-輪弱零知識證明有了非常大的改進。雖然[BPK, STOC 19]中的構造仍然不是一個正常定義下（模擬仍需依賴具體的區分器）的零知識證明，這也是目前標準假設下的最好的構造了。
[BPK, STOC 19]中的同態模擬非常巧妙和複雜，在這裡我們不打算來詳細介紹它，但仍有兩方面值得注意：
Chung，Lui和Pass[CLP,TCC13]證明了這種區分器依賴的模擬器可以提升到只依賴區分器執行時間的模擬器（允許某個很小的區分優勢），這離標準定義下的零知識更近了一步。
如果一個零知識帶有一個依賴區分器的模擬器（即使仍存在某個很小的區分優勢），那麼該零知識協議通常會是標準定義下證據隱藏的。在我看來，Jain等人和Bitansky等人一個很大的貢獻就是實現了標準定義下的3-輪證據隱藏協議，在他們結果之前，針對一般NP斷言的3-輪證據隱藏協議很多時候被認為和3-輪零知識協議一樣難以實現。
個體化歸約/模擬
在寫上面提到的有關Feige-Shamir協議併發安全性結果的同時，一個偶然的機會我注意到了基於整數分解的Rabin加密的一個優良性質，感覺可以用它來實現個體化歸約，構造一個非常簡單的3-輪弱零知識協議。但寫作和投稿出人意外的漫長，期間收到了一些有趣和有益的評論，也被發現了一些錯誤，結果也幾經改動。
這個想法的核心相對比較簡單，但對於某些要求合成環境下安全的協議（如選擇開啟安全的承諾，併發零知識證明等），它在具體實現上（參見[Deng,Asiacrypt 20]）要比下面的描述稍微複雜一點。
個體化（幾乎最優）抽取器
考慮一個濃縮的2-輪協議（A,B），其中第一輪訊息中B向A傳送一個NP困難問題例項y，並且這個協議具有如下兩個性質：
個體化抽取器/模擬器：依賴B的結構？
上面的抽取器（和模擬器）均依賴具體敵手演算法B的結構。這裡我們給出兩個例子。假設y是某個單向置換的像。如果演算法B僅僅利用它自身的隨機帶來隨機選擇一個像，那麼對應的最優抽取器可以是一個垃圾演算法（因為單向性，所以不存在好的抽取原像的演算法，這個垃圾演算法也是最優了）。
如果B利用它自身的隨機帶來隨機選擇一個原像，然後透過該原像來計算它對應的像y，那麼對應的最優抽取器可以直接利用B的隨機帶來計算y對應的原像，它的成功概率就是1，所以是最優的抽取演算法。這兩個例子可以看出抽取器對演算法B結構上的依賴。
我們還不知道能否利用個體化模擬/歸約獲得更好的安全性和更好的構造。期待未來能看到更多有趣的想法。
參考
[3]注意到 Feige-Shamir 協議是一個論證系統 （argument, 具有隻能抵抗多項式惡意證明者的可靠性）。我們同樣可以構造常數輪零知識證明（proof, 具有可以抵抗任意惡意證明者的可靠性）系統。
[4] 這裡準確的斷言為“存在 b 和 x_b, 使得 y_b=f(x_b)”。由於 3-輪證據不可區分協議通常具有知識的證明性質，這裡我們可以將此斷言寫成上面這種形式。
[5] The Role of Relativization in Complexity Theory，以及 Relativizing versus Nonrelativizing Techniques: The Role of Local Checkability。
[6] RK 協議原始版本是一個證明系統，而非這裡所描述的論證系統。
[7] 實際上為兩輪訊息，第一輪放到了初始階段。
[8] 這一過程並非構造性的。
[9] 目前我們發現也可以基於另外一下標準假設，如 LWE
