斯坦福Dan Boneh密碼學(xué)——02 計算密碼與語義安全

語義安全這塊內(nèi)容實在是被書繞暈了，雖然模型就那么一個，但有各種各樣的數(shù)學(xué)符號交織證明，還有官方深奧的語言表述。第一次看是一知半解的，后面勢必還要再返回來精讀幾遍完善筆記。以篇幅來看，語義安全是密碼學(xué)中非常重要的一個版塊。

計算密碼與語義安全

我們還是希望能夠使用短密鑰加密長消息。圍繞香農(nóng)定理的唯一方法是放寬我們的安全要求。我們這樣做的方式不是考慮所有可能的對手，而是只考慮計算上可行的對手，即“真實世界”的對手，他們必須使用合理的時間和內(nèi)存在真實計算機上執(zhí)行計算。這將導(dǎo)致稱為語義安全的安全性定義減弱。

計算密碼的定義

計算密碼本身是一對有效的算法E和D。加密算法E將密鑰k和消息m作為輸入，并將密文c作為輸出。其實類似于香農(nóng)密碼，只是其密鑰位于某個有限密鑰空間k中，消息位于有限消息空間m中，密文位于有限密文空間c中。我們將允許加密函數(shù)E是一種概率算法，這意味著對于固定輸入k和m，E（k，m）的輸出可能是多個值之一。

這表示一個執(zhí)行E（k，m）并將輸出分配給程序變量c的過程。雖然可以允許解密算法具有概率性，但我們不需要這樣做，因此只討論具有確定性解密算法的密碼。然而，有時允許解密算法返回一個特殊的拒絕值（不同于所有消息）會很方便，這表明解密過程中發(fā)生了某種錯誤。在一般情況下，我們可以更正式地聲明正確性要求：

確定性密碼與香農(nóng)密碼

一次性密碼、可變長度一次性密碼和附加一次性密碼都是確定性密碼。如果字母∑不太大，那么替換密碼也是如此。任何確定性密碼都是香農(nóng)密碼；然而，計算密碼不必是香農(nóng)密碼（如果它有概率加密算法），香農(nóng)加密不必是計算密碼（如果其加密或解密操作沒有有效的實現(xiàn)）。

語義安全

在完美安全性公式中，我們對于密文空間上的所有謂詞φ，以及所有消息m₀、m₁，都有以下定義：

上述式子中k是均勻分布在密鑰空間k上的隨機變量。現(xiàn)在我們做出一些改變，不再堅持k的取值概率相等，我們只要求它們非常接近；也就是說：

這里的 $$?$$ 當(dāng)然可以取一些非常小或可以忽略不計的值。它的意義在于，我們不要求完美安全的式子對每一個可能的φ、m₀和m₁都成立，雖然并非完全安全，但我們可能愿意說，該密碼在所有實際用途上都是安全的。

要了解語義安全，首先可以從理解完美保密性和實際保密性的概念入手。我們都知道，加密算法中有三個必備的東西：被加密的消息m，加密密鑰k，以及加密算法對(E, D)。我們首先來定義一下什么叫做加密算法的完美保密性：

這個定義的意思是，對于任意等長的消息m，只要這個m屬于消息空間（就是說用這個加密算法可以加密m），那么用加密密鑰k加密后，加密結(jié)果“看起來都一樣”，沒法看出來這是從m，還是從其他什么消息加密得來的。密碼學(xué)中證明了，唯一能達(dá)到這個安全條件的加密算法是一次性密碼，其問題在于加密時使用的密鑰長度至少要跟消息長度一樣才行。

上面這個定義說的是加密結(jié)果讓誰看，“看起來都一樣”，這完美得太完美了?，F(xiàn)在我們稍作變動，選一個迄今為止計算能力最強的人來看加密的結(jié)果，要是他都覺得“看起來都一樣”。那就足夠了！到現(xiàn)在為止，計算能力最強的就是計算機了。這樣的話就引出了實際保密性：

與上面相比，就一個符號改變了，就是等號變成了約等于號。

那么如何用計算機的計算能力來描述實際保密性呢？

我們用兩個計算機來定義。一個計算機是來攻擊這個加密算法的，叫攻擊者（Adversary）；一個計算機是運行這個加密算法的，接受攻擊者的攻擊挑戰(zhàn)，叫挑戰(zhàn)者（Challenger），挑戰(zhàn)者拿著密鑰k，攻擊者的目的就是看看挑戰(zhàn)者運行加密算法后，輸出的加密結(jié)果是不是“看起來一樣”。我們定義兩個實驗：實驗0，實驗1。

實驗0：

1. 攻擊者自己任意選擇兩個消息m₀、m₁（注意，這個m₀、m₁是攻擊者自己選的）
2. 攻擊者把這兩個消息發(fā)送給挑戰(zhàn)者。
3. 挑戰(zhàn)者運行加密算法，加密m₀，把加密結(jié)果發(fā)送給攻擊者。

實驗1：

1. 攻擊者自己任意選擇兩個消息m₀、m₁（注意，這個m₀、m₁是攻擊者自己選的）
2. 攻擊者把這兩個消息發(fā)送給挑戰(zhàn)者。
3. 挑戰(zhàn)者運行加密算法，加密m₁，把加密結(jié)果發(fā)送給攻擊者。

攻擊者的目的呢？就是看到加密結(jié)果后，猜這個加密結(jié)果是由m₀加密來的，還是由m₁加密來的。這兩個實驗唯一的區(qū)別就是，挑戰(zhàn)者是返回m₀的加密結(jié)果，還是返回m₁的加密結(jié)果。而且，執(zhí)行哪個實驗是挑戰(zhàn)者說了算！好啦，現(xiàn)在我們把這兩個實驗合起來：

實驗b：

1. 攻擊者自己任意選擇兩個消息m₀、m₁（注意，這個m₀、m₁是攻擊者自己選的）
2. 攻擊者把這兩個消息發(fā)送給挑戰(zhàn)者。
3. 挑戰(zhàn)者運行加密算法，加密m_b，把加密結(jié)果發(fā)送給攻擊者。

如果挑戰(zhàn)者以$$\frac{1}{2}$$的概率執(zhí)行實驗0，以$$\frac{1}{2}$$的概率執(zhí)行實驗1。那么，如果加密結(jié)果真的沒辦法反映出原始消息的一點點信息，那么攻擊者判斷正確的概率是多少呢？也應(yīng)該是$$\frac{1}{2}$$，因為加密結(jié)果沒法幫助到他，所以他也只能隨便猜，猜對了就撞大運了。

語義安全的定義泛化

某些特定的安全屬性(稱為“X”)，對于某些密碼系統(tǒng)(稱為“S”)可以定義為一個包含兩個實驗的攻擊博弈，實驗0和實驗1，其中對手A的協(xié)議在兩個實驗中是相同的，而挑戰(zhàn)者的協(xié)議是不同的。對于b = 0,1，我們定義W_b為A在實驗b中輸出1的事件，我們定義：

成為A的" X優(yōu)勢"如上所述，我們總是可以定義一個攻擊博弈的“猜位”版本，挑戰(zhàn)者隨機選擇b∈{0,1}，然后運行實驗b作為其協(xié)議。如果W是對手的輸出等于b的事件，那么我們定義：

成為A的“猜位X優(yōu)勢”。我們還可以得出：

上面這條公式是根據(jù)以下過程例證出來的:

設(shè)p₀為攻擊博弈實驗0中對手輸出1的概率，設(shè)p₁為對手輸出1的概率。如果我們以b = 0的事件為條件，那么在這個條件概率空間中，挑戰(zhàn)者和對手所做的所有其他隨機選擇的分布方式與實驗0的對應(yīng)值完全相同。因此，如果在攻擊游戲中，對手的輸出是b，我們有:

依次可以得到等號左右的兩倍關(guān)系。

可忽略函數(shù)

一個函數(shù)f：Z_≥1→R被稱為可忽略函數(shù)，如果對于所有的c∈R>0，存在n₀∈Z_≥1，使得對于所有的整數(shù)n≥n₀，我們有|f(n)|<1/n^c。

定理：函數(shù) f：Z_≥1→R 可忽略當(dāng)且僅當(dāng)對于所有的c > 0，我們有：

比如說有這些函數(shù)，2^-n，n^-logn，它們都是可忽略函數(shù)。

超聚函數(shù)

函數(shù) f：Z_≥1→R 如果 1/f 可以忽略，則稱為超聚函數(shù)。

多有界函數(shù)

函數(shù) f:：Z_≥1→R 稱為多有界函數(shù)，如果存在c, d∈R>0，使得對于所有n≥0的整數(shù)，我們有|f(n)|≤n^c + d。

注意，如果f是一個多界函數(shù)，那么1/f肯定不是一個可以忽略的函數(shù)。例如，定義f: Z_≥1→R，使f(n)對于所有偶整數(shù)n = 1/n, f(n)對于所有奇整數(shù)n = 2^?n，則f不可忽略，且1/f既非聚有界也非超聚。

計算密碼的規(guī)范

我們說計算密碼 $$?$$ =（E，D）是在（K，M，C）上定義的，其中K是密鑰空間，M是消息空間，C是密文空間，而這些空間中的每一個都是有限集，我們并沒有說出全部真相。在數(shù)學(xué)模型中（雖然在實際系統(tǒng)中并不總是如此），我們將密鑰、消息和密文空間的E族關(guān)聯(lián)起來，索引方式為：

（1）一個安全參數(shù)，它是一個正整數(shù)，用λ表示

（2）一個系統(tǒng)參數(shù)，它是位串，用∧表示

因此，我們有了有限集族，而不僅僅是有限集K、M和C。

出于這個定義的目的，我們將其視為一組位字符串（它可以通過一些規(guī)范的編碼函數(shù)來表示數(shù)學(xué)對象）。其思想是，當(dāng)部署密碼 $$?$$ 時，安全參數(shù)λ固定為某個值。一般來說，λ值越大，意味著安全級別越高（即對擁有更多計算資源的對手的抵抗力），但密鑰大小也越大，加密和解密速度也越慢。因此，安全參數(shù)就像我們可以轉(zhuǎn)動的“撥號盤”，在安全性和效率之間進行權(quán)衡。一旦選擇λ，系統(tǒng)參數(shù)∧將使用特定于密碼的算法生成。

這一個固定實例可以部署在一個更大的系統(tǒng)中，并由多方使用—— λ 和 ∧ 的值是公開的，并且為所有人（包括對手）所知。

用一個例子來理解計算密碼的規(guī)范，附加一次性密碼，該密碼是以模n來描述的。為了部署這樣的密碼，會生成一個合適的模n，并將其公開。模n是該密碼的系統(tǒng)參數(shù)。安全參數(shù)的每個特定值決定n的長度（以位為單位）。值n本身由一些可能是概率的算法生成，其輸出分布可能取決于預(yù)期應(yīng)用。

計算密碼由一對算法E和D以及三個具有系統(tǒng)參數(shù)化P的空間族組成：
文章來源地址http://www.zghlxwxcb.cn/news/detail-477613.html

到了這里，關(guān)于斯坦福Dan Boneh密碼學(xué)——02 計算密碼與語義安全的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！