現(xiàn)代密碼學(xué)導(dǎo)論-19-基于偽隨機(jī)函數(shù)的CPA安全-創(chuàng)新互聯(lián)

10年專注成都網(wǎng)站制作，成都企業(yè)網(wǎng)站建設(shè)，個人網(wǎng)站制作服務(wù)，為大家分享網(wǎng)站制作知識、方案，網(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)頁制作,對成都人造霧等多個領(lǐ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是一個偽隨機(jī)函數(shù)，則定義一個對于明文長度為 n 的私鑰加密方案如下：

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

THEOREM 3.29?方案3.28是CPA安全的

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

THEOREM 3.29?的證明

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

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

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

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

Distinguisher D：

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

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

重點(diǎn)如下：

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

因此，得到A式

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

因此，得到B式

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

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

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

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

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

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

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

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

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

但是，A最多只能對預(yù)言機(jī)查詢q(n)次，因此，A最多獲得q(n)個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)是可忽略的

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

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

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

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

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

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

當(dāng)前題目：現(xiàn)代密碼學(xué)導(dǎo)論-19-基于偽隨機(jī)函數(shù)的CPA安全-創(chuàng)新互聯(lián)
文章地址：http://muchs.cn/article2/eicic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、面包屑導(dǎo)航、營銷型網(wǎng)站建設(shè)、軟件開發(fā)、自適應(yīng)網(wǎng)站、虛擬主機(jī)

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容