基于不經(jīng)意多項(xiàng)式估值的SM4協(xié)同加解密方案

摘 要：協(xié)同加解密是安全多方計(jì)算中的重要研究方向，它可以安全高效地實(shí)現(xiàn)數(shù)據(jù)保護(hù)、隱私保護(hù)。為解決現(xiàn)有SM4協(xié)同加解密方案離線(xiàn)計(jì)算階段計(jì)算復(fù)雜度偏高的問(wèn)題，提出一種基于不經(jīng)意多項(xiàng)式估值的SM4協(xié)同加解密方案。方案利用預(yù)計(jì)算的多項(xiàng)式集合和多項(xiàng)式值集合來(lái)完成在線(xiàn)階段的S盒協(xié)同計(jì)算，從而提高在線(xiàn)計(jì)算階段的性能。其證明了所提方案的正確性和安全性，同時(shí)與四種不同的方案進(jìn)行對(duì)比，結(jié)果表明，所提方案計(jì)算效率明顯高于其他方案，說(shuō)明所提方案能安全高效地完成SM4協(xié)同加解密。

關(guān)鍵詞：安全多方計(jì)算； 協(xié)同加解密； SM4； 不經(jīng)意多項(xiàng)式估值

中圖分類(lèi)號(hào)：TP309 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2024）06-038-1862-07

doi：10.19734/j.issn.1001-3695.2023.09.0432

SM4 collaborative encryption and decryption scheme based onoblivious polynomial evaluation

Abstract：Cooperative encryption and decryption is an important research direction in secure multi-party computation. It can achieve data protection and privacy protection safely and efficiently. To solve the problem of high computational complexity in the offline calculation phase of existing SM4 collaborative encryption and decryption schemes， this paper proposed a new SM4 collaborative encryption and decryption scheme based on oblivious polynomial evaluation. The scheme utilized pre-calculated polynomial sets and sets of polynomial values to complete S-box collaborative computation in the online stage， thereby improving the performance of the online calculation stage. This paper proved the correctness and security of the proposed scheme， and compared with four different schemes，the results show that the computational efficiency of the proposed scheme is significantly higher than that of other schemes. This shows that the proposed scheme can complete SM4 cooperative encryption and decryption safely and efficiently.

Key words：secure multi-party computation; collaborative encryption and decryption; SM4; oblivious polynomial evaluation

0 引言

隨著信息技術(shù)和通信技術(shù)的迅速發(fā)展，以及人們對(duì)網(wǎng)絡(luò)安全和數(shù)據(jù)隱私保護(hù)的日益關(guān)注，作為一個(gè)擁有龐大人口和復(fù)雜安全環(huán)境的國(guó)家，保護(hù)個(gè)人隱私、商業(yè)機(jī)密和國(guó)家機(jī)密已經(jīng)成為了目前面臨的一項(xiàng)重要挑戰(zhàn)。在這種背景下，建立具備自主知識(shí)產(chǎn)權(quán)的加密系統(tǒng)，成為了政府推動(dòng)信息化建設(shè)、保障國(guó)家安全的一個(gè)緊迫問(wèn)題。SM4正是針對(duì)上述需求而推出的一款符合國(guó)際標(biāo)準(zhǔn)、具有自主知識(shí)產(chǎn)權(quán)、能夠滿(mǎn)足不同安全等級(jí)需求的分組密碼算法。在多個(gè)組織或參與者之間共享和協(xié)作處理敏感數(shù)據(jù)時(shí)，需要確保各自數(shù)據(jù)的機(jī)密性和安全性，由于集中式加解密方式存在單點(diǎn)故障和中心化信任問(wèn)題，不再適用。

協(xié)同加解密技術(shù)可以防止單點(diǎn)故障和黑客攻擊，其理論和算法建立在安全多方計(jì)算［1］和密碼學(xué)的基礎(chǔ)上，可以有效應(yīng)對(duì)信息處理中的安全問(wèn)題。它采用了類(lèi)似于區(qū)塊鏈技術(shù)的去中心化模型，允許多方在不需要可信第三方的情況下協(xié)同加解密，從而獲取敏感數(shù)據(jù)。在傳統(tǒng)的加密方式中，一般都是由一方來(lái)掌握加解密的權(quán)限，這可能會(huì)導(dǎo)致數(shù)據(jù)難以共享，同時(shí)也存在被竄改和泄露的風(fēng)險(xiǎn)。協(xié)同加解密技術(shù)將數(shù)據(jù)和加解密的控制權(quán)分布到整個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)，使得每一個(gè)節(jié)點(diǎn)都具有數(shù)據(jù)加解密的能力，密鑰也被分散存儲(chǔ)在多個(gè)節(jié)點(diǎn)上，從而降低了密鑰被攻擊的風(fēng)險(xiǎn)，能夠更好地保證數(shù)據(jù)隱私和安全。盡管協(xié)同加解密技術(shù)在實(shí)現(xiàn)時(shí)存在很多難題，并且需要合適的環(huán)境和基礎(chǔ)設(shè)施支撐，但是它為數(shù)據(jù)共享和計(jì)算提供了一種全新的解決方案。

最早的協(xié)同計(jì)算方案大多基于1979年Shamir［2］提出的門(mén)限秘密共享方法。該方法將密鑰分成n份，并分別由n個(gè)參與方保存。然后設(shè)置一個(gè)特定的門(mén)限值t。只有當(dāng)參與方的數(shù)量大于或等于t時(shí)，這些參與方才可以通過(guò)多項(xiàng)式插值的方法恢復(fù)出完整的密鑰，然后完成簽名或者解密操作。但這種方法存在一定的安全隱患，參與方在獲得完整密鑰后，即可在其他參與方不知情的情況下使用密鑰。MacKenzie等人［3］提出一種DSA兩方協(xié)同簽名的方案，將私鑰分割后分別存儲(chǔ)在兩個(gè)實(shí)體中，雙方都不能單獨(dú)生成合法的DSA簽名，只有通過(guò)一系列的交互后才可以協(xié)同完成簽名或解密，全程不會(huì)暴露雙方的私鑰。Mu等人［4］提出一種SM9兩方協(xié)同簽名的方案，保證雙方不需要重構(gòu)出完整私鑰的情況下，通過(guò)協(xié)作能輸出合法的SM9簽名。徐彬彬等人［5］提出了支持門(mén)限的分布式SM2/SM9算法，但算法中引入了同態(tài)加密，算法的計(jì)算復(fù)雜度較高。Lindell［6］提出一種基于Paillier同態(tài)加密算法的兩方ECDSA協(xié)同簽名方案，規(guī)避了大量零知識(shí)證明，利用Paillier算法的同態(tài)性質(zhì)來(lái)完成兩方協(xié)同簽名，但由于方案中引入了Paillier同態(tài)加密算法，方案的性能有待提高。顏萌等人［7］提出了一種高效的兩方ECDSA門(mén)限方案簽名，將簽名分為預(yù)計(jì)算階段和在線(xiàn)簽名階段，將在線(xiàn)簽名階段的同態(tài)操作轉(zhuǎn)移到預(yù)計(jì)算階段，加快了在線(xiàn)簽名階段的計(jì)算速度。嚴(yán)都力等人［8］提出了一種抗差分故障攻擊的兩方協(xié)同EdDSA簽名方案，但也借助了Paillier同態(tài)加密算法。Doerner等人［9］提出了一種基于秘密共享和不經(jīng)意傳輸技術(shù)的協(xié)同計(jì)算方案，由于引入了不經(jīng)意傳輸技術(shù)，通信量和通信次數(shù)比較高。文嘉明等人［10］提出了一種基于非對(duì)稱(chēng)模格問(wèn)題的兩方協(xié)同Aigis簽名，能有效縮減簽名的尺寸。關(guān)于公鑰密碼協(xié)同計(jì)算的研究都集中在RSA協(xié)同簽名、ECDSA協(xié)同簽名［11，12］、SM2/9協(xié)同簽名。

不經(jīng)意多項(xiàng)估值協(xié)議作為一種兩方安全的多方計(jì)算協(xié)議，可以作為很多安全多方計(jì)算協(xié)議實(shí)現(xiàn)的基礎(chǔ)。Dttling等人［13］提出了一個(gè)兩方安全多方計(jì)算協(xié)議，其中兩個(gè)參與者使用不經(jīng)意多項(xiàng)式估值在預(yù)計(jì)算階段完成乘法三元組的計(jì)算。楊博為等人［14］提出了一種三方不經(jīng)意多項(xiàng)式求值協(xié)議，協(xié)議利用Diffie-Hellman密鑰交換協(xié)議和安全的不經(jīng)意傳輸來(lái)實(shí)現(xiàn)。Cianciullo等人［15］提出用不經(jīng)意多項(xiàng)式估值來(lái)計(jì)算安全多方計(jì)算中的乘法，與使用Beaver乘法三元組的方法相比，減少了計(jì)算乘法時(shí)所需參與方數(shù)量，降低了通信復(fù)雜度。Cianciullo等人［16］將分布式不經(jīng)意傳輸協(xié)議改編為靈活的分布式不經(jīng)意多項(xiàng)式估值協(xié)議，同時(shí)創(chuàng)建了第三方不經(jīng)意多項(xiàng)式估值協(xié)議的三個(gè)擴(kuò)展。

從公開(kāi)的文獻(xiàn)來(lái)看，對(duì)稱(chēng)密碼協(xié)同計(jì)算的研究并不多。楊伊等人［17］提出了一種密鑰管理服務(wù)系統(tǒng)下的安全高效的多方協(xié)同SM4加/解密方案。該方案利用Beaver乘法三元組［18］來(lái)實(shí)現(xiàn)S盒協(xié)同計(jì)算的高效性和安全性，但生成Beaver乘法三元組時(shí)需要用到同態(tài)加密，而同態(tài)加密需要進(jìn)行復(fù)雜的數(shù)學(xué)運(yùn)算，其計(jì)算量大、速度慢，需要更多的計(jì)算資源和存儲(chǔ)空間。

本文基于不經(jīng)意多項(xiàng)式估值協(xié)議設(shè)計(jì)了一種新的SM4協(xié)同加解密方案，該方案由離線(xiàn)預(yù)計(jì)算階段和在線(xiàn)計(jì)算階段組成，預(yù)計(jì)算階段執(zhí)行不經(jīng)意多項(xiàng)式估值協(xié)議后，參與方能分別獲得多項(xiàng)式集合和多項(xiàng)式值的集合。在線(xiàn)計(jì)算階段的關(guān)鍵在于S盒協(xié)同計(jì)算，各參與方利用預(yù)計(jì)算階段計(jì)算得到的多項(xiàng)式集合和多項(xiàng)式值的集合進(jìn)行S盒協(xié)同計(jì)算。由于預(yù)計(jì)算階段的不經(jīng)意多項(xiàng)估值協(xié)議是采用引入隨機(jī)函數(shù)的方法而不是同態(tài)加密，提高了SM4協(xié)同加解密的運(yùn)算性能。

1 預(yù)備知識(shí)

1.1 半誠(chéng)實(shí)模型及其安全性定義

定義1 半誠(chéng)實(shí)模型下協(xié)議的安全性［19］。當(dāng)參與者都是半誠(chéng)實(shí)參與者時(shí)，若存在概率多項(xiàng)式時(shí)間算法E，使得對(duì)于任意的I，都有式（2）成立：

1.2 SM4算法

SM4［20］是我國(guó)自主設(shè)計(jì)的分組密碼算法。該算法的分組長(zhǎng)度和密鑰長(zhǎng)度均為128 bit。加密算法與密鑰擴(kuò)展算法都采用32輪非線(xiàn)性迭代結(jié)構(gòu)。SM4采用了Feistel結(jié)構(gòu)，解密算法與加密算法的結(jié)構(gòu)相同，只是輪密鑰的使用順序相反，解密輪密鑰是加密輪密鑰的逆序。S盒是SM4的關(guān)鍵部分，查表實(shí)現(xiàn)是S盒最基本的實(shí)現(xiàn)方法，還有一種是通過(guò)多項(xiàng)式運(yùn)算來(lái)實(shí)現(xiàn)的。SM4的S盒定義在GF（28）上，該伽羅瓦域采用的不可約多項(xiàng)式M（x）是x8+x7+x6+x5+x4+x2+1，S盒的生成方式為S（x）=A（Ax+c）-1+c，其中：

1.3 不經(jīng)意多項(xiàng)式估值

不經(jīng)意多項(xiàng)式估值（oblivious polynomial evaluation，OPE）是Naor等人 ［21］在1999年首次提出的。一個(gè)OPE協(xié)議有一個(gè)發(fā)送方和一個(gè)接收方，發(fā)送方S擁有一個(gè)私密多項(xiàng)式W（x），接收方R擁有一個(gè)私密值α。OPE協(xié)議執(zhí)行完成后，接收方R只能得到W（α），發(fā)送方S得不到任何信息，同時(shí)保證發(fā)送方的W（x）不泄露。

2 方案設(shè)計(jì)

安全多方計(jì)算允許n個(gè)相互不信任的參與方在其私密輸入不泄露的前提下，安全計(jì)算任何給定函數(shù)。就效率和通信復(fù)雜性而言，安全多方計(jì)算協(xié)議中的乘法運(yùn)算一直是瓶頸。當(dāng)前協(xié)議大多數(shù)采用的典型方法是使用Beaver乘法三元組來(lái)完成乘法運(yùn)算，該方法依賴(lài)于同態(tài)加密或不經(jīng)意傳輸。文獻(xiàn)［13］介紹了一種基于不經(jīng)意多項(xiàng)式估值的安全多方計(jì)算協(xié)議，該協(xié)議雖然也依賴(lài)于一些預(yù)先計(jì)算的信息，但在效率和通信復(fù)雜性上都要優(yōu)于基于Beaver乘法三元組的安全多方計(jì)算協(xié)議。

SM4的運(yùn)算可以分為線(xiàn)性運(yùn)算和非線(xiàn)性運(yùn)算，非線(xiàn)性運(yùn)算即S盒運(yùn)算，除S盒運(yùn)算外都是線(xiàn)性運(yùn)算?，F(xiàn)有的協(xié)同加解密的思路大多都基于秘密分享，但是由于S盒運(yùn)算是非線(xiàn)性的，所以?xún)H僅對(duì)SM4的密鑰、明文等其他參數(shù)進(jìn)行秘密分享是無(wú)法實(shí)現(xiàn)正確的SM4協(xié)同加解密的。實(shí)現(xiàn)SM4協(xié)同加解密的關(guān)鍵在于實(shí)現(xiàn)S盒的協(xié)同計(jì)算結(jié)果與原始SM4的S盒輸出結(jié)果相同。文獻(xiàn)［17］提出了一種對(duì)S盒進(jìn)行協(xié)同設(shè)計(jì)來(lái)實(shí)現(xiàn)SM4協(xié)同加解密的方法，其中S盒協(xié)同計(jì)算通過(guò)Beaver乘法三元組來(lái)實(shí)現(xiàn)安全兩方乘法，但是Beaver乘法三元組的生成需要用到同態(tài)加密，計(jì)算開(kāi)銷(xiāo)大。

本文是在文獻(xiàn)［17］對(duì)S盒協(xié)同計(jì)算來(lái)實(shí)現(xiàn)SM4協(xié)同加解密的思路上，對(duì)其方案進(jìn)行改進(jìn)，利用不經(jīng)意多項(xiàng)式估值來(lái)實(shí)現(xiàn)S盒協(xié)同計(jì)算時(shí)需要的安全的兩方乘法運(yùn)算，從而實(shí)現(xiàn)比文獻(xiàn)［17］方案更高效的SM4協(xié)同加解密。

本文提出的SM4協(xié)同加解密方案分為預(yù)計(jì)算階段和在線(xiàn)計(jì)算階段兩部分，其中預(yù)計(jì)算階段執(zhí)行不經(jīng)意多項(xiàng)式估值協(xié)議，為在線(xiàn)計(jì)算階段的S盒協(xié)同計(jì)算部分的兩方安全乘法作準(zhǔn)備。在線(xiàn)計(jì)算階段包括密鑰與消息分配、S盒協(xié)同計(jì)算、密鑰協(xié)同擴(kuò)展和協(xié)同加解密四個(gè)部分。由于SM4采用的是Feistel結(jié)構(gòu)，加解密的結(jié)構(gòu)對(duì)稱(chēng)，只是輪密鑰的使用順序相反，所以本文只對(duì)協(xié)同加密（圖1）進(jìn)行描述。協(xié)同加密的具體過(guò)程在下文展開(kāi)描述，其中加密算法與密鑰擴(kuò)展算法都采用32輪非線(xiàn)性迭代結(jié)構(gòu)。

2.1 符號(hào)及定義

本文方案的符號(hào)及定義如表1所示。

2.2 預(yù)計(jì)算階段

以?xún)蓚€(gè)參與方為例，參與方P1隨機(jī)選擇a0，a1∈GF（28）構(gòu)造多項(xiàng)式W（x）=a0+a1x。參與方P2隨機(jī)選擇α∈GF（28）。協(xié)議執(zhí)行完后，參與方P1不泄露其多項(xiàng)式，參與方P2獲得多項(xiàng)式值W（α）。不經(jīng)意多項(xiàng)式估值協(xié)議（圖2）具體過(guò)程如下：

a）P1隨機(jī)選取a2，a3，r1，r2，r3，r4，t1，t2∈GF（28），計(jì)算g（x）、R1（x）和R2（x）為

g（x）=r2+r3xR1（x）=r1W（x）+r2g（x）+t1R2（x）=r3W（x）+r4g（x）+t2（4）

GF（28）中的元素都是次數(shù)小于或等于8的多項(xiàng)式，多項(xiàng)式的加法可以轉(zhuǎn)換成其對(duì)應(yīng)2進(jìn)制數(shù)的異或，所以R1（x）和R2（x）可以表示為

并將R1（x）和R2（x）發(fā)送給P2。

并將Q1、R1′（x）和R2′（x）發(fā)送給P2。

d）P2隨機(jī)選取η2∈GF（28），計(jì)算U2為

并將U2發(fā)送給P1。

f）P2隨機(jī)選取Y∈GF（28），計(jì)算U3為

并將U3發(fā)送給P1。

g）P1計(jì)算Q3為

并將Q3發(fā)送給P2。

h）P2計(jì)算ξ=Q3Y-1=W（α）。

2.3 密鑰與消息分配

該階段完成密鑰、消息、系統(tǒng)參數(shù)的分配，將加密密鑰key、明文M、系統(tǒng)參數(shù)FK、系統(tǒng)參數(shù)CK、S盒仿射變換使用的c都分割成n份，分別發(fā)送給n個(gè)參與方。

2.4 S盒協(xié)同計(jì)算

每個(gè)參與方借助預(yù)計(jì)算階段計(jì)算得到的多項(xiàng)式集合和多項(xiàng)式值的集合與剩下的n-1個(gè)參與方兩兩協(xié)同計(jì)算，各自獲得S盒的輸出，具體過(guò)程如下：

（a）P1的S盒輸入為x1，P1計(jì)算第一次仿射變換后的中間值β1為β1=Ax1+c1。P2的S盒輸入為x2，P2計(jì)算第一次仿射變換后的中間值β2=Ax2+c2。

（b）P1從預(yù)計(jì)算階段生成的多項(xiàng)式集合中順序選擇W1（x）和W2（x）為

W1（x）=θ1+θ2x，W2（x）=θ3+θ4x（13）

P1隨機(jī)選取v1、v2，b1∈GF（28），得到F1（x）和F2（x）為

F1（x）=v1+β1x，F(xiàn)2（x）=v2+b1x（14）

（c）P2隨機(jī)選取b2∈GF（28），并且從多項(xiàng)式集合中順序選擇W1（α1）和W2（α2）為

P2計(jì)算u1、u2并將其發(fā)送給P1。

（d）P1計(jì)算V1（x）、V2（x）、h1，并將其發(fā)送給P2。

（e）P2計(jì)算F1（b2）、F2（β2）、h2，并將h2發(fā)送給P1。

（f）此時(shí)雙方都能計(jì)算出h為

b）Pi與剩余的參與方兩兩執(zhí)行安全兩方乘法后，將各自的hi發(fā)給剩余的參與方，所有參與方都能計(jì)算出h為

Pi先計(jì)算（kij）k為

（kij）k=h-1×（bij）kmod M（x）（21）

然后進(jìn)行第二次仿射變換計(jì)算得到（lij）k為

最終，Pi的S盒協(xié)同計(jì)算的結(jié)果為

lij=（（lij）0，（lij）1，（lij）2，（lij）3）（23）

2.5 密鑰協(xié)同擴(kuò)展

密鑰協(xié)同擴(kuò)展的過(guò)程除了將原始SM4的S盒計(jì)算部分替換成S盒協(xié)同計(jì)算，其他部分都和原始SM4一樣。n個(gè)參與方協(xié)同計(jì)算出各自的輪密鑰rkij。

Pi擁有部分密鑰keyi=（keyi0，keyi1，keyi2，keyi3），首先計(jì)算Ki0、Ki1、Ki2、Ki3為

然后，對(duì)于j=0，1，2，…，31，Pi操作如下：

a）計(jì)算σij為

將σij作為4個(gè)S盒的輸入。n個(gè)參與方進(jìn)行S盒協(xié)同計(jì)算后，得到各自的S盒輸出為lij。

b）計(jì)算輪密鑰rkij為

2.6 協(xié)同加密

協(xié)同加密的過(guò)程與密鑰協(xié)同擴(kuò)展的過(guò)程基本相同，只是將其中的線(xiàn)性變換L修改為L(zhǎng)′。每個(gè)參與方都擁有部分明文Mi和輪密鑰rkij 。從第1輪（j=0）到第32輪（j=31），Pi循環(huán)執(zhí)行以下操作：

a）Pi擁有部分明文Mi=（Xi0，Xi1，Xi2，Xi3），計(jì)算σij′為

Pi將σij′分別作為4個(gè)S盒的輸入。n個(gè)參與方進(jìn)行S盒協(xié)同計(jì)算后，得到各自的S盒輸出為lij′。

b）用S盒的輸出來(lái)計(jì)算Xij+4為

經(jīng)過(guò)32輪協(xié)同加密后，Pi得到部分密文Ci為

Ci=（Xi35，Xi34，Xi33，Xi32）（29）

將所有參與方的部分密文合并得到最終的密文為

3 安全性證明

3.1 正確性分析

本文方案關(guān)鍵在于預(yù)計(jì)算階段的不經(jīng)意多項(xiàng)式估值協(xié)議和在線(xiàn)計(jì)算階段的S盒協(xié)同計(jì)算。在線(xiàn)計(jì)算階段的S盒協(xié)同計(jì)算利用安全多方計(jì)算，保證多方交互過(guò)程中各方擁有的秘密值不被泄露以及最終結(jié)果的正確性，其他部分都和原始SM4保持一致。因此，本文方案的正確性分析主要是針對(duì)預(yù)計(jì)算階段的不經(jīng)意多項(xiàng)式估值協(xié)議和在線(xiàn)階段的S盒協(xié)同計(jì)算兩部分進(jìn)行的。

a）不經(jīng)意多項(xiàng)式估值協(xié)議的正確性分析。

b）S盒協(xié)同計(jì)算的正確性分析。

S盒協(xié)同計(jì)算是正確的，等價(jià)于各參與方S盒協(xié)同計(jì)算輸出異或起來(lái)的結(jié)果與原始SM4算法S盒輸出是一致的。

這樣就保證了n個(gè)參與方協(xié)同計(jì)算后，各自得到的S盒輸出全部異或之后的結(jié)果和原始SM4的S盒輸出是一致的。因此，本文方案中的S盒協(xié)同計(jì)算是正確的。

兩方SM4協(xié)同加密結(jié)果如圖4所示，兩方密文異或結(jié)果與原始SM4加密的密文一致，因此本文的SM4協(xié)同加密方案是正確的。

3.2 安全性分析

本方案分為預(yù)計(jì)算階段和在線(xiàn)計(jì)算階段，需對(duì)兩個(gè)階段都進(jìn)行安全性證明。預(yù)計(jì)算階段主要是參與方兩兩多次執(zhí)行不經(jīng)意多項(xiàng)式估值協(xié)議生成多項(xiàng)式集合、多項(xiàng)式值的集合，為在線(xiàn)計(jì)算階段的S盒協(xié)同計(jì)算安全乘法部分做準(zhǔn)備。在線(xiàn)計(jì)算階段是在SM4基礎(chǔ)上，利用不經(jīng)意多項(xiàng)式估值協(xié)議進(jìn)行S盒協(xié)同設(shè)計(jì)。SM4的安全性建立在底層結(jié)構(gòu)和多輪迭代上，本文方案基于不經(jīng)意多項(xiàng)式估值協(xié)議的S盒協(xié)同計(jì)算并沒(méi)有破壞SM4底層結(jié)構(gòu)和多輪迭代。因此，本文方案的安全性分析主要針對(duì)預(yù)計(jì)算階段的不經(jīng)意多項(xiàng)式估值協(xié)議以及在線(xiàn)計(jì)算階段的S盒協(xié)同計(jì)算。

a）不經(jīng)意多項(xiàng)式估值協(xié)議的安全性分析。

不經(jīng)意多項(xiàng)式估值協(xié)議的安全性分為兩方面：一方面是協(xié)議結(jié)束后發(fā)送方不能獲得接收方所得的份額（α，W（α））的任何信息。另一方面是協(xié)議結(jié)束后，接收方只能得到份額（α，W（α）），除此之外不能得到任何有關(guān)W（x）的信息。

（a）協(xié)議結(jié)束后，發(fā)送方不能獲得接收方所得的份額（α，W（α））的任何信息。

證明 由協(xié)議可知，發(fā)送方從接收方得到的信息為U1、U2、U3三個(gè)等式計(jì)算得到的數(shù)值。接收方在每個(gè)等式中都引入了一個(gè)隨機(jī)數(shù)，分別為η1、η2、Y。接收方的α對(duì)于發(fā)送方來(lái)說(shuō)也是一個(gè)隨機(jī)數(shù)。未知數(shù)個(gè)數(shù)為4，方程個(gè)數(shù)為3，未知數(shù)個(gè)數(shù)大于方程個(gè)數(shù)，因此發(fā)送方無(wú)法計(jì)算出接收方的α。

（b）協(xié)議結(jié)束后，接收方只能得到份額（α，W（α）），除此之外不能得到任何有關(guān)W（x）的信息。

b）S盒協(xié)同計(jì)算的安全性。

現(xiàn)在借助模擬器的概念來(lái)證明S盒協(xié)同計(jì)算的安全性。

證明 因?yàn)樵赟盒協(xié)同計(jì)算的過(guò)程中，所有參與方的地位是相同的，所以誠(chéng)實(shí)的參與方能受到最大的安全威脅就是其他所有參與方合謀企圖獲得該誠(chéng)實(shí)參與方的隱私輸入。這些攻擊者構(gòu)成的集合稱(chēng)為最大合謀攻擊者集合。如果協(xié)議對(duì)最大合謀攻擊者集合是安全的，顯然對(duì)于最大合謀攻擊者集合的任何子集都是安全的。假設(shè)P1是誠(chéng)實(shí)的參與方，最大合謀攻擊者集合為I={P2，P3，…，Pn}。

在協(xié)議執(zhí)行過(guò)程中，I作為一個(gè)整體收到的消息只有u121，u122，…，u1n1，u1n2和h121，…，h1n1以及最后用于計(jì)算h值的h1。那么在協(xié)議執(zhí)行過(guò)程中，I的視圖為

viewΠI（β1，…，βn，b1，…，bn）=

{u121，u122，…，u1n1，u1n2，…，h121，…，h1n1，h1}（33）

接下來(lái)本文通過(guò)構(gòu)造模擬器S來(lái)證明協(xié)議的安全性。E的模擬過(guò)程如下：

（a）接收輸入 （I，（β2，…，βn，b2，…，bn），fI（β1，…，βn，b1，…，bn）），隨機(jī)選擇β1′，b1′∈GF（28），使得

（b）隨機(jī)選擇v121′，v122′，…，v1n1′，v1n2′∈GF（28），構(gòu)造多項(xiàng)式F121′（x），F(xiàn)122′（x），…，F(xiàn)1n1′（x），F(xiàn)1n2′（x）。

（c）隨機(jī)選取α121′，α122′，…，α1n1′，α1n2′∈GF（28）為不經(jīng)意多項(xiàng)式的私密值，隨機(jī)構(gòu)造多項(xiàng)式W121（x），W122（x），…，W1n1（x），W1n2（x）。

（d）E模擬協(xié)議中的所有成員（模擬的P1不參與合謀）執(zhí)行協(xié)議得到

在P1不參與合謀的情況下，在I的視角下，u121，u122，…，u1n1，u1n2和u121′，u122′，…，u1n1′，u1n2′都是GF（28）中的隨機(jī)數(shù)，它們是計(jì)算不可區(qū)分的。同樣地，h121，…，h1n1，h1和h121′，…，h1n1′，h1′也都是GF（28）中的隨機(jī)數(shù)，它們也是計(jì)算不可區(qū)分的。

（e）因而得到

因此，本文的S盒協(xié)同計(jì)算在半誠(chéng)實(shí)模型下是安全的。綜上所述，本文方案在半誠(chéng)實(shí)敵手模型下是安全的。

4 性能分析及實(shí)驗(yàn)驗(yàn)證

4.1 計(jì)算量分析對(duì)比

在半誠(chéng)實(shí)敵手模型下，將公鑰密碼協(xié)同簽名看作特殊的加密，用文獻(xiàn)［6，7，17，22］與本文方案對(duì)同一明文進(jìn)行兩方協(xié)同加密，對(duì)5個(gè)方案進(jìn)行對(duì)比分析。加減法的計(jì)算量遠(yuǎn)小于橢圓曲線(xiàn)上的點(diǎn)乘運(yùn)算計(jì)算量、Paillier加密及解密計(jì)算的計(jì)算量、求逆運(yùn)算的計(jì)算量、普通乘法的計(jì)算量，因此在分析計(jì)算量時(shí)，本文忽略加減法的計(jì)算量，把一次橢圓曲線(xiàn)上的點(diǎn)乘運(yùn)算的時(shí)間記為T(mén)d，Paillier加密或解密計(jì)算時(shí)間記為T(mén)p，將求逆運(yùn)算的時(shí)間記為T(mén)i，將一次普通乘法的時(shí)間記為T(mén)m，將一次關(guān)于循環(huán)群上橢圓曲線(xiàn)離散對(duì)數(shù)關(guān)系的零知識(shí)證明時(shí)間記為T(mén)zk。普通乘法和求逆都為線(xiàn)性運(yùn)算，其運(yùn)算復(fù)雜度遠(yuǎn)遠(yuǎn)小于橢圓曲線(xiàn)上的點(diǎn)乘、Paillier加解密。

Paillier同態(tài)加密密文c=rNgm（mod N2），當(dāng)生成元g取N+1時(shí)，gm可以簡(jiǎn)化成1+mN，進(jìn)一步密文可以轉(zhuǎn)換為c=rN·（1+mN）（mod N2）。Tp就可以轉(zhuǎn)換成N次乘法運(yùn)算所需的時(shí)間，而N是兩個(gè)大素?cái)?shù)的乘積，N>>1792，因此Tp&gt;>1792Tm。Ti為求逆運(yùn)算所需時(shí)間，求逆運(yùn)算通過(guò)擴(kuò)展歐幾里德算法實(shí)現(xiàn)，其計(jì)算量與輸入的整數(shù)大小相關(guān)，假設(shè)輸入的整數(shù)為A和模數(shù)B，且A<B。擴(kuò)展歐幾里德算法的計(jì)算量取決于迭代的次數(shù)。每次迭代都需要計(jì)算商和余數(shù)。在最壞情況下，擴(kuò)展歐幾里德算法的迭代次數(shù)不超過(guò)log2（A）次。由于SM4協(xié)同加解密在線(xiàn)計(jì)算階段的數(shù)據(jù)大小在0～501，Ti最多為9次除法，因此Tp>>259Ti。由4個(gè)方案的效率對(duì)比結(jié)果（表2）可知，本文方案優(yōu)于其他方案。

a）本文和文獻(xiàn)［17］的對(duì)稱(chēng)密碼協(xié)同加密方案和公鑰協(xié)同加密方案相比，不需要密鑰生成階段。

b）離線(xiàn)預(yù)計(jì)算階段：本文方案中，用戶(hù)P1執(zhí)行了16次乘法運(yùn)算和5次求逆運(yùn)算，計(jì)算時(shí)間為16·Tm+5·Ti；用戶(hù)P2執(zhí)行了10次乘法運(yùn)算和3次求逆運(yùn)算，計(jì)算時(shí)間為10·Tm+3·Ti。而在文獻(xiàn)［17］的方案中，用戶(hù)P1執(zhí)行了4次Paillier加/解密計(jì)算，計(jì)算時(shí)間為4·Tp；用戶(hù)P2執(zhí)行了4次Paillier加/解密計(jì)算，計(jì)算時(shí)間為4·Tp。文獻(xiàn)［6，7］兩個(gè)公鑰協(xié)同加密方案均使用了橢圓曲線(xiàn)上的點(diǎn)乘運(yùn)算和Paillier加/解密。因此本文方案在離線(xiàn)預(yù)計(jì)算階段是最優(yōu)的。

c）在線(xiàn)計(jì)算階段：在本文方案中，用戶(hù)P1和P2均執(zhí)行了1 536次乘法運(yùn)算和256次求逆運(yùn)算，計(jì)算時(shí)間都為1536·Tm+256·Ti。文獻(xiàn)［17］的方案中，用戶(hù)P1的計(jì)算時(shí)間為1536·Tm+256·Ti，用戶(hù)P2的計(jì)算時(shí)間為1792·Tm+256·Ti。文獻(xiàn)［6］的方案中，用戶(hù)P1和P2均執(zhí)行了1次Paillier加/解密計(jì)算。文獻(xiàn)［7］的方案中，用戶(hù)P1執(zhí)行了2次乘法運(yùn)算和1次求逆運(yùn)算，計(jì)算時(shí)間為2·Tm+1·Ti，用戶(hù)P2執(zhí)行了3次乘法運(yùn)算和1次求逆運(yùn)算，計(jì)算時(shí)間為3·Tm+1·Ti。文獻(xiàn)［22］中，用戶(hù)P1執(zhí)行了2次乘法運(yùn)算、1次點(diǎn)乘運(yùn)算、1次求逆運(yùn)算和1次零知識(shí)證明，用戶(hù)P2執(zhí)行了7次乘法運(yùn)算、1次點(diǎn)乘運(yùn)算、3次求逆運(yùn)算和1次零知識(shí)證明。文獻(xiàn)［7］所需計(jì)算時(shí)間最少。

d）全過(guò)程：在本文方案中，用戶(hù)P1的計(jì)算時(shí)間為1552·Tm+231·Ti，用戶(hù)P2的計(jì)算時(shí)間為1546·Tm+259·Ti。因?yàn)門(mén)p>>1792Tm，Tp>>259Ti，所以2·Tp>>1552·Tm+231·Ti>1546·Tm+259·Ti。文獻(xiàn)［6，7，17，22］中，用戶(hù)P1和P2的計(jì)算時(shí)間均大于2·Tp，本文所需計(jì)算時(shí)間最少，計(jì)算效率最高。

4.2 交互次數(shù)分析對(duì)比

本文方案和文獻(xiàn)［17］方案均為SM4協(xié)同加解密方案，兩方SM4協(xié)同加密一次過(guò)程中的交互次數(shù)對(duì)比如表3所示?？梢钥闯觯疚姆桨傅慕换ゴ螖?shù)略高于文獻(xiàn)［17］，但是在離線(xiàn)預(yù)計(jì)算階段，文獻(xiàn)［17］需要傳輸同態(tài)加密密文，由同態(tài)加密密文c=rNgm（mod N2）可知0<c<N2，而本文傳輸?shù)男畔⒋笮≡?～501。因此文獻(xiàn)［17］在離線(xiàn)預(yù)計(jì)算階段交互時(shí)發(fā)送的信息量高于本文方案。

4.3 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證本文的SM4協(xié)同加解密算法相比于文獻(xiàn)［17］更加高效，本文在模擬環(huán)境下對(duì)該算法和文獻(xiàn)［17］中的算法進(jìn)行相同條件下的測(cè)試，并對(duì)結(jié)果進(jìn)行分析比較。實(shí)驗(yàn)環(huán)境如表4所示。

在表4的實(shí)驗(yàn)環(huán)境下，對(duì)本文加密方案進(jìn)行實(shí)驗(yàn)驗(yàn)證，并與文獻(xiàn)［17］的方案進(jìn)行相同條件下的測(cè)試，從算法的加密執(zhí)行時(shí)間進(jìn)行分析比較。本文使用國(guó)家密碼管理局發(fā)布的SM4C語(yǔ)言代碼來(lái)實(shí)現(xiàn)SM4協(xié)同加解密，使用密碼數(shù)論庫(kù)（NTL）實(shí)現(xiàn)Paillier同態(tài)加密算法，選取Paillier同態(tài)加密算法的N為10 bit的3055358447，然后分別選取分割前的明文為0x0123436789abcdeffedcba9876543210，加密密鑰為0x012343-6789abcdeffedcba9876543210，分別用本文SM4協(xié)同加解密算法和文獻(xiàn)［17］中的方法進(jìn)行100次加密實(shí)驗(yàn)，對(duì)結(jié)果進(jìn)行整理分析，得到圖5所示的不同SM4協(xié)同加密單次執(zhí)行時(shí)間對(duì)比。

由圖5可知，相較于文獻(xiàn)［17］，本文方法在SM4協(xié)同加密執(zhí)行時(shí)間上具有較大優(yōu)勢(shì)。

5 結(jié)束語(yǔ)

本文提出了一種基于不經(jīng)意多項(xiàng)式估值協(xié)議的SM4協(xié)同加解密方案。在方案的安全性方面，將其規(guī)約到S盒協(xié)同計(jì)算的安全性，并通過(guò)基于模擬器的可證明安全方法證明了方案在半誠(chéng)實(shí)敵手模型下是安全的。在方案的性能方面，通過(guò)與現(xiàn)有的公鑰協(xié)同簽名方案、SM4協(xié)同加解密方案進(jìn)行對(duì)比分析，并進(jìn)行實(shí)驗(yàn)驗(yàn)證。相比之下，本文方案比現(xiàn)有的SM4協(xié)同加解密方案更高效，縮短了協(xié)同加解密執(zhí)行的時(shí)間。未來(lái)將進(jìn)一步考慮方案性能的優(yōu)化，同時(shí)也將研究其他對(duì)稱(chēng)密碼算法協(xié)同加解密構(gòu)造方案，并探索本文方案在電子投標(biāo)文件協(xié)同加解密中的應(yīng)用。

參考文獻(xiàn)：

［1］Lindell Y. Secure multiparty computation［J］. Communications of the ACM， 2020，64（1）： 86-96.

［2］Shamir A. How to share a secret［J］. Communications of the ACM， 1979， 22（11）： 612-613.

［3］MacKenzie P， Reiter M K. Two-party generation of DSA signatures［J］. International Journal of Information Security， 2004， 2： 218-239.

［4］Mu Yongheng， Xu Haixia， Li Peili， et al. Secure two-party SM9 signing［J］. Science China Information Sciences， 2020， 63： 1-3.

［5］涂彬彬， 王現(xiàn)方， 張立廷. 兩種分布式 SM2/9 算法應(yīng)用［J］. 密碼學(xué)報(bào)， 2020， 7（6）： 826-838. （Tu Binbin， Wang Xianfang， Zhang Liting. Application of two distributed SM2/9 algorithms［J］. Journal of Cryptography， 2020， 7（6）： 826-838.）

［6］Lindell Y. Fast secure two-party ECDSA signing［J］. Journal of Cryptology， 2021，34： 1-38.

［7］顏萌， 馬昌社. 高效的兩方ECDSA門(mén)限方案［J］. 華南師范大學(xué)學(xué)報(bào)： 自然科學(xué)版， 2022，54（4）： 121-128. （Yan Meng， Ma Changshe. An efficient threshold scheme for two-party ECDSA［J］. Journal of South China Normal University： Natural Science Edition， 2022，54（4）： 121-128.）

［8］嚴(yán)都力， 謝敏， 趙艷琦， 等. 抗差分故障攻擊的兩方協(xié)同EdDSA簽名方案［J］. 軟件學(xué)報(bào)， 2022， 34（2）： 915-931. （Yan Duli， Xie Min， Zhao Yanqi， et al. A two-party collaborative EdDSA signature scheme against differential fault attacks［J］. Journal of Software， 2023，34（2）： 915-931.）

［9］Doerner J， Kondi Y， Lee E， et al. Secure two-party threshold ECDSA from ECDSA assumptions［C］//Proc of IEEE Symposium on Security and Privacy. Piscataway，NJ： IEEE Press， 2018： 980-997.

［10］文嘉明， 王后珍， 劉金會(huì)， 等. Aitps： 基于非對(duì)稱(chēng)模格問(wèn)題的兩方協(xié)同簽名方案［J］. 計(jì)算機(jī)研究與發(fā)展， 2023，60（9）： 1-18. （Wen Jiaming， Wang Houzhen， Liu Jinhui， et al. Aitps： a two-party cooperative signature scheme based on asymmetric modular grid problem［J］. Journal of Computer Research and Development， 2023，60（9）： 1-18.）

［11］Xue Haiyang， Au M H， Xie Xiang， et al. Efficient online-friendly two-party ECDSA signature［C］//Proc of ACM SIGSAC Conference on Computer and Communications Security. New York： ACM Press， 2021： 558-573.

［12］Gennaro R， Goldfeder S， Narayanan A. Threshold-optimal DSA/ECDSA signatures and an application to bitcoin wallet security［C］//Proc of the 14th International Conference on Applied Cryptography and Network Security. Berlin： Springer， 2016： 156-174.

［13］Dttling N， Ghosh S， Nielsen J B， et al. TinyOLE： efficient actively secure two-party computation from oblivious linear function evaluation［C］//Proc of the 24th ACM SIGSAC Conference on Computer and Communications Security. New York： ACM Press， 2017： 2263-2276.

［14］楊博為， 孫達(dá)志， 李曉紅. 三方不經(jīng)意多項(xiàng)式求值協(xié)議［J］. 計(jì)算機(jī)工程與設(shè)計(jì)， 2016， 37（11）： 2934-2938. （Yang Bowei， Sun Dazhi， Li Xiaohong. Three-party oblivious polynomial evaluation protocol［J］. Computer Engineering and Design， 2016，37（11）： 2934-2938.）

［15］Cianciullo L， Ghodosi H. Efficient information theoretic multi-party computation from oblivious linear evaluation［C］//Proc of Internatio-nal Conference on Information Security Theory and Practice. Berlin： Springer， 2018： 78-90.

［16］Cianciullo L， Ghodosi H. Unconditionally secure oblivious polynomial evaluation： a survey and new results［J］. Journal of Computer Science and Technology， 2022，37（2）： 443-458.

［17］楊伊， 何德彪， 文義紅， 等. 密鑰管理服務(wù)系統(tǒng)下的多方協(xié)同SM4加/解密方案［J］. 信息網(wǎng)絡(luò)安全， 2021， 21（8）： 17-25. （Yang Yi， He Debiao， Wen Yihong， et al. Multi-party collaborative SM4 encryption/decryption scheme under key management service system［J］. Information Network Security， 2021，21（8）： 17-25.）

［18］呂克偉， 陳馳. Beaver三元組主動(dòng)性生成協(xié)議研究［J］. 信息網(wǎng)絡(luò)安全， 2022， 22（12）： 16-24. （Lyu Kewei， Chen Chi. Research on proactive generation protocol of Beaver triples［J］. Information Network Security， 2022，22（12）： 16-24.）

［19］Goldreich O. Foundations of cryptography： basic applications［M］. Cambridge： Cambridge University Press， 2004.

［20］中華人民共和國(guó)國(guó)家質(zhì)量監(jiān)督檢驗(yàn)檢疫總局. GB/T32907—2016， 信息安全技術(shù)SM4分組密碼算法［S］. 北京： 中國(guó)國(guó)家標(biāo)準(zhǔn)化管理委員會(huì)， 2016. （General Administration of Quality Supervision， Inspection and Quarantine of the People’s Republic of China. GB/T32907—2016， SM4 block cipher algorithm for information security technology［S］. Beijing： Standardization Administration of the People’s Republic of China， 2016.）

［21］Naor M， Pinkas B. Oblivious transfer with adaptive queries［C］//Proc of the 19th Annual International Cryptology Conference. Berlin： Springer， 1999： 573-590.

［22］彭金輝， 雷宗華， 張志鴻. ECDSA協(xié)同簽名方案設(shè)計(jì)與實(shí)現(xiàn)［J］. 信息安全研究， 2023， 9（11）： 1120-1130. （Peng Jinhui， Lei Zonghua， Zhang Zhihong. Design and implementation of ECDSA collaborative signature scheme［J］. Journal of Information Security Research， 2023，9（11）： 1120-1130.）