目錄

10年專注成都網(wǎng)站制作，成都企業(yè)網(wǎng)站建設(shè)，個(gè)人網(wǎng)站制作服務(wù)，為大家分享網(wǎng)站制作知識(shí)、方案，網(wǎng)站設(shè)計(jì)流程、步驟,成功服務(wù)上千家企業(yè)。為您提供網(wǎng)站建設(shè),網(wǎng)站制作,網(wǎng)頁設(shè)計(jì)及定制高端網(wǎng)站建設(shè)服務(wù),專注于成都企業(yè)網(wǎng)站建設(shè),高端網(wǎng)頁制作,對(duì)成都人造霧等多個(gè)領(lǐng)域，擁有多年的營(yíng)銷推廣經(jīng)驗(yàn)。

3.5.2?基于偽隨機(jī)函數(shù)的CPA安全

基于偽隨機(jī)函數(shù)的加密示意圖

CONSTRUCTION 3.28 構(gòu)造基于偽隨機(jī)函數(shù)的CPA安全的加密方案

THEOREM 3.29?方案3.28是CPA安全的

THEOREM 3.29?的證明

---

3.5.2?基于偽隨機(jī)函數(shù)的CPA安全 基于偽隨機(jī)函數(shù)的加密示意圖

---

CONSTRUCTION 3.28 構(gòu)造基于偽隨機(jī)函數(shù)的CPA安全的加密方案

設(shè)F是一個(gè)偽隨機(jī)函數(shù)，則定義一個(gè)對(duì)于明文長(zhǎng)度為 n 的私鑰加密方案如下：

Gen：對(duì)于輸入1^n，隨機(jī)均勻選擇 k ∈ {0, 1}^n 并輸出

Enc：對(duì)于輸入的 k ∈ {0, 1}^n以及明文 m ∈ {0, 1}^n，隨機(jī)均勻選擇 r∈{0, 1}^n，然后輸出密文c :=，其中?s=Fk(r)⊕m

Dec：對(duì)于輸入的 k ∈ {0, 1}^n以及密文 c =，輸出明文 m := Fk(r)⊕s

---

THEOREM 3.29?方案3.28是CPA安全的

如果F是一個(gè)偽隨機(jī)函數(shù)，則由方案3.28構(gòu)造的對(duì)于明文長(zhǎng)度為 n 的私鑰加密方案是CPA安全的

---

THEOREM 3.29?的證明

記方案3.28為Π= (Gen, Enc, Dec)

我們?cè)贅?gòu)建一個(gè)新方案。這個(gè)新方案除了用真隨機(jī)函數(shù)代替3.28中的偽隨機(jī)函數(shù)，其他均相同。我們記為

有一個(gè)PPT敵手A，設(shè)q(n)為敵手 A 在安全參數(shù)為n的CPA竊聽實(shí)驗(yàn)中詢問預(yù)言機(jī)的次數(shù)上限，q必須存在某個(gè)多項(xiàng)式的上界。

我們用A來構(gòu)造偽隨機(jī)函數(shù)F的一個(gè)區(qū)分器D。區(qū)分器D的輸入是函數(shù)O的預(yù)言機(jī)，區(qū)分器的目標(biāo)是判斷該預(yù)言機(jī)對(duì)應(yīng)的函數(shù)O是否為偽隨機(jī)函數(shù)

Distinguisher D：

D被給定1^n和預(yù)言機(jī)O，其中O滿足

1. 運(yùn)行A(1^n)，當(dāng)敵手A用消息m∈{0, 1}^n詢問預(yù)言機(jī)時(shí)，D隨機(jī)均勻選擇一個(gè)r∈{0, 1}^n并用r詢問預(yù)言機(jī)，得到結(jié)果y=O(r)，將密文c=計(jì)算并返回給A
2. 當(dāng)A輸出消息m0，m1∈{0,1}^?n時(shí)，D隨機(jī)均勻選擇b∈{0, 1}，并且均勻選擇一個(gè)r∈{0, 1}^n并用r詢問預(yù)言機(jī)，得到結(jié)果y=O(r)，將密文c=計(jì)算并返回給A
3. A仍保持步驟1.中詢問預(yù)言機(jī)的權(quán)利，直到A輸出b’。D獲取敵手A輸出的b'，如果 b = b'，則D輸出 1；否則D輸出0

重點(diǎn)如下：

如果區(qū)分器D的預(yù)言機(jī)對(duì)應(yīng)于偽隨機(jī)函數(shù)，那么當(dāng)A作為D的子程序運(yùn)行時(shí)，以A的視角來看，A就相當(dāng)于在做實(shí)驗(yàn)

因此，得到A式

如果區(qū)分器D的預(yù)言機(jī)對(duì)應(yīng)于真隨機(jī)函數(shù)，那么當(dāng)A作為D的子程序運(yùn)行時(shí)，以A的視角來看，A就相當(dāng)于在做實(shí)驗(yàn)

因此，得到B式

由于F是一個(gè)偽隨機(jī)函數(shù)，根據(jù)偽隨機(jī)函數(shù)的定義，

現(xiàn)代密碼學(xué)導(dǎo)論-17-偽隨機(jī)函數(shù)_南鳶北折的博客-博客

DEFINITION 3.24 偽隨機(jī)函數(shù)的正式定義

存在一個(gè)可以忽略的函數(shù)negl，滿足C式?

聯(lián)立A、B、C式，得到D式

這個(gè)式子的形式非常像EAV-安全的第二個(gè)等價(jià)定義。但是對(duì)于CPA安全，我們還沒有考慮過。

考慮實(shí)驗(yàn)

請(qǐng)注意，每次消息m被加密時(shí)，即詢問預(yù)言機(jī)或當(dāng)挑戰(zhàn)密文被計(jì)算時(shí)，會(huì)隨機(jī)均勻選擇一個(gè)r∈{0, 1}^n，并計(jì)算c=。我們?cè)O(shè)r*表示在生成挑戰(zhàn)密文時(shí)使用的隨機(jī)字符串。有兩種可能性：

1. 如果r*在預(yù)言機(jī)對(duì)A的回答中沒有出現(xiàn)過，由于f是真隨機(jī)函數(shù)，A與預(yù)言機(jī)的交互中不能獲得關(guān)于f(r*)的任何信息，那么A輸出的b'=b的概率就是1/2
2. 如果r*在預(yù)言機(jī)對(duì)A的回答中出現(xiàn)過，也就是說 A 獲取了，那么其可以通過計(jì)算 f(r*)=f(r*)⊕m⊕m 就能得出f(r*)，在得知了 f(r*) 的情況下，A輸出的b'=b的概率就為1

但是，A最多只能對(duì)預(yù)言機(jī)查詢q(n)次，因此，A最多獲得q(n)個(gè)r。由于r*是從{0, 1}^n中隨機(jī)均勻選取的，因此有2^n種可能。那么A獲取的r中包含r*的可能性就為q(n)/(2^n)

把事件“r*?被A捕獲” 記為事件Repeat，則Pr[Repeat] ≤ q(n)/(2^n)

我們得到

將上式帶入D式，得到

由于p(n)是多項(xiàng)式函數(shù)，因此q(n)/(2^n)是可忽略的

我們?cè)O(shè)negl’(n)=q(n)/(2^n)+negl(n)，根據(jù)

現(xiàn)代密碼學(xué)導(dǎo)論-8-計(jì)算安全性_南鳶北折的博客-博客

PROPOSITION 3.6 可忽略函數(shù)的性質(zhì)中的性質(zhì)一

兩個(gè)可忽略函數(shù)的和仍然是可忽略函數(shù)。因此negl’(n)是可忽略函數(shù)，使得

這樣，我們就證明了方案3.28是CPA安全的?

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章標(biāo)題：現(xiàn)代密碼學(xué)導(dǎo)論-19-基于偽隨機(jī)函數(shù)的CPA安全-創(chuàng)新互聯(lián)
網(wǎng)站URL：http://weahome.cn/article/eicic.html