上饒師范學(xué)院 孫瑞

本文旨在d-正則(3,2s)-CNF問題基礎(chǔ)上提出公鑰加密系統(tǒng)，但一般的具有正則結(jié)構(gòu)的SAT合取范式并沒有加密作用，因此給研究過程帶來較大障礙。為了解決此類問題，我們結(jié)合并改進(jìn)SDRRK2S模型作為隱藏明文的工具，通過引入此模型生成難解的d-正則(3,2s) -CNF實(shí)例，可以達(dá)到密文合取范式難解的目的，從而提高其安全性。

1 研究背景

公鑰加密體制是現(xiàn)代網(wǎng)絡(luò)信息安全的重要工具，也是后量子時(shí)代密碼學(xué)中的關(guān)鍵技術(shù)，它們建立在某些難解問題的基礎(chǔ)上來確保加密體制的安全性，較對(duì)稱密碼系統(tǒng)安全程度更高,公鑰加密模型如圖1所示。而d-正則(3,2s)-CNF問題是相對(duì)于其他問題假設(shè)來說應(yīng)用在密碼方案里極少的類型，目前的基于SAT構(gòu)造的加密系統(tǒng)[1]安全程度較低。值得關(guān)注的是，布爾合取范式的臨界值影響了其是否可滿足性與求解難度，在此方面的研究更多的是關(guān)注其參數(shù)與求解難度間的關(guān)系。研究者們通過矩方法等得出了隨機(jī)(k,s)-SAT臨界值的范圍[2-6]。而后，人們提出的d-正則(3,2s)-CNF問題是一個(gè)具有更強(qiáng)正則約束的SAT問題，而2020年符祖峰等人[7]證明了構(gòu)造此類難解實(shí)例的參數(shù)范圍，并給出了SDRRK2S實(shí)例生成模型，這對(duì)我們進(jìn)一步加強(qiáng)基于SAT問題密碼方案的安全性帶來了有力工具。受此啟發(fā)，下面我們以這些研究工作為基礎(chǔ)來建立一個(gè)以d-正則(3,2s)-CNF問題為困難性假設(shè)的加密模型。

2 方案介紹

在本節(jié)，將闡述此加密算法的具體過程，加密系統(tǒng)模型如圖2所示。

圖2 本方案加密算法模型Fig.2 The encryption algorithm model of this scheme

算法1：密鑰生成算法

Input：隨機(jī)選擇變量個(gè)數(shù)M，以及n,yj(j=1,2,...,M)，出現(xiàn)的次數(shù)2s=20，d=8(其中n,M∈N*,M≥220,n/M=4.267,sM=3n,)，私鑰sk:Y=y1y2...yM，k=3。

Output：d-正則(3, 2s)-CNF公式

Step 1.令R:=?,t:=1,E:=1,K=1,2,...,N,保存E中值為真的文字序號(hào)；

Step 2.對(duì)于每個(gè)yj(j=1,2,...,M)，將yj的（或）個(gè)正文字和（或個(gè)負(fù)文字置于B中;

Step 3.在B中任意不重復(fù)地抽3個(gè)文字ek1,ek2,ek3;

Step 3.1如果t≤n，E=1時(shí)，重復(fù)下列步驟；

Step 3.2如果k1、k2、k3兩兩互不相同，且ek1,ek2,ek3互異且不同時(shí)出現(xiàn)在已產(chǎn)生的Et中，(令t=1,2,...,n，表示的真值)，執(zhí)行Step 3.2.1和Step 3.2.2;

Step 3.2.1 把ykj代 入ekj( j∈{1, 2, 3})，如果將ekj置于B中，同時(shí)把kj置于S1；否則，執(zhí)行Step 3.2.2;

Step 3.2.2 核對(duì)已產(chǎn)生的含有kj(j∈{1,2,3})的Sk(k=1,2,...,t-1），如果將ykj的值代入Ek后，所對(duì)應(yīng)的ek′j真值為1，同時(shí)Ek里另外三個(gè)文字被私鑰賦值后任意一個(gè)真值為1，則互換ekj與ek′j，并把kj放置于St內(nèi)，再把Sk里的kj去除；否則，把ek1,ek2,ek3置于B內(nèi)，執(zhí)行Step 3；

Step 3.3得到析取范式Et，把里面的ek1,ek2,ek3按角標(biāo)依次增大排列；

Step 3.4R:=R∩Et，t:=t+1，E=1，那么執(zhí)行Step 3；

算法2：加密算法

算法2.2 產(chǎn)生布爾函數(shù)，它是由除Et中出現(xiàn)的變?cè)獾钠溆嘧兞繕?gòu)成的任意布爾函數(shù)；

算法2.3 假設(shè)明文是X，通過運(yùn)算下列式子加密:

為使上式成立，作如下分類討論：

算法3：解密算法

接收者使用私鑰Y=y1y2...yM計(jì)算密文：X=Φ⊕1，解出X。

3 方案分析

3.1 正確性分析

我們通過明文的兩種取值來討論方案的正確性：

即：X⊕Φ=1

所以，（1）式是正確的。

3.2 方案對(duì)比

下面我們將本方案與文獻(xiàn)[1]的加密系統(tǒng)進(jìn)行對(duì)比，具體將從困難性假設(shè)與安全性兩方面討論。如表1所示：

表1 本文方案與已有的基于SAT的加密方案的對(duì)比Tab.1 Comparison between the proposed scheme and existing SAT-based encryption schemes

由上表可知，文獻(xiàn)[1]是建立在k-SAT問題基礎(chǔ)上的，而我們的方案是基于隨機(jī)正則d-正則(3,2s)-CNF問題的難解性假設(shè)。兩個(gè)方案在密鑰長(zhǎng)度和密文的長(zhǎng)度上相同，但本方案是IND-CPA安全的，相對(duì)來說能夠提供更高的安全保障。

4 結(jié)語

本文在傳統(tǒng)的3-SAT問題上另辟蹊徑，在隨機(jī)d-正則(3,2s)-CNF問題的基礎(chǔ)上構(gòu)造了加密協(xié)議。相比方案[1]，本文結(jié)合了SDRRK2S模型，同時(shí)將約束密度控制在了使得d-正則(3,2s)-CNF難以求解的值上，進(jìn)一步強(qiáng)化了加密算法的安全程度，相對(duì)于現(xiàn)有的基于SAT問題的密碼系統(tǒng)安全系數(shù)有所提高。但目前仍然存在加密效率不高，以及安全性還待提高等問題，考慮如何用其他密碼學(xué)或數(shù)學(xué)工具進(jìn)一步完善是主要難題，接下來的工作方向是如何在保證已有優(yōu)勢(shì)的條件下，使其具有高效、安全以及同態(tài)性等較好的計(jì)算性質(zhì)。