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

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

1 研究背景

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

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

2 方案介紹

3 方案分析

3.1 正確性分析

3.2 安全性分析

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

3.2.1 挑戰(zhàn)階段

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

3.2.2 猜測階段

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

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

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

4 結(jié)語

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