密鑰協(xié)議和安全計(jì)算的交互

1、密鑰協(xié)議和安全計(jì)算的交互摘要通過互動的公共通信通道，我們分析了多方的相關(guān)數(shù)據(jù)，仔細(xì)研究了信息理論密鑰（SK）和安全函數(shù)計(jì)算。我們主要的研究是SK的長度上限，通過綜合多方SK協(xié)議減少二元假設(shè)測算推測來得出。建立在這個基本結(jié)果之上，我們得到了新的SK協(xié)議的認(rèn)識。此外，將無視傳輸協(xié)議和某些承諾協(xié)議與SK協(xié)議相關(guān)聯(lián)，我們得到了交互的結(jié)果。最后，得到了受信方集體數(shù)據(jù)函數(shù)可行性安全計(jì)算的必要條件，那就是使用一個本身不會泄露價(jià)值功能的交互式的大眾媒體傳播。在很多情況下，我們加強(qiáng)和改善先前已知的交互界定，得到的結(jié)果是單發(fā)的并且只是用給定的相關(guān)觀測的聯(lián)合分布。對于這個例子，當(dāng)相關(guān)的觀察值由獨(dú)立分布序列組成時，我

2、們獲得了更精確的的先前版本的交互。關(guān)鍵詞假設(shè)測算，密鑰協(xié)議，安全雙方計(jì)算，單發(fā)交互。1.介紹信息理論的密碼學(xué)與相關(guān)的隨機(jī)觀察各方的實(shí)用性有關(guān)。如果同行者的觀察是相互獨(dú)立的，那么多方密鑰（SK）和安全計(jì)算是可行的。事實(shí)上，SK協(xié)議并不可行，即使是觀察一些獨(dú)立分區(qū)。作為對這一原則的一個擴(kuò)展，我們可以預(yù)計(jì)，加密原語與“多遠(yuǎn)”觀察是一個聯(lián)合分布，呈現(xiàn)出觀察獨(dú)立性（在某些分區(qū)組內(nèi)）。我們形式化這一啟發(fā)式原則，利用它限定使用相關(guān)資源的效率來實(shí)現(xiàn)SK協(xié)議和安全計(jì)算。我們報(bào)告了單發(fā)交互結(jié)果，特別的，我們不認(rèn)為當(dāng)事人的觀察結(jié)果是由一個長的獨(dú)立同分布（IID）隨機(jī)過程序列所組成。在多方SK協(xié)議中，觀察相關(guān)隨機(jī)變量

3、（RSV）的同行者尋求達(dá)成共享隨機(jī)比特并隱藏訪問相關(guān)信息的偷聽者。同行者可以在一個無聲的公共頻道內(nèi)相互交流，但是傳送的通信將可能被偷聽。推導(dǎo)我們交互結(jié)果的主要工具是減少SK協(xié)議二次假設(shè)測算的內(nèi)容。對我們的主要思想進(jìn)行一下說明，考慮一個雙方的例子。當(dāng)偷聽者僅僅觀察合法雙方之間的通信而不觀察任何額外的信息時，很顯然，如果合法方的觀察是獨(dú)立的，那么SK就不能生成。根據(jù)“多遠(yuǎn)”所生成的SK長度上界是觀察方的聯(lián)合分布，通過分布呈現(xiàn)他們觀察的獨(dú)立性。具體的說，對于這個特殊的情況，我們得出SK的最大長度s的上界是鑒于型誤差的概率小于，當(dāng)測試的零假設(shè)代替時，是型的最優(yōu)概率誤差。這個代表和之間的距離。同樣，在一

4、般情況下對于任意數(shù)量的相關(guān)方信息的偷聽者，我們在定理3中的結(jié)果依據(jù)觀察方聯(lián)合分布之間的距離界定了密鑰長度，當(dāng)條件為偷聽者的信息時，當(dāng)事人的預(yù)測條件就獨(dú)立成一些分區(qū)。這個界定是對上述啟發(fā)式原理的顯示，被稱為約束條件獨(dú)立測試。我們所運(yùn)用的的方法將SK協(xié)議與二次假設(shè)測算進(jìn)行了結(jié)構(gòu)連接。這個方法在參考文獻(xiàn)52中有所體現(xiàn)，對信道編碼和二次假設(shè)測算進(jìn)行連接是用來建立一個擁有極佳上限的信道碼率。當(dāng)然，我們的上界讓人想起了在參考文獻(xiàn)74中提到的纏結(jié)量子態(tài)的測量，即國家的密度矩陣之間的最小距離及其分狀態(tài)。纏結(jié)的措施在參考文獻(xiàn)74中被證明是一個上限蒸餾的纏結(jié)，其中后者是最大比例的最大纏結(jié)態(tài)，可以使用精華蒸餾過程。

5、使用我們的基本結(jié)果，我們得到新的SK協(xié)議。同時，為了確保雙方的安全計(jì)算，可以減少SK的無視傳輸協(xié)議和承諾協(xié)議。在許多情況下，我們加強(qiáng)和改善先前已知的結(jié)果，將我們主要的貢獻(xiàn)總結(jié)如下。A. 密鑰協(xié)議對同行者來說，SK密鑰協(xié)議相關(guān)的觀察問題是較好的研究。這一問題是由Maurer、Ahlswede和Csiszar引入，他們考慮到了一個例子：同行者去觀察IID序列。但是在某些應(yīng)用程序中，考慮由相關(guān)RVS實(shí)現(xiàn)結(jié)果所引起的觀察值是很有趣的。例如，在生物識別等應(yīng)用程序和硬件驗(yàn)證方面，對包括生物的不同版本和硬件簽名的相關(guān)觀察分別進(jìn)行了記錄登記和分階段驗(yàn)證。為此，Renner和Wolf推導(dǎo)出了SK的長度上限，它由

6、雙方觀察一個單一的RVS時通過單面溝通所產(chǎn)生。對于IID設(shè)置來說，多方SK協(xié)議的問題在參考文獻(xiàn)16中進(jìn)行了解釋。在本次研究中，我們通過觀察一個單一的RVS考慮了多方SK協(xié)議問題。我們的條件獨(dú)立測試界定是一個單發(fā)的SKs長度上限，可以由多方使用公共交流互動觀察相關(guān)數(shù)據(jù)所產(chǎn)生。與在參考文獻(xiàn)60中僅限制與單向通信方通信不同，我們允許任意多方的互動交流。我們的漸進(jìn)界限是緊密的，其在IID中的應(yīng)用可以恢復(fù)一些之前所知的SK率漸進(jìn)界限。事實(shí)上，我們加強(qiáng)了先前已知的漸進(jìn)結(jié)果，因?yàn)槲覀儾槐乜紤]SK協(xié)議或保密漸進(jìn)指數(shù)中的錯誤。（參見第四節(jié)詳細(xì)討論）B. 雙方的安全計(jì)算雙方的安全計(jì)算問題在參考文獻(xiàn)83中進(jìn)行了介紹

7、，雙方尋找一個可以不必知道雙方數(shù)據(jù)就可以計(jì)算出他們的集體數(shù)據(jù)的函數(shù)。對這個普遍問題進(jìn)行了幾個實(shí)例研究。我們考慮了轉(zhuǎn)移（OT）和承諾（BC）這兩個問題，他們是構(gòu)成雙方安全計(jì)算的基礎(chǔ)元素。OT是雙方之間信息傳輸模式“發(fā)送方不知道收件人是否收到信息”。在這篇文章中，我們考慮到了二分之一的OT問題：第一方觀察兩個字符串K0、K1的長度，第二方尋求Bth串的值。對于這個問題我們需要用一種使B和均隱含的方式完成，簡單說這個問題就是安全函數(shù)計(jì)算的核心。任何安全函數(shù)計(jì)算任務(wù)可以反復(fù)使用基本協(xié)議完成。不巧的是，信息理論安全OT在沒有額外的資源時是不可行的。值得慶幸的是，如果雙方共享一個嘈雜的通信通道或者如果他們

8、注意到了相關(guān)的隨機(jī)性，OT就可以完成。在本文中，我們考慮了后者情況，作為額外的資源，雙方遵守相關(guān)的和?；跍p少OTSK協(xié)議的相關(guān)參數(shù)，我們所得到的OT的上界長度可以完成給定的，?？偟膩碚f，由此獲得的界限比在參考文獻(xiàn)79里的更嚴(yán)格。此外，我們綁定到應(yīng)用程序IID的觀測表明OT長度的上界在參考文獻(xiàn)2、48中很大?，F(xiàn)在讓我們看看BC問題。其中第一個實(shí)例介紹了Blum在7中所提到的電話拋硬幣問題，這是在雙方互不信任的情況下發(fā)生的。有些承諾協(xié)議分為兩個階段。在第一階段提交方生成一個隨機(jī)比特串K“拋硬幣”。隨后，雙方互相溝通，第一階段結(jié)束。在第二階段，提交方揭示K。承諾協(xié)議必須禁止提交方欺騙或者在第二階段

9、改變K。在OT這個例子中，信息理論安全BC沒有額外的資源是不可能的。我們考慮這樣一個版本，雙方使用公共交互通信觀察x1,x2，從而實(shí)現(xiàn)信息安全。目標(biāo)是最大化所提交的字符串K的長度。通過降低SK對BC的協(xié)議，我們獲得了一個BC長度的上限。另外，在IID觀測的情況下，我們得到了一個強(qiáng)大的BC能力的交互，后者是BC長度的最大值。C. 受信方的安全計(jì)算在不同的方向，我們在下面的安全問題函數(shù)計(jì)算中進(jìn)行敘述（一個早期的版本，看50）：觀察相關(guān)數(shù)據(jù)的多方，尋求一個可以計(jì)算他們集體數(shù)據(jù)的函數(shù)。為此，他們通過公共通信信道交互溝通，這被認(rèn)為是身份驗(yàn)證和零錯誤。這個要求函數(shù)值對訪問交流的偷聽者是隱藏的。那么這樣一個

10、給定函數(shù)的安全計(jì)算什么時候是可行的呢？相比上面所討論的傳統(tǒng)的安全計(jì)算問題，這個設(shè)置更適合于一下應(yīng)用，例如：傳感網(wǎng)絡(luò)，合法方是被信任的并且可以通過共享信道自由提取任何相關(guān)方的信息。通過使用有條件的獨(dú)立測試綁定，我們獲得了存在一個通信協(xié)議的必要條件，允許當(dāng)事人可靠的恢復(fù)一個給定函數(shù)的值，同時保持這個值對訪問的偷聽者是隱蔽的。在參考文獻(xiàn)69,匹配了安全計(jì)算性的必要和充要條件的情況下推導(dǎo)出了給定函數(shù)的IID觀察值。相比之下，我們的安全計(jì)算性的必要條件是單發(fā)，不依賴于IID觀察值。D. 文件輪廓下一部分介紹一下在研究中使用到的基本概念，條件獨(dú)立測試邊界在第三部分導(dǎo)出。在隨后的三個部分中，我們提出了這個界

11、限的隱意：第四部分詳細(xì)介紹了SK的能力；第五部分描述了OT和BC問題的結(jié)果；第六部分描述了受信方安全計(jì)算問題的結(jié)果；最后一部分簡短的討論了可能的擴(kuò)展。E. 符號為了簡便起見，我們使用縮寫SK，RV，IID分別表示密鑰，隨機(jī)變量，獨(dú)立同分布；復(fù)數(shù)形式通過加s來實(shí)現(xiàn)。RVs用大寫字母表示，相應(yīng)的區(qū)間集用書法字母表示。RVU的分布規(guī)律是由PU給出的，當(dāng)不會混淆時我們標(biāo)注了下標(biāo)U。當(dāng)事人的集合1,.,.,m由M標(biāo)識。作為RVs集U1，.,Um和M的子集A，UA用來表示RVsUi，iA。Un表示nIID 就是RVU的重復(fù)次數(shù)。Pn表示由P所生成的nIID重復(fù)次數(shù)的分布。文中出現(xiàn)的所以對數(shù)參見基礎(chǔ)2。.導(dǎo)

12、論A. 密鑰考慮使用互動的公共通信SK協(xié)議m，第i個當(dāng)事人觀察在一個有限集Xi,1<i<m,上的RV離散。通過這些觀察，雙方在通過公共通信通道交互溝通時可以被偷聽者介入，而且還能另外觀察像RVs（XM，Z）這樣的RVZ。我們假設(shè)溝通無誤，并且各方從其他方接受溝通。另外，我們假設(shè)公共通信可以進(jìn)行驗(yàn)證且偷聽者無法篡改它。具體來說，通信循環(huán)交互發(fā)送r。在第j個循環(huán)交互中，1<j<r,第i個當(dāng)事人發(fā)送Fij(觀察值Xi，局部隨機(jī)生成的Ui,先前觀察的通信之間的函數(shù)) 整體的互動溝通F11，.,Fm1,.,F1r,.,Fmr是由F分配的。使用局部的觀察和交互溝通，雙方達(dá)成一致的S

13、K。通常，SK是RVsK1，.,Km的集合，第i個當(dāng)事人給定Ki,同意率接近1并且對偷聽者隱藏。第i個當(dāng)事人計(jì)算函數(shù)Ki(Ui,Xi,F)，如果滿足下面兩個條件，RVs K1,.,Km在給定一個K時就構(gòu)成了一個范圍（，）-SK：Punif是K的均勻分布，d(P,Q)是P和Q之間變化的距離，由下式得出： 上面第一個條件是可靠的恢復(fù)SK，第二個條件是保密。在這項(xiàng)工作中，我們使用以下的式子來替代SK的定義，方便的結(jié)合了可恢復(fù)性和保密條件：如果滿足(3)上述的RVs K1,.,km組成了擁有常數(shù)范圍K的-SK：事實(shí)上，上述的這兩個定義聯(lián)系很密切。命題1：給定0<,<1,如果KM在（1）式下

14、組成（，）-SK，那么它在（3）式下組成（+）-SK。相反的，如果KM在（3）式下組成-SK，那么它在（1）和（2）式下組成（，）-SK。因此，通過組合在8中的定理，復(fù)雜的加密協(xié)議使用這樣的SKs代替原始的SKs是安全的。我們對描述-SK中l(wèi)og|K|的最大長度很感興趣。定義1：給定0<<1,在給定常數(shù)范圍K時，由表示-SK的log|K|的最大長度。我們的上界是基于有關(guān)SK協(xié)議問題的二次假設(shè)檢測問題，下面我們將回顧一些在假設(shè)檢測中會用到的基本概念。B假設(shè)檢測考慮一個二次零假設(shè)檢測問題P和對立假設(shè)Q，P和Q分布在相同的字母表X中。觀察一個值xX,觀察者需要決定生成的值是否為分布P或Q

15、。為此，觀察者應(yīng)用隨機(jī)測試，測試的一個條件分布在0,1給定的觀察值是xX。當(dāng)xX是觀察值時，測試T選擇零假設(shè)的概率是T（0|x），對立假設(shè)的概率是T（1|x）=1-T(0|x)。對于0<<1, 與型中由（P,Q）表示的最大下界相比，型的誤差概率小于，我們記錄了量（P,Q）的兩個重要屬性。1） 數(shù)據(jù)處理不均：令W為從X到Y(jié)的隨機(jī)映射，對于每一個xX,W(.|x)在Y中都有一個分布。然后 2） Stein的引理：對于每一個0<<1,都有D（P|Q）是kl散度，公式如下：我們約定： C（P,Q）評定方法的備注我們討論一下（P,Q）評定方法。注意，（P,Q）在（4）中的表示是一

16、種線型規(guī)劃，用于解決觀測空間規(guī)模的多項(xiàng)式復(fù)雜性。一個簡易的操作生成了更容易計(jì)算的范圍：當(dāng)P和Q符合IID RVs時，在（7）中的尾數(shù)概率可以直接進(jìn)行數(shù)值計(jì)算或者可以用Berry-Esseen定理近似近似計(jì)算得出。另一方面，當(dāng)P和Q符合馬爾科夫鏈時，可以進(jìn)行尾數(shù)概率的數(shù)值計(jì)算。對于這種情況，在（P,Q）中的易于計(jì)算和漸進(jìn)約束的綁定在77中可以建立。同時，通過設(shè)置的當(dāng)>1時Resyi的散列值可以得出，式子在61中給出下面是所獲得的（P,Q）的簡單界定：對于量子觀察中的變種界定在49,Th,1中進(jìn)行了記錄。一個典型的例子，界定必須遵從簡單的證據(jù)，如下：由Ay表示的集合x:logP(x)/Q(x

17、)<y。因此，對于>1,進(jìn)一步暗示了。（8）受（7）的影響，一般來說，當(dāng)（8）的界定不是很小時，它的推論是遵循Stein的定理的。 最后，我們總結(jié)當(dāng)條件成立時，P下1的可能性是滿足的，這一界定在（7）中有顯示給定兩個RVs X和Y，保密信息理論的核心問題是：有多少無偏獨(dú)立位可以從X中獲得？IID底層分布時，最佳的提取比特率可以依據(jù)香農(nóng)熵和給定的H(X|Y)表示。然而，對于我們的單發(fā)設(shè)置，在5860中引入的光滑的最小熵是一個相關(guān)的隨機(jī)測量，依據(jù)其他變化的綜述。我們也回顧剩下的散列理論，解決一下在上面所提出的光滑的核心最小熵的問題。同時，對于改變最小熵的測量手冊，我們定義了光滑最大散度

18、它滿足不均的數(shù)據(jù)處理。定義2：P的最小熵被定義為：對于Pxy和Qy的分布，Pxy的最小熵為Qy提供的條件如下：最后，Pxy的最小熵為Y給定的條件如下：來自最大散度Dmax(PQ)的等式是正的，并且當(dāng)且僅當(dāng)P=Q是，等式為0.條件最小熵的替代形式是在41被第一次提出，首次提出了最一般的量子設(shè)置并顯示了Hmin(PXY|Y)相對于-log的推測X,Y的平均可能性的條件。然而，11中的最初的形式更適合我們的目的。最小熵的定義和最小熵的條件在所有低能的，非負(fù)函數(shù)Pxy都是可行的 Pxy如下：我們需要這個擴(kuò)展和平滑的概念為接下來的定義提供更嚴(yán)謹(jǐn)?shù)慕缍?。定義3：給定的>0,Y一定時，-smooth對

19、應(yīng)的Pxy的條件最小熵被定義為：當(dāng)Y時恒定的，-soomth的最小熵由來表示?，F(xiàn)在我們陳述剩余的散列引理，就是從中提取出的隱藏Y的獨(dú)立的X。引理2：給定一個聯(lián)合分布Pxy,對于每一個0<2<1,0<,存在一個映射K： 。 最后，我們回顧光滑最大散列，其在18中作為量子設(shè)置被引入。接下來定義的平滑方法余18的略有不同，但是是適合我們的目的的。定義4：P和Q之間的最大散列被定義為在的條件下，0<<1, P和Q之間的最大散列被定義為接下來將被使用的兩個平滑最大散列屬性是：1） 不均數(shù)據(jù)處理：對于每一個隨機(jī)映射W: 只要 2） kl散度的收斂：對于IID分配的Pn和Qn,

20、如果不等條件是不存在的。因此，這足以證明一點(diǎn)，在假定條件下D（P|Q）是限定的。為了這個目的，考慮。對于一個序列和xX的元素，通過N(x|x)來表示x在x里的發(fā)生次數(shù)。然后每一個序列滿足注意對于足夠大，因此，在假設(shè)時，最后一個不等式來自（14）.對于其他方向的不等式，如果我們給定一個并且 那么， 對于所有的n都足夠大，這進(jìn)一步的表明，存在一個 實(shí)現(xiàn)的確，如果不這樣的話，那么對于所有的與在（15）中進(jìn)一步顯示的是相矛盾的。因此，對于例子這里存在，使得，因?yàn)?，所以上述等式的右邊也是無窮的。另一方面，如果D(P|Q)是限定的，使用（14），對于序列上述等式的右邊是有界的。.有條件的獨(dú)立測試本文的交互

21、結(jié)果是基于最大長度S的，在這里我們展示一下這個結(jié)果?？紤]M中的一個集合劃分，如果底層分布的觀測值PXMZ四條件獨(dú)立的跨分區(qū)Z，那么SK的長度可以生成為0。我們的方法就是限制SK的生成長度，依據(jù)“多遠(yuǎn)”是來自另一個分區(qū)的分區(qū)PXMZ呈現(xiàn)XM，兩個分區(qū)的親密度是測量得到的。特別的，對于一個劃分，讓成為所有劃分的一部分，因式分解如下：定理3：給定0<<1,0<<1-,M的一個劃分對于所有的備注1：Renner和Wolf得到了一個對于SK長度的界定，可以由使用同一交互通道的雙發(fā)產(chǎn)生。這個界定在定理3中的對比是不可能實(shí)現(xiàn)的，因?yàn)榍罢甙o助的RVs并且很難評估。備注2：對于m=2

22、,Z=常數(shù)，SK長度的下界在定理3中與Polyanskiy的meta-converse緊密相關(guān)。此外，信息M進(jìn)行點(diǎn)對點(diǎn)通信，代碼的可靠傳輸產(chǎn)生一個發(fā)送者和接受者；SK的長度可以由定理3來界定。然而，結(jié)果略低于meta-converse，在最優(yōu)規(guī)模傳播代碼64中不產(chǎn)生三階漸進(jìn)詞。備注3：下面的定理3的證據(jù)仍然是有效的，即使是用一般的條件去取代保密條件 ： 我們證明定理3的潛在關(guān)鍵理念是一個的下限，對于擁有觀察空間KM的二次假設(shè)檢測，零假設(shè)P給出了：對立假設(shè)Q給出了：即，測試的問題是K1，.,Km是否構(gòu)成了完美的相關(guān)統(tǒng)一隨機(jī)性和他們是不是互相獨(dú)立的。引理4：對于在（18）（19）中的和，對于所有的

23、0<<i都有證明：考慮對數(shù)似然比的極限，給出測試可以進(jìn)行的可行范圍對于這個測試，型的錯誤率界定如下另一方面，型錯誤率如下，只要組成KM的元素滿足第二個等式就成立。內(nèi)部和可被進(jìn)一步的展示如下上述第一個等式成立時,第二個等式成立時遵循Holder的不等原則。綜合（21）（22）得出因此我們有一個型錯誤率小于的測試，型的錯誤率在（20）中有所展示，因此，。證明結(jié)束。在（18）中的PKM對應(yīng)于一個被m個同行者分享的完美的密鑰，接下來的結(jié)果擴(kuò)展了引理4,中的關(guān)鍵值KM、F通道、被觀察的偷聽者的編帶信息Z和對應(yīng)于SK-M的零假設(shè)PKMZ。引理5：對于每一個0<<1-,每一個都有 對

24、于聯(lián)合分布 是 的臨界，并且是對應(yīng)的臨界。當(dāng)然我們需要下述68交互通信的基本特性來貫穿整篇文章。引理6：給定一個和交互式通信F，得到如下式子：所以在交互通信附加條件獨(dú)立的觀察結(jié)果仍然成立。特別的，如果那么引理5的證明：證明簡單的修改了引理4。首先記錄引理6，是F確定的函數(shù)，這里有。因此，引理4在Q作用下有分布對于每個，對于每個（f,z）有，形如： 我們考慮如下的測試，對于一個二次假設(shè)檢測問題，有零假設(shè)和替代假設(shè)：對于一個觀察者，如果且有其他的替換我們接受零假設(shè)。使用公式（24）型的錯誤性計(jì)算如下：通過（25）型的錯誤性計(jì)算如下：。 最后，我們利用零假設(shè)、替代假設(shè)進(jìn)行試驗(yàn)考慮了假設(shè)檢測問題。顯然

25、，型錯誤率不變。另外，在（3）所考慮的安全條件下，型的錯誤率在不超過時將增加，這一點(diǎn)已經(jīng)得到了證明。 定理3的證明：我們首先考慮在每一個元素中的劃分，對于1<i<m,對于這個例子，由定理5和不等式（5）數(shù)據(jù)處理產(chǎn)生：并且。對于每一個1<<1-,有擴(kuò)展（26）得到一個劃分，我們聲明，當(dāng)?shù)豬個同行者觀察時（1<i<）,一個-sk的原始模型與m方都會產(chǎn)生一個與-sk長度相同的模型?，F(xiàn)在只需要證明上述聲明。為此，對于原始的模型給定一個-sk我們給-sk定義一個新模型，如下：在原始的模型中任何一個在溝通時生成的KM，雙方運(yùn)行協(xié)議。對于在新模型中的每個同行者i，我們選擇

26、一個代表；具體地說，讓i0成為中最小的部分。在新模型中一個當(dāng)時給定，由如下分布表示單調(diào)性證明如下：證明完畢。.密鑰容量的隱喻對于SK協(xié)議問題，一個感興趣的特殊的例子當(dāng)觀察者組成的長度為n的IID系列，第i個觀察者和像RVs的偷聽者是IID。對于這個例子，可知能生成SK對n的長度比例；SK利率的最大值被稱為SK容量。為了展示這一部分的總長度，我們需要借助于在（1）（2）中給出的的原始定義。定義1的方式表示了的最大長度。它來自于命題1。定義5：給定0<,<1,容量如下定義：當(dāng)是IID并且1<t<n,有同分布，SK容量的極限定義如下：對于這個例子，當(dāng)偷聽者沒有觀察到任何邊界信

27、息時Z=常數(shù)，雙方的SK容量由Maurer、Ahlswede和Csiszar給出。之后，當(dāng)Z=常量，SK容量在多方模型中由Csiszar和Narayan給出。SK容量的很多下界在116172644中給出。在這一部分，我們得到了雙方SK容量的單射版本，這是在這個例子中最容易理解的。另外，對于多方同行者，我們建立了一個SK容量的強(qiáng)交互，但我們并不能通過降低恢復(fù)能力需求或者安全需求提高SK比率。A 雙方交互的結(jié)果在26中顯示了在26里的假設(shè)依賴于是IID這一結(jié)論，并且不能應(yīng)用于單射設(shè)置。下述的結(jié)果是27的單射版本，SKs進(jìn)行了證明。定理7：對于0<,+2<1,對于每一個RV U都有通過推

28、論，我們得出了一個單射的版本并在27中擴(kuò)展了下界，不需要最合適的漸進(jìn)恢復(fù)機(jī)漸進(jìn)安全性。推理8：對于0<,推論9：對于0<,引理10：令（K1，K2）在中取然后，對于每一個RV U，0<<1-2,有定理7的證明：讓（K1，K2）在中取然后通過引理10和在（13）里的最大散度的數(shù)據(jù)處理，我們得到：通過剩余的散列引理，這里存在一個的映像在中得到的，滿足因此，構(gòu)成了X1，X2的，當(dāng)偷聽者觀察（Z，U）時推論8由定理3得出。推論9的證明：推論8的結(jié)果應(yīng)用了Stein的引理,遵循最大散列的收斂性。定理10的證明：通過定義和足以顯示對于每一個映像T：0,1時，這里存在一個非負(fù)函數(shù)和一

29、個分布滿足如下條件由給出，因?yàn)樗赃@是個有效的非負(fù)函數(shù)。另外，因?yàn)槲覀兊玫搅耍?9）的公式如下：第一個不等式是三角不等式，最后一個不等式根據(jù)安全條件（2）和假設(shè)（28）得到。接下來將定義如下：得到：B 多方同行者的強(qiáng)交互當(dāng)偷聽者得不到邊界信息時，我們分析一下m的終端例子。通過化簡，SK對于多方的容量由Csiszar和Narayan給出。另外，在等式右側(cè)進(jìn)行了顯示的表達(dá)，展示了當(dāng)m=2,3時它的緊密度。最后，對于任意的m的緊密度在10中進(jìn)行解釋；我們將所得的結(jié)果總結(jié)如下。定理11：SK容量的例子，當(dāng)偷聽者的邊界信息Z=常數(shù)時得到，其中最小值是M的所有劃分。這個由Maurer、Ahlswede和C

30、siszar提出的普遍的結(jié)果是建立于兩個同行者之間的。定理11的交互部分依賴于當(dāng)時。下面我們加強(qiáng)這個交互并將將SK率的下界在定理11中進(jìn)行表述。特別的，對于，Z=常數(shù)，一個定理3對IID的應(yīng)用是，因此使用Stein的引理我們得到如果SK率是無窮的。實(shí)際上，考慮一個，此時RV生成一個K1并且通過公共交互通道將它發(fā)送給其他的同行者。因?yàn)镵是隨意的，所以的長度結(jié)果是隨意大的。因此，我們建立了如下的當(dāng)Z=常數(shù)時，SK容量的強(qiáng)交互。推理12：給定容量給定如下：.雙方安全計(jì)算的影響這一部分我們考慮雙方的安全計(jì)算，在過去的三十年這個問題推進(jìn)了密碼學(xué)的研究。特殊的我們要考慮一下不經(jīng)意的傳輸和一部分委托問題，這

31、是安全計(jì)算雙方的基本單元。我們分析一下理論上的闡述：作為一個額外的資源，同行雙方觀察相關(guān)的和我們得出的逆命題是基于還原與SK有關(guān)的參數(shù)，并應(yīng)用于了定理3。A. 常見函數(shù)最大值和充分統(tǒng)計(jì)量最小值B. 為了陳述我們的結(jié)果，我們需要常見函數(shù)最大值和充分統(tǒng)計(jì)量最小值的概念。常見函數(shù)最大值的概念在24中通過用隨機(jī)變量X1和X2對常見函數(shù)進(jìn)行測試進(jìn)行了介紹。它對于安全的作用在82中有所強(qiáng)調(diào)。操作上對常見函數(shù)的X1和X2的最大值定義如下。定義6：當(dāng)存在函數(shù)和時（例如），一個常見函數(shù)X1和X2是隨機(jī)變量U。常見函數(shù)X1和X2的最大值，通過進(jìn)行表示。事實(shí)上，Gacs和Korner提出了提出其有如下的等式關(guān)系：充

32、分統(tǒng)計(jì)數(shù)最小值的作用在82做了強(qiáng)調(diào)。定義7：X1給定的充分統(tǒng)計(jì)數(shù)X2是如下的一個隨機(jī)變量U，存在一個函數(shù)U=g(X1)使得馬爾科夫鏈成立，X1給定的最小充分統(tǒng)計(jì)數(shù)X2是每一個充分統(tǒng)計(jì)數(shù)U的一個函數(shù)。對于的精確的特征是存在的，并且遵循如下的等價(jià)關(guān)系;C 不經(jīng)意傳輸假如同行者1生成可K0和K1，均勻的分布在同行者2生成B，均勻的分布在0,1，作為OT協(xié)議的輸出。假定和B是互相獨(dú)立的，OT協(xié)議的目的是讓同行者2實(shí)現(xiàn)KB。另外，同行者i在i=1,2時實(shí)現(xiàn)。在協(xié)議中，同行者可以互相交流。通常，同行者可以使用當(dāng)?shù)氐碾S機(jī)取樣；為了簡單起見，沒有當(dāng)?shù)仉S機(jī)取樣時就阻止協(xié)議進(jìn)行。然而，如備注6所寫，當(dāng)當(dāng)?shù)仉S機(jī)取樣

33、允許時，我們的結(jié)果依然有效。定義8：實(shí)現(xiàn)的協(xié)議組成了交互通信F，同行者2的估計(jì)值滿足一下條件：當(dāng)?shù)诙⑷齻€條件對于同行者1,2安全時，上述第一個條件表示了OT的可靠性。表示了l的長度。 當(dāng)潛在的觀察者X1，X2組成IID的長度系列時，可得的線型關(guān)系n。稱最大增長率為OT容量。 定義9：對于，的容量定義如下：然后，OT容量定義如下：本節(jié)的主要結(jié)果是一個上限。因此，我們恢復(fù)由和提出的上限。事實(shí)上，我們表明，上限是無窮的，并應(yīng)用于，當(dāng)觀察雙方相關(guān)時，OT是可行的。但是，任何一方都不應(yīng)該有超越他人的有點(diǎn)，以及只有一部分當(dāng)事人遵守相關(guān)的隨機(jī)性是有用的，不能由另一方來決定。借鑒此啟發(fā)式，對OT長度進(jìn)行兩種

34、界限是可能的，基于OT長度的聯(lián)合分布所觀察到的相關(guān)隨機(jī)性PX1X2是一個沒用的分配，無用分布的選擇是兩個不同的范圍。對于第一個界限，我們考慮一個分布：使得X1和X2獨(dú)立給出。對于這樣的分布，一旦每個共享知識同行者分解出來就沒有相關(guān)性O(shè)T了。在第二界限，我們認(rèn)為V1 = MSS（X2 | X1）可以通過X2來確定。注意，對于這種分布因式分解成立時，這樣的分布是無用的，因?yàn)镺T的本質(zhì)是由X2決定的。作為SK協(xié)議的情況，我們將使用測量兩個分布之間的距離。事實(shí)上，我們通過減少SK協(xié)議來證明OT，對于這兩個界限的消減是不同的。定理13：對于RVs和下列不等式成立:對于所有的有推理14：對于0<&l

35、t;1, (X1, X2)的容量OT滿足：，。定理13的證明意味著要減少SK協(xié)議，（37）的界限是通過獲得回收的KB作為SK，而（38）是由回收得到KB作為SK；我們注意到這兩個反應(yīng)作為單獨(dú)的引理如下：引理15：考慮到雙方遵守X1和X2的SK協(xié)議，分別與竊聽者觀察。給定一個協(xié)議，存在一個用于產(chǎn)生一個協(xié)議長度L的。引理16：考慮到雙方SK協(xié)議，其中同行者1觀察X1，同行者2觀察(V1, X2) = (mss(X2|X1), X2)和所述的竊聽者X2。給定一個實(shí)現(xiàn)長度為L的，存在用于生成長度為L的協(xié)議。備注4：底層的證明是對OT的協(xié)議的縮減，這是我們證明的延長，下面證明（）。相反，邊界的證明依賴于

36、條款。下面我們舉一個替代減少的論據(jù)證明（38）。備注5：在一般情況下，我們的界限比在79中提出的要大。例如，當(dāng)觀察者由IIDRVs的最大值組成時后者是松散的。此外，雖然（38）和（79）兩者足以獲得在推論14的結(jié)論，但是相反，（37）和79不能產(chǎn)生第一個推論14的約束。備注6：為了表述的簡單起見，我們不容許進(jìn)行隨機(jī)的配方。然而，它可以很容易的包括到X1和X2中。由于我們的證明是基于減少SK協(xié)議的OT，經(jīng)指出，mss(X2,U2|X1,U1) =mss(X2|X1)，隨機(jī)性的可用性是不會代表我們對SK長的上限界定的，上述結(jié)果仍然有效，即使隨機(jī)性可用。備注7：容量可以限定，而不需要 去作為C(X1

37、, X2)。然而，右側(cè)（39）構(gòu)成一個上限，只有當(dāng)，建立這種約束的有效性。我們證明引理15和16如下，數(shù)據(jù)處理不等式（5）；推理如下斯坦因引理。引理15：設(shè)K作為KB的估計(jì)方2，下列協(xié)議生成。（1） 甲方1生成兩個隨機(jī)字符串K0和K1，甲方2生成隨機(jī)比特B。雙方運(yùn)行OT協(xié)議，甲方獲得KB的K個估計(jì)。（2） 甲方2通過公共頻道發(fā)送B。（3） 使用B，甲方計(jì)算KB。 我們將證明所述的RVsKB，其中組成了。此SK的可靠性是有保障的，因?yàn)殡p方對KB的同意概率大于。為了建立保密制度，注意，如果同行者2向B發(fā)送，竊聽者不能確定KB。另一方面，由同行者2在整體保密狀態(tài)下觀察同行者1的(K0, K1, X1

38、, F)會得到和B一樣的分布。因此，相同的分布偷聽者不能從(B, F)來確定KB。 形式上，由命題1和3注釋的，只需要證明分布。引理16的證明：以下協(xié)議產(chǎn)生了一個長度為L的。（1） 同行者1生成兩個隨機(jī)字符K0和K1，長度為L,同行者2生成隨機(jī)比特B，兩方運(yùn)行OT協(xié)議。（2） 根據(jù)觀察者F，同行者2生成根據(jù)的采樣。（3） 同行者2通過公共頻道發(fā)送B。（4） 同行者1計(jì)算KB，同行者2計(jì)算。我們將證明所述的，組成了。這個協(xié)議用同行者仿真了，同行者1不需要關(guān)心B的價(jià)值，用控制會導(dǎo)致KB的估計(jì)值保留聯(lián)合分布。 由命題1和（35），它足以說明：其中不等式使用（40），最后一個不等式使用Markov的關(guān)

39、系。D 比特委托雙方遵循相關(guān)意見X1和X2，使用公共交互通信來實(shí)現(xiàn)信息安全理論BC。第一方一個報(bào)道，用于報(bào)告第二方的一系列結(jié)果。在以后的現(xiàn)階段，通行者1可以檢測同行者2。從形式上看，BC協(xié)議組成了兩個階段：提交階段和揭示階段。在提交階段，同行者1生成一個隨機(jī)串K，超過0, 1的L分布和均勻分布(X1, X2)。此外，雙方相互使用交互式交互通信F。在揭示階段，同行者1透漏了數(shù)據(jù)，即，它發(fā)送了和，聲稱這些是它的和的最初的選擇。隨后，同行者2適用于一個隨機(jī) 測試功能，這里的，和。定義10：一個長度為L的實(shí)現(xiàn)的執(zhí)行協(xié)議組成的交互交流F，在交流階段被發(fā)送，值隨機(jī)的測試函數(shù)T在揭示階段使用，這時得滿足以下

40、條件：對于RVs K和X1任何選擇，X1具有相同范圍集K和X1，滿足：。上述的第一條件是一個可靠的狀態(tài)，當(dāng)同行者1可信時，BC是可信的，下一個狀態(tài)是隱藏態(tài)。最后，結(jié)合（44）中的條件限制，同行者1可以在揭示階段作弊。通過記錄的最大L，使得協(xié)議實(shí)現(xiàn)長度為L的。對于長度為n的IID序列生成，的最大比率被稱為BC容量。定義11：對于，對于的容量定義如下：BC容量定義如下：。Winter等人的結(jié)果如下，給出對于C(X1, X2)的簡單公式。定理17：對于RVs X1, X2,讓V1 = mss(X2|X1)，BC容量給定如下：。在本節(jié)中，我們提出了一個上限，這又導(dǎo)致了一個更大的BC容量。定理18:給定

41、對于和，得到下列不等式：對于，。推論19：對于0<,滿足：，。定理19是由減少SK協(xié)議獲得的BC，下面的引理得到了相應(yīng)的約束。引理20:對于，滿足，。備注8：當(dāng)隨機(jī)性不允許前面的討論時，如之前，我們的結(jié)果不與當(dāng)?shù)氐碾S機(jī)性的改變而改變。備注9：對于，下列的界定在56中推導(dǎo)得出：然而這種界定比定理18要牽強(qiáng)，在一般情況下，對于推論19是不充分的。如定理18所示，隨著Markov關(guān)系X1V1X2和數(shù)據(jù)不等式（5），下面我們證明引理20。引理20的證明：給定一個長度為L的，考慮經(jīng)雙方觀察X1和(V1, X2)的SK協(xié)議。為了生成一個SK，各方運(yùn)行BC協(xié)議的提交階段，即，同行者1生成，并發(fā)送F的交

42、互通信。我們展示了組成的交流密鑰K。事實(shí)上，隱藏條件（43），對滿足的保密條件（2）。從而，同行者2可以找到唯一獲得的K的估計(jì)值字符串，它是與（V1，X2，F(xiàn)）兼容的。通常，會有這樣的一個證明，存在，使最后，對于隨機(jī)測試T，讓，給定的函數(shù) 讓。對于上述的，給出：，第一個不等式使用了定義，第二個不等式使用了Markov的關(guān)系，上述不等式要滿足以下條件：我們通過觀察一個簡單的應(yīng)用程序結(jié)束本節(jié)。對于一個詳細(xì)的討論56。例1：假設(shè)雙方有一個長度為n的OT，以此作為一個資源，怎樣建立一個長度為l的結(jié)構(gòu)呢？由K0，K1指示的OT的串，并通過B的OT位表示同行者2。讓和。需要注意的是，并且因此，通過定理18

43、和（10），我們可以得到。它顯示了一個遞增的損失然而56顯示了一個增加的線型序列。.安全計(jì)算與可信方的啟示 本節(jié)中，我們提出的安全功能計(jì)算問題的計(jì)算關(guān)系，值得信賴的同行者，如果當(dāng)事人試圖計(jì)算的函數(shù)，其觀察所使用的通訊沒有透露本身的功能的值。這是相對于處理的安全計(jì)算的第部分，其中所講述的通信是安全的，但是同行者被禁止獲得更多的計(jì)算函數(shù)的信息。此問題是在引入69時，被賦予了匹配的充分的條件。在這里，用定理3，我們導(dǎo)出的必要條件，例如：安全的可行性計(jì)算的一般性的意見。 在形式上，考慮在m 2時，同行者觀察RVs X1, . . . , Xm由有限集可得值。在得出這些結(jié)果時，雙方溝通交互可以可靠的計(jì)算一個函數(shù)。在以下的證明中，對于第i個同行者根據(jù)它所觀察函數(shù)的估計(jì)G(i)形成基于函數(shù)的觀察值Xi，局部隨機(jī)化的UI和交互通信F即，。對于，這里存在一個定理，滿足： 第一個條件的捕獲的可靠性計(jì)算和第二條件的保密的協(xié)議。用于保密的F觀察者必須懂得計(jì)算值函數(shù)的功能。我們力求表征計(jì)算函數(shù)g的。 在19,同行者觀察并且尋求計(jì)算值。對于IID的，一個函數(shù)g，在同行者可以組成估計(jì)時是安全計(jì)算，這樣。 定理21：對于漸進(jìn)情況如上述所述，一個函數(shù)g在時是可以安全計(jì)算的，其中，。反正，如果一個函