基于可滿足性問題的非對稱密碼方案設計

孫 瑞，黃佳文，孫學貴

（上饒師范學院，江西 上饒 334001）

1 研究背景

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

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

2 方案介紹

3 方案分析

3.1 正確性分析

3.2 安全性分析

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

3.2.1 挑戰階段

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

3.2.2 猜測階段

在詢問加密機階段,多項式時間內所獲得的明文-密文對是有限的。

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

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

4 結語

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