【導讀】數(shù)字簽名與hash函數(shù)。公開密鑰密碼應(yīng)用基礎(chǔ)。零知識證明介紹?雙向認證使通信雙方確認對方的身份。用對稱密碼分發(fā)對稱密鑰。該協(xié)議不能抵抗重放攻擊。每個用戶知道授權(quán)機構(gòu)的公鑰。雙方的身份證明信息:抵抗假冒。需要預先存在共享密鑰或知道對方的公鑰。在有效時間內(nèi)重放。不能檢測的重放:原始的消息沒有到達。保障時效性的措施。需初始值且要隨機性?該協(xié)議必須有良好的容錯性和安全性。任一方失去時鐘同步,攻擊就可能發(fā)生。時間窗口必須大于網(wǎng)絡(luò)延時。適合于有連接的通信。KDC產(chǎn)生并安全地分發(fā)隨機會話密鑰。攻擊者獲得一個舊Ks即可冒充A實施重放攻擊。Denning的改進:增加時間戳。KDC把B的身份和時間戳,A的nonce以及會

　　

【正文】 很大的概率說服 B接受 “ x?L”的事實 . Institute of Computer Science amp。 Technology, Peking University 72 交互證明系統(tǒng)定義 (2) ?合理性 (Soundness):對每個 k0和充分長的 x?L, 對任意交互圖靈機 A?(未必遵守協(xié)議 ),將 x作為(A?,B)的輸入 ,則 B至多以 |x|k的概率接收 概率指對于協(xié)議 (A?,B)的所有可能的擲硬幣而言 ?本質(zhì)上講 ,合理性是指 ,如果 x?L,那么無論 A采取什么欺騙策略 ,B接受 “ x?L”的概率非常小 . ?完全性 (Completeness)與 合理性 (Soundness)的誤差率均為 |x|k,可以證明 ,該誤差率和常數(shù)誤差率?: 0??1/2以及指數(shù)誤差率 : 2|x|是等價的 . Institute of Computer Science amp。 Technology, Peking University 73 二次非剩余的例子 : 預備信息 ?Zn={0,1,2,… ,n1}, Zn*={y?Zn: gcd(y,n)=1} ?QR={(n,y): n?N,y?Zn*,y是 n的二次剩余 } ?QNR={(n,y): n?N,y?Zn*,y是 n的二次非剩余且(y/n)=1}, 其中 (y/n)是 y模 n的 Jacobi符號 ?QR:二次剩余語言 , QNR:二次非剩余語言 ?(A,B)是一個交互協(xié)議 ,(n,y)是其公共輸入 , m是 n的二進制長度 (|x|) ?目的 : A向 B證明 (n,y)?QNR. ?開始時 B先檢查是否 : n?1, y?Zn*以及 (y/n)=不是 ,則停機 。否則執(zhí)行 m次 : Institute of Computer Science amp。 Technology, Peking University 74 二次非剩余的例子 : 協(xié)議步驟 ?B從它的隨機讀入一個位 i(0或 1)和一個整數(shù)r?Zn*(即隨機選取 i和 r,r?Zn*),計算 w=yir2 mod n,將 w寫到其只寫通信帶 (即發(fā)給 A) ?A讀出 w,察看是否 (n,w)?QR,若是 ,置 j=0,否則置j=1,然后將 j寫到其只寫通信帶 (即發(fā)給 B) ?B讀出 j,驗證是否 i=j ?若 m輪都通過 ,則 B接收 A的證明 ,即認為(n,y)?QNR Institute of Computer Science amp。 Technology, Peking University 75 二次非剩余的例子 : 完全性 ?B選 i(0或 1)和 r?Zn*,計算 w=yir2 mod n,將 w給 A ?A讀出 w,察看是否 (n,w)?QR,若是 ,置 j=0,否則置j=1,將 j給 B ?B讀出 j,驗證是否 i=j ?協(xié)議是否具備完全性 ?即如果 A遵守協(xié)議并且具備判斷一對數(shù) (n,w)是否屬于 QR的能力 ,B是否會以很大的概率接收 A的證明結(jié)論 ? A遵守協(xié)議 ,由于 (n,y)?QNR, 當 i=0時 , w=r2 mod n是 n的二次剩余 ,故 j=0。 當 i=1時 , w=yr2 mod n不是 n的二次剩余 ,故 j=1。 總之 i=j,因此 B以概率 1接收 A的證明 Institute of Computer Science amp。 Technology, Peking University 76 二次非剩余的例子 : 合理性 ?B選 i(0或 1)和 r?Zn*,計算 w=yir2 mod n,將 w給 A ?A讀出 w,察看是否 (n,w)?QR,若是 ,置 j=0,否則置j=1,將 j給 B ?B讀出 j,驗證是否 i=j ?協(xié)議是否具備合理性 ?即若 (n,y)?QNR,B是否會以很小的概率接收 A的證明結(jié)論 ? 若 (n,y)?QNR,則 (n,y)?QR 無論 A是否遵守協(xié)議 ,無論 i取 0還是 1,w =yir2 mod n總是 n的二次剩余 ,A無法知道 B選擇的 i是 0還是 1,就只得憑空猜測 .每次 A只有 1/2的概率猜對 ,m次只有 2m=n1的機會猜對 . Institute of Computer Science amp。 Technology, Peking University 77 二次非剩余的例子 :B的計算時間 ?開始時 B檢查是否 : n?1, y?Zn*以及 (y/n)=1. ?B選 i(0或 1)和 r?Zn*,計算 w=yir2 mod n,將 w給 A ?B讀出 j,驗證是否 i=j ?B檢查 n?1 ?y?Zn*的判斷 :Euclidean算法 ,|n|的多項式時間 ?Jacobi符號的計算是否為 |n|的多項式時間 ? ?選擇 r?Zn*的時間 : 只要選擇使得 gcd(r,n)=1的 r ?計算 w=yir2 mod n: |n|的多項式時間 ?B驗證是否 i=j Institute of Computer Science amp。 Technology, Peking University 78 Jacobi符號的計算時間 ?Jacobi符號的性質(zhì) : 若 m,n不互素 ,則 (n/m)=0。 ?二次互反律 : (n/m) = (m/n)(1)(n1)(m1)/4 。 ?若 a ? b mod n,則 (a/n) = (b/n)。 (ab/n) = (a/n)(b/n)。 ?(1/n) = (1)(n1)/2。 (2/n) = (1)(n?n1)/8。 ?Jacobi符號的計算過程 : ?若 gcd(m,n) ? 1,則 (n/m) = 0: ?多項式時間 ?(n/m)=(m/n)(1)(n1)(m1)/4=(m?/n)(1)(n1)(m1)/4 , m?=m mod n。 m ? m?: ?多項式時間 ?若 m是偶數(shù) ,令 m=2km?, m?是奇數(shù) ,則 (m/n)=(2/n)k (m?/n) : ?多項式時間 ?每執(zhí)行兩次 ?,?,類似 Euclidean算法 , max(m,n)至少減小一半 ,最多執(zhí)行 2?ln(max(m,n))次 . Institute of Computer Science amp。 Technology, Peking University 79 隨機變量的不可區(qū)分性和可逼近性 ?語言 L?{0,1}* ?U={U(x):x?L}和 V={V(x):x?L}為兩族隨機變量 ,所有隨機變量都在 {0,1}*中取值 . ?隨著 x長度的增加 ,最終 U(x)與 V(x)可相互 “ 取代 ” ?從 U或 V中隨機抽取一批樣本并交給判決者 ,在研究這些樣本后 ,判決者將做出 0(樣本屬于 U)或1(樣本屬于 V)的判決 .如果隨著 |x|的增加 ,任何判決者都無法準確做出判斷 ,則認為 U和 V可相互取代 (或不可區(qū)分 ) ?根據(jù) 樣本的數(shù)目 和判決者進行 判決所需的時間(計算量 ),可得到不同的不可區(qū)分的類型 . Institute of Computer Science amp。 Technology, Peking University 80 完全和統(tǒng)計不可區(qū)分 ?U與 V完全不可區(qū)分 :對于充分長的 x,對每個??{0,1}*, P(U(x)=?) = P(V(x)=?) ?若兩族隨機變量完全不可區(qū)分 ,則判決者即使有無窮多的樣本 和 無限的計算能力 ,他也無法判斷樣本究竟來自哪一個 . ?U與 V統(tǒng)計不可區(qū)分 :對于任意常數(shù) c0和每個充分長的 x,成立 : ?{|P(U(x)=?)P(V(x)=?)| : ??{0,1}*} |x|c ?若兩族隨機變量統(tǒng)計不可區(qū)分 ,則擁有 多項式個樣本 和 無限計算能力 的判決者也基本無法區(qū)分 ?完全不可區(qū)分 ? 統(tǒng)計不可區(qū)分 Institute of Computer Science amp。 Technology, Peking University 81 計算不可區(qū)分 ?多項式規(guī)模的電路族 :C={Cx:x?L}為一族布爾電路 ,Cx的輸入為 x,輸出僅為 0或 1,且存在常數(shù) k0使得 C中的每個布爾電路至多有 |x|k個門 . ?多項式規(guī)模電路族的計算能力可能強于概率圖靈機 ?多項式界隨機變量族 (U):存在常數(shù) k0使得對于所有隨機變量 U(x)?U只對長度不超過 |x|k的串分配正概率 (即 U(x)的值 :一個串 ,的長度不超過 |x|k) ?P(U,C,x)=按 U(x)分布的隨機串輸入后 Cx輸出 1的概率 ?U與 V計算不可區(qū)分 : U和 V為兩族多項式界隨機變量 ,對于任意常數(shù) c0和每個充分長的 x,成立 : |P(U,C,x)P(V,C,x)| |x|c Institute of Computer Science amp。 Technology, Peking University 82 統(tǒng)計不可區(qū)分與計算不可區(qū)分 ?統(tǒng)計不可區(qū)分 ? 計算不可區(qū)分 ?用 Sx表示使得 Cx輸出為 1的輸入集 ,則 U和 V統(tǒng)計不可區(qū)分表明 ,對于任意常數(shù) c0和每個充分長的x,成立 : ?{|P(U(x)=?)P(V(x)=?)| : ??{0,1}*} |x|c 從而 |P(U(x):x?Sx)P(V(x):x?Sx)| =|?{P(U(x)=?):??Sx}?{P(V(x)=?):??Sx}| ?{?|P(U(x)=?)P(V(x)=?)| : ??Sx} ?{?|P(U(x)=?)P(V(x)=?)| : ??{0,1}*} |x|c 注意到 : P(U,C,x)=P(U(x):x?Sx) P(V,C,x)=P(V(x):x?Sx), 因此 |P(U,C,x)P(V,C,x)| |x|c 即 U和 V在語言 L上是計算不可分的 Institute of Computer Science amp。 Technology, Peking University 83 隨機變量的可逼近性 ?M是一個關(guān)于輸入 x以概率 1停機的概率圖靈機 ,用 M(x)表示一個隨機變量 ,該隨機變量的分布為 :對每個串 ?,P(M(x)=?) = P(M關(guān)于輸入 x輸出 ?). ?語言 L?{0,1}*, U={U(x):x?L}:一族隨機變量 ,稱 U在語言 L上是 完全 可逼近 的 ,如果存在多項式時間的概率圖靈機 M,使得 {U(x):x?L}和 {M(x):x?L}在 L上是 完全不可區(qū)分 的 ?類似可定義 :統(tǒng)計 可逼近 ,計算 可逼近 ?完全可逼近 ? 統(tǒng)計可逼近 ? 計算可逼近 Institute of Computer Science amp。 Technology, Peking University 84 成員的零知識證明定義 (1) ?成員的交互證明系統(tǒng) (A,B)是 A和 B雙方執(zhí)行的一個協(xié)議 ,證明者 A試圖說服驗證者 B相信某個結(jié)論 T(如 x?L)為真 . ?一方面 ,如果 T不為真 (如 x?L),則即使 A不遵守協(xié)議 ,采取任何欺騙策略 ,也無法說服 B相信 T為真 . ?另一方面 ,即使某個驗證者不遵守協(xié)議 ,則他也無法從 A獲得 T為真以外的消息 ?假設(shè) B?是一個交互圖靈機且有額外輸入 :當公共輸入為 x時 ,B?還有額外輸入 H,H的長度不超過 |x|的多項式 (H可能是 B?已經(jīng)擁有的關(guān)于 x的知識 ).假定 A和 B?根據(jù)協(xié)議執(zhí)行了 n步 ,相應(yīng)的隨機子串為 ?和 ?,相應(yīng)的消息為 ai和 bi,B?獲得的全部信息為 : Institute of Computer Science amp。 Technology, Peking University 85 成員的零知識證明定義 (2) ViewA,B?(x,H)=(?,a1,b1,a2,b2,… , an,bn) ?B?的工作帶內(nèi)容可不在其中 ,因為其可在多項式時間內(nèi)獲得 . ?語言 L?{0,1}*,定義語言 L?={(x,H): x?L,H的長度不超過 |x|的多項式 },若隨機變量族 ViewA,B?= {ViewA,B?(x,H): (x,H)?L?}關(guān)于語言 L?是 完全可逼近 的 ,則稱 (A,B)對 B?關(guān)于語言 L?是 完全零知識 的 .如果協(xié)議 (A,B)對所有多項式時間的概率圖靈機 B?都是 完全零知識 的 ,則稱協(xié)議關(guān)于語言 L是 完全零知識協(xié)議 . ?類似可定義 ,統(tǒng)計零知識協(xié)議 ,計算零知識協(xié)議 Institute of Computer Science amp。 Technology, Peking University 86 成員的零知識證明定義 (3) ?語言 L?{0,1}*,(A,B)是一個交互協(xié)議 ,稱 (A,B)對語言 L是一個 成員的完全 (統(tǒng)計 ,計算 )零知識證明系統(tǒng) ,如果 (A,B)對 L是一個成員的交互證明系統(tǒng)并且關(guān)于 L是一個 完全 (統(tǒng)計 ,計算 )零知識協(xié)議 ?通常稱 計算零知識證明系統(tǒng) 為 零知識證明系統(tǒng) ,簡稱 零知識證明 . ?關(guān)于 QNR的成員交互證明系統(tǒng) : B可以通過 A解決他事先不知道或者不能解決的問題 (國際象棋特級大師問題 ): C要