選擇打開攻擊下的公鑰加密方案設(shè)計(jì)及安全性證明.pdf

1、公鑰加密的選擇打開安全性（securityagainst selective opening attacks，簡記為SOA安全性）是由Bellare，Hofheinz和Yilek在會議Eurocrypt2009上正式定義的，主要是考慮多用戶環(huán)境中數(shù)據(jù)的安全性：假設(shè)有多個(gè)發(fā)送者用同一個(gè)接收者的公鑰進(jìn)行加密，而敵手除了能夠截獲所有的密文，還能在現(xiàn)實(shí)中賄賂一部分發(fā)送者，取得他們加密的明文以及加密過程中所用的隨機(jī)數(shù)。選擇打開安全性的要求就是，未

2、被賄賂的那些發(fā)送者的明文依然是保密的。
　　目前，選擇打開安全性定義主要有兩類：一類是基于仿真的選擇打開安全性（simulation-based SOA安全性，簡記為SIM-SOA安全性），另一類是基于不可區(qū)分的選擇打開安全性（indistinguishability-based SOA安全性，簡記為IND-SOA安全性）。一個(gè)安全性定義通常還要考慮敵手的攻擊能力，常見的敵手攻擊能力主要有三種：選擇明文攻擊（chosen-plai

3、ntext attack，簡記為CPA）、非適應(yīng)性選擇密文攻擊（non-adaptive chosen-ciphertext attack，簡記為CCA1）和適應(yīng)性選擇密文攻擊（adaptive chosen-ciphertext attack，簡記為CCA2）。敵手的這三種攻擊能力依次增強(qiáng)。所以，相應(yīng)地，SIM-SOA安全性（或IND-SOA安全性）包括SIM-SO-CPA安全性、SIM-SO-CCA1安全性和SIM-SO-CCA2安

4、全性（或IND-SO-CPA安全性、IND-SO-CCA1安全性和IND-SO-CCA2安全性），這三種安全性也是依次增強(qiáng)的。
　　自從選擇打開安全性定義正式提出以來，國際密碼學(xué)界在這方面做了大量的工作，研究熱點(diǎn)主要集中于加密方案的構(gòu)造以及安全性定義之間關(guān)系的發(fā)掘。在方案構(gòu)造方面，目前主要有兩種構(gòu)造方法可以實(shí)現(xiàn)選擇打開安全性，一種是通過Bellare，Hofheinz和Yilek（Eurocrypt2009）提出的有損加密，另一種

5、則是通過Fehr，Hofheinz，Kiltz和Wee（Eurocrypt2010）提出的非承諾加密；在安全性定義之間的關(guān)系方面，目前也有不少重要結(jié)論：比如，在選擇明文攻擊模式下，基于仿真的選擇打開安全性（SIM-SO-CPA安全性）蘊(yùn)含了基于不可區(qū)分的選擇打開安全性（IND-SO-CPA安全性）；又比如，任意綁定（binding）的承諾加密方案都不可能具有SIM-SOA安全性。
　　總的來說，迄今為止，密碼學(xué)界在公鑰加密的選擇打

6、開安全性方面已取得了一系列非常好的研究成果。但是，同時(shí)也有許多問題還有待解決：比如與選擇打開安全方案構(gòu)造密切相關(guān)的All-But-Many有損陷門函數(shù)（all-but-many lossy trapdoor function）（Eurocrypt2012），其安全性證明的歸約不夠緊致，且安全性所基于的假設(shè)也不是標(biāo)準(zhǔn)假設(shè)；又比如，根據(jù)Pass，Shelat和Vaikuntanathan（Asiacrypt2007）的工作，一般的密文不可延

7、展性之間的關(guān)系本身就很復(fù)雜，而選擇打開攻擊模式下的密文不可延展性則根本沒人研究過。
　　我們的研究工作圍繞選擇打開安全性展開，主要結(jié)果包括以下三個(gè)部分。
　　1.我們給出了兩個(gè)SIM-SO-CCA2安全加密方案的構(gòu)造。我們的方案是基于Fehr，Hofheinz，Kiltz和Wee（Eurocrypt2010）的非承諾加密方案（簡記為FHKW方案）而提出的。在本文中，我們對FHKW方案進(jìn)行安全性分析，指出其適應(yīng)性選擇攻擊模式下

8、的非承諾（NC-CCA2）安全性證明根本不成立。更確切地說，F(xiàn)ehr等人在FHKW方案的安全性證明中構(gòu)造了一個(gè)仿真器，并“證明”了該仿真器提供的理想實(shí)驗(yàn)與真實(shí)實(shí)驗(yàn)是計(jì)算不可區(qū)分的；而我們針對該仿真器構(gòu)造出一個(gè)敵手，該敵手能以壓倒性的優(yōu)勢區(qū)分該仿真器提供的理想實(shí)驗(yàn)與真實(shí)實(shí)驗(yàn)。為了解決FHKW方案安全性證明中的這個(gè)問題，我們提出了下面這兩個(gè)方案：
　　2.我們提出一個(gè)簡化版的FHKW方案。該方案雖然只能加密單比特明文，但方案構(gòu)造中剔除

9、了原FHKW方案中不可或缺的交叉認(rèn)證碼，更重要的是，我們的簡化版方案可以證明是NC-CCA2安全的，從而根據(jù)Fehr等人的結(jié)論，該方案也是SIM-SO-CCA2安全的。
　　我們提出“強(qiáng)交叉認(rèn)證碼”的概念，將其用于FHKW方案的構(gòu)造，由此得到了一個(gè)新版的、可以加密多比特明文的FHKW方案，最重要的是，該方案可以證明是NC-CCA2安全的，從而也是SIM-SO-CCA2安全的。
　　3.我們提出“n-含糊的All-But-Ma

10、ny有損陷門函數(shù)（n-evasive all-but-many lossy trapdoor function，簡記為n-evasive ABM-LTF）”的概念，給出了該函數(shù)的兩種構(gòu)造，并利用該函數(shù)構(gòu)造出了一個(gè)IND-SO-CCA2安全的加密方案。具體而言，n-evasive ABM-LTF可以視為All-But-Many有損陷門函數(shù)的一個(gè)特例，同時(shí)也是All-But-n有損陷門函數(shù)的一種推廣。關(guān)于n-evasive ABM-LTF的

11、構(gòu)造，我們提出了兩種方法：第一種以Paillier加密方案作為基本構(gòu)件，其安全性依賴于判定性合數(shù)剩余假設(shè)；第二種以All-But-n有損陷門函數(shù)和變色龍哈希函數(shù)作為基本構(gòu)件，其安全性依賴于這兩個(gè)構(gòu)件本身的安全性。以n-evasive ABM-LTF、有損陷門函數(shù)和哈希函數(shù)這三者作為基本構(gòu)件，我們構(gòu)造出了一個(gè)通用的IND-SO-CCA2安全的公鑰加密方案。
　　4.我們提出了“選擇打開攻擊下的密文不可延展性（non-malleabi

12、lity under selective opening attacks，簡記為NM-SO安全性）”的正式定義，并深入研究了這個(gè)定義與一般的標(biāo)準(zhǔn)安全性定義之間的關(guān)系。更確切地說，我們從“仿真”和“不可區(qū)分”兩個(gè)角度提出“選擇打開攻擊下的密文不可延展性”的形式化定義（分別記為SIM-NM-SO安全性和IND-NM-SO安全性），用于刻畫選擇打開安全的密文不可延展性。我們還深入研究了這兩個(gè)新安全性定義與一般的選擇打開安全性定義、一般的密文不