A.4 一個例子

考慮下面的例子，它是Fiat-Shamir機制[3]的一個簡化方案。這里，我們給定了一個模數n和一個關于模n的數，稱作y。在這個方案中，A的陳述是“我知道y關于模n的一個平方根”。注意到x是y關于模n的一個平方根，當且僅當x2 mod n=y.
A和B之間的會話將如下進行：
重復t次：
1.A隨機選擇r（這里2≤r≤n-1），將其模n平方并發送給B。
2.B隨機選擇比特b 等于0或1，發送給A。
3.如果b等于0那么A發送
z=r

z=rx mod n,

這里x是y關于模n的平方根，這是A所知道的。

z2≡r2(mod n)。

相應的，如果b等于1那么B檢查

    z2≡r2y(mod n)

如果檢查是正確的就繼續，否則B拒絕并且終止程序。

不難看出，如果A和B都遵循上述程序，那么B將不會拒絕A；將z平方意味著把r或　rx平方，那將給出結果r2 mod n或（rx）2=r2x2=r2y mod n。
另一方面，如果在t次迭代的任何一次中，Ａ對于b=0和b=1都能夠提供正確的答案，這就意味著Ａ能夠提供z0和z1 ,使得

　　　　　　　　　　　　　 z0２＝r2 mod n
并且
　　　　　　　　　　　　　 z1２＝r2y mod n。
通過將第一個方程式插入到第二個，可以直接地看出來數z1／z0　mod n是y的一個平方根（z0≠０并且z0必須以極大的概率和n互素）。如果Ａ能夠計算出具有在這樣性質的z１和z0，那么他就能夠計算z1／z0，因此關于他知道y的一個平方根的陳述就是真實的。但是相反地，如果Ａ是在欺騙，他并不知道y的平方根，在t次迭代的每一次中他必定不能正確回答b的至少一個值。因此一個欺騙的聲稱者使驗證者確信的概率至多為2-t。比如重復20次，我們就把這個概率縮小到約百萬分之一。從而也滿足了合理性的要求。至于零知識，注意到驗證者在會話結束之后所留下的是兩個數z和r2，滿足
z2≡r2 (mod n)
或者
z2≡r2y (mod n)
但是這些事情實際上驗證者不用與A會話，自己就可以生成。B只要選擇一個隨機的z，定義
r2= z2 mod n
或者
r2=z2/y mod n。
假如這樣的話，這種計算r2和z的方式不同于聲稱者的計算方式，但是這個事實是無關緊要的；二者的計算結果的分布是完全一樣的，也就是說，不可能分辨其差異。因此，除了得知A知道y的一個平方根這個事實之外，B不能得到任何他自己不能計算的信息。
讓我們在這里預先考慮一個經常會提問到的問題。如果驗證者不掌握y的一個根就能夠自己生成很好的會話，那么為什么當聲稱者產生一個類似會話的時候，驗證者就應該確信他的話呢？答案是當B模擬這個協議的時候，他可以自由地以‘相反的方向’產生數字，也就是說，他首先選擇z然后尋找符合條件的r2。在協議的實際執行中，A沒有這個機會。驗證者期望在選擇b之前看到r2，然后聲稱者必須找到一個正確的z。
盡管我們在這里已經解釋了幾個技術難點，但存在討論的要點：為什么機制具有零知識的特性。