基于可滿足性問題的非對(duì)稱密碼方案設(shè)計(jì)

孫 瑞，黃佳文，孫學(xué)貴

（上饒師范學(xué)院，江西 上饒 334001）

1 研究背景

公鑰加密(非對(duì)稱加密）體制是保障用戶信息傳輸安全的重要工具,其構(gòu)造往往基于一些難解的困難性問題以保障加密體制的安全性。 可滿足性問題(SAT）是著名的NPC問題,相對(duì)于其他問題假設(shè)來(lái)說(shuō)是應(yīng)用在密碼方案里較少的類型,由于其在一定條件下的難解性,我們考慮以此為基礎(chǔ)建立密碼系統(tǒng)。Schmittner［1］首先基于 SAT 問題構(gòu)造了一個(gè)同態(tài)加密算法, 但安全性并未嚴(yán)格的證明。 而 Thomas 和Chaudhari［2］結(jié)合基于 SAT 與 RSA 算法的優(yōu)點(diǎn)提出了混合密碼協(xié)議,雖然加密過程更簡(jiǎn)便了,但所滿足的安全級(jí)別并未給出。

另一方面,值得關(guān)注的是,布爾表達(dá)式的臨界值決定了其可滿足性與難解性。 Zhou 等人［3］在前人方法的基礎(chǔ)上詳細(xì)證明了(k,s）- SAT臨界值的更為精確的取值范圍。 我們的算法就是基于以上理論前提來(lái)構(gòu)造的,下面我們將介紹此算法的詳細(xì)加、解密過程,接著針對(duì)方案來(lái)證明過程是正確的,并且是選擇明文攻擊安全的,最后總結(jié)此算法的優(yōu)缺點(diǎn)以及未來(lái)的研究方向。

2 方案介紹

3 方案分析

3.1 正確性分析

3.2 安全性分析

這一節(jié),我們將分情況具體分析此密碼方案將會(huì)遇到的挑戰(zhàn)以及其安全性。

3.2.1 挑戰(zhàn)階段

攻擊者隨機(jī)抽取不同明文M0,M1發(fā)送給模擬器,模擬器通過硬幣隨機(jī)在其中選擇一個(gè)密文Mb(b∈｛0,1｝） 對(duì)其加密,攻擊者獲得密文后猜測(cè)一個(gè)值b′。

3.2.2 猜測(cè)階段

在詢問加密機(jī)階段,多項(xiàng)式時(shí)間內(nèi)所獲得的明文-密文對(duì)是有限的。

(1）設(shè)在挑戰(zhàn)階段生成的密文與在詢問階段所獲密文相同的概率為P1。 已知F所包含的變量組合項(xiàng)數(shù)為而每個(gè)Ck的項(xiàng)數(shù)在1 至8 項(xiàng)之間；除此之外,fk中的項(xiàng)數(shù)為1 項(xiàng)至(2N-3-1） 項(xiàng),從而Ckfk將包含 1 項(xiàng)至 8(2N-3- 1） 項(xiàng)。 因此,式子的項(xiàng)數(shù)是m至 8(2N-3- 1）m項(xiàng)。

因此,攻擊者猜對(duì)b′的可能性是可以忽略的函數(shù)。另外,由于本方案的相變點(diǎn)恰當(dāng)?shù)脑O(shè)置足以保證實(shí)例的難解性,從而能夠證明此方案符合選擇明文攻擊安全(IND-CPA 安全）。

4 結(jié)語(yǔ)

這里我們基于(3,s）- SAT的困難性問題提出了一個(gè)非對(duì)稱密碼系統(tǒng)。 相比方案［1］,文章改進(jìn)了SRR(N,k,s） 模型,同時(shí)將約束密度控制在使得(3,s）- SAT合取范式難解的范圍,由此提升了算法的安全級(jí)別。 但其方案仍然存在不足,就是雖然確保了算法的安全性,但存在低效的弊端。 所以,如何既提升其安全性又能提高效率以及通過相關(guān)密碼學(xué)方法使其滿足同態(tài)性等良好的性質(zhì)是接下來(lái)需要考慮的問題。