摘 要：現(xiàn)存的大多數(shù)可截取簽名方案具有公開驗(yàn)證性，但在某些情況下可能會導(dǎo)致簽名者的隱私泄露。為提高安全性，并使簽名方案具有抗量子性，基于理想格上的ring-SIS問題，結(jié)合強(qiáng)指定驗(yàn)證者簽名方案，提出一種新型的可截取簽名方案。該方案采用均勻采樣的異常中止技術(shù)，能夠抵抗側(cè)信道攻擊。同時(shí)，證明了該方案的安全性和正確性。相較于其他方案，該方案在安全性、重復(fù)次數(shù)和簽名尺寸等方面都表現(xiàn)出明顯的優(yōu)勢。

關(guān)鍵詞：可截取簽名； 強(qiáng)指定驗(yàn)證者簽名； 理想格； ring-SIS

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2024）10-038-3149-06

doi：10.19734/j.issn.1001-3695.2024.01.0011

Strongly specifying verifier’s interceptable signature scheme on ideal lattice

Wang Yu1， Chen Huiyan1， Wang Ke1， Xin Hongcai1， Wang Qingnan1， Yao Yunfei2

（1.Dept. of Electronic & Communication Engineering， Beijing Electronic Science & Technology Institute， Beijing 100070， China; 2.School of Cyberspace Security， Beijing University of Posts & Telecommunications， Beijing 100876， China）

Abstract：Most of the existing content extraction signature schemes publicly verify signatures， but in some cases， they may compromise the signer’s privacy. To enhance security and render the signature scheme resistant to quantum attacks， this paper proposed a new interceptable signature scheme based on the ring-SIS problem on the ideal lattice and integrated it with the strong specified verifier signature scheme. The scheme employed the anomaly abort technique of uniform sampling， capable of thwarting side-channel attacks. Additionally， this paper validated the security and correctness of the scheme. Compared to other schemes， this scheme exhibits clear advantages in security， number of repetitions， and signature size.

Key words：content extraction signature; strong designated verifier signature; ideal lattice; ring-SIS

0 引言

可截取簽名是指無須與簽名者互動的情況下，刪除已簽署數(shù)據(jù)中的敏感信息，并為截取后的數(shù)據(jù)生成有效簽名。2001年，Steinfeld等人［1］最先闡述了可截取簽名（content extraction signatures，CES）方案。2019年，文獻(xiàn)［2］結(jié)合可截取簽名提出了一種可被修改簽名方案，該方案提出修改容忍度的概念，擴(kuò)展了數(shù)字簽名方案的同時(shí)，還保證了可修改簽名的隱私。文獻(xiàn)［3］提出了一種前向安全的可截取簽名方案，通過固定公鑰，不斷變化私鑰的方式確保安全，但是依賴復(fù)雜的雙線性對運(yùn)算。2017年，Ma等人［4］提出具有細(xì)粒度單調(diào)修訂控制的可截取簽名方案。2019年，Liu 等人［5］提出門限型的可截取簽名方案，限制了可刪除數(shù)據(jù)塊數(shù)量的閾值。

指定驗(yàn)證者簽名（designated verifier signature，DVS）［6］是指只有被指定的驗(yàn)證者才有權(quán)驗(yàn)證簽名的正確性。然而，若簽名在傳遞至驗(yàn)證者之前被敵手截獲，敵手將獲悉簽名源自簽名者而非驗(yàn)證者。為了抵抗此類攻擊，1996年Jakobsson等人［7］第一次闡述強(qiáng)指定驗(yàn)證者簽名（strong designated verifier signatur，SDVS）。2003年，Saeednia等人［8］利用Schnorr簽名等方案設(shè)計(jì)了一個(gè)SDVS方案，該方案在簽名驗(yàn)證過程中結(jié)合了驗(yàn)證者的私鑰，從而滿足強(qiáng)指定驗(yàn)證者簽名方案的安全性要求。Wang等人［9］在2012年提出了第一個(gè)基于格的強(qiáng)指定驗(yàn)證者簽名方案。文獻(xiàn)［10］在2019年提出了一種高效的SDVS方案，該方案基于環(huán)上的小整數(shù)解（R-SIS）問題，并對其安全性進(jìn)行了證明。

格密碼具有抵抗量子計(jì)算攻擊、實(shí)現(xiàn)簡單高效等優(yōu)點(diǎn)，是目前應(yīng)用比較廣泛的后量子密碼之一。Goldreich等人［11］在1997年提出了基于格的數(shù)字簽名方案。此后，格簽名一直是數(shù)字簽名領(lǐng)域研究的熱點(diǎn)。特別是，在美國國家標(biāo)準(zhǔn)與技術(shù)研究院（National Institute of Standards and Technology，NIST）經(jīng)過三輪嚴(yán)格評選后，公布了首批三種后量子簽名標(biāo)準(zhǔn)算法［12］，基于格的方案占據(jù)兩個(gè)席位。

目前存在的可截取簽名方案，大多數(shù)都具備公開驗(yàn)證性，即所有拿到簽名的個(gè)體都有權(quán)利驗(yàn)證簽名的有效性，這在某些情況下會泄露簽名者的隱私［13］。而且由于現(xiàn)存的可截取簽名方案大多建立在傳統(tǒng)數(shù)論難題之上，所以不具備抵抗量子攻擊的能力。本文結(jié)合可截取簽名方案和強(qiáng)指定驗(yàn)證者簽名方案，在理想格上設(shè)計(jì)出一個(gè)強(qiáng)指定驗(yàn)證者的可截取簽名方案（ideal lattice-based strongly designated verifier extractable signature scheme，VES），不僅可以實(shí)現(xiàn)對數(shù)據(jù)的替換、刪除、整合等合理操作［14］，而且可以更好地保護(hù)簽名者的隱私，同時(shí)還具有抵抗量子攻擊的能力。VES在Fiat-Shamir簽名框架的基礎(chǔ)之上，結(jié)合均勻采樣的異常中止技術(shù)，相比于現(xiàn)有方案，在簽名尺寸、重復(fù)次數(shù)以及安全性等方面均具有較高的優(yōu)勢。此外，VES能夠抵抗側(cè)信道攻擊。

在基于區(qū)塊鏈的共享電子病歷系統(tǒng)中，由于區(qū)塊鏈中數(shù)據(jù)是公開的，如果直接上鏈存儲，會導(dǎo)致隱私泄露［15］。而且，患者去不同的醫(yī)院就醫(yī)時(shí)，希望透露的信息各不相同［16］。同時(shí)，為了更好地保護(hù)患者的隱私權(quán)，醫(yī)生查看電子病歷時(shí)需要向患者提出申請［17］。VES就可以很好地解決此類問題。比如患者A去醫(yī)院C就診，患者A可以提供歷史就診醫(yī)院B簽發(fā)的電子病歷。然而電子病歷中涵蓋了家庭住址、身份證號碼、聯(lián)系電話以及患者過往治療記錄等隱私信息，患者A不愿向醫(yī)院C透露家庭住址等信息。那么醫(yī)院B在簽發(fā)電子病歷時(shí)就可以使用VES進(jìn)行簽名。然后，患者A可以對電子病歷進(jìn)行適當(dāng)?shù)膭h改操作，然后將刪改后的文件及簽名提供給醫(yī)院C。在提出申請的醫(yī)生列表中，只有被患者A指定的醫(yī)生才有權(quán)解密此電子病歷。

1 預(yù)備知識

1.1 符號

表1給出本文中所使用的符號及其含義。

1.2 格與理想格

定義1 設(shè)B=b1，b2，…，bn是向量空間Euclid ExtraaBpm上n個(gè)線性無關(guān)的向量，則由B生成的格Λ定義為

Λ=Euclid Math OneLAp（B）={∑ni=1xibi：xi∈Euclid ExtrabBp}

其中：稱B為Λ的一組基。m表示格的維數(shù)，而n表示格的秩。當(dāng)m=n時(shí)，該格被稱為滿秩格。

定義2 設(shè)Euclid ExtrabBp［x］是全體整系數(shù)多項(xiàng)式構(gòu)成的多項(xiàng)式環(huán)，給定次數(shù)為n的分圓多項(xiàng)式f（x）∈Euclid ExtrabBp［x］，R=Euclid ExtrabBp［x］/（f（x））為分圓多項(xiàng)式環(huán)。給定素?cái)?shù)q=1 mod 2n，Rq=R/qR=Euclid ExtrabBpq［x］/（f（x））為模f（x）和q的整數(shù)多項(xiàng)式環(huán)。

本文所采用的多項(xiàng)式環(huán)均為R=Euclid ExtrabBp［x］/（xn+1），其中n取2的冪次。

定義3 標(biāo)準(zhǔn)格是由一組格基構(gòu)成的，而理想格充分使用了理想格基的循環(huán)性，一個(gè)主格基就可構(gòu)成。理想格與多項(xiàng)式環(huán)Euclid ExtrabBp［x］/f（x）相對應(yīng)。

定義4 設(shè)q是一個(gè)素?cái)?shù)，可以定義多項(xiàng)式環(huán)上模格如下：

Λq（a）={e∈Euclid ExtraaBpm，s.t. s∈Rq，s.t.aTs=e（mod q）}

Λ⊥q（a）={e∈Euclid ExtraaBpm，s.t. ae=0（mod q）}

Λuq（a）={e∈Euclid ExtraaBpm，s.t. ae=u（mod q）}

1.3 離散高斯分布

定義5 對任意正實(shí)數(shù)s，向量c∈Euclid ExtraaBpn，n維高斯函數(shù)定義為：ρ（x）=exp（-π（‖x-c‖/s）2），x∈Euclid ExtraaBpn。

定義6 對任意正實(shí)數(shù)s，向量c∈Euclid ExtraaBpn，n維格Λ上的離散高斯分布被定義為DΛ，s，c（x）=ρ（s，c）（x）ρ（s，c）（Λ），x∈Λ

1.4 ring-SIS

定義7 環(huán)上小整數(shù)解問題（ring shortest interger solution，ring-SISn，m，q，β）［18，19］。給定正整數(shù)m、q，實(shí)數(shù)β和向量a=（a1，a2，…，am）T∈Euclid ExtraaBpmq，找到一個(gè)小系數(shù)的非零多項(xiàng)式向量x=（x1，x2，…，xm）T∈Euclid ExtraaBpm，滿足

aT x=∑mi=1aixi=0 mod q

‖x‖∞≤β

若將環(huán)R變?yōu)檎麛?shù)Euclid ExtrabBp，則可以得到經(jīng)典SIS問題。與SIS 問題相比，ring-SIS問題因其獨(dú)特的多項(xiàng)式環(huán)結(jié)構(gòu)使得結(jié)構(gòu)更加緊湊，計(jì)算更加高效。

1.5 統(tǒng)計(jì)距離

定義8 假設(shè)X和Y是離散集合D上的兩個(gè)隨機(jī)變量，定義Δ（X，Y）=12∑x∈D|Pr［X=x］-Pr［Y=x］|為X和Y之間的統(tǒng)計(jì)距離。

對于任意的函數(shù)f，統(tǒng)計(jì)距離滿足Δ（f（X），f（Y））≤Δ（X，Y）［20］。

1.6 Filtering引理

引理1［21］ 令q=Ω（n），任意a∈{v∈Euclid ExtrabBpq：‖v‖∞≤A}，隨機(jī)選取b←{v∈Euclid ExtrabBpq：‖v‖∞≤B}，參數(shù)θ∈Euclid ExtraeBp+。如果B≥θqA，那么Pr［‖a-b‖∞≤B-A］>1e1/θ-o（1）。

Filtering引理的基本思想是為了確保簽名的安全性，生成簽名的長度必須在一個(gè)“安全區(qū)間”范圍內(nèi)，只有在這個(gè)范圍內(nèi)，簽名才能有效輸出，從而防止私鑰泄露的風(fēng)險(xiǎn)。在該“安全區(qū)間”內(nèi)生成的簽名要么與均勻分布不可區(qū)分，要么服從均勻分布。目前的簽名框架中，a-b一般是簽名，要使簽名落在“安全區(qū)間”內(nèi)需要重復(fù)1/（e1/θ）次。

1.7 拒絕采樣引理

引理2［22］ 設(shè)V是Euclid ExtrabBpm的一個(gè)子集，且任意v∈V都滿足‖v‖≤T。h是一個(gè)概率分布，可以將V映射到Euclid ExtraaBp。令ψ=ω（Tlog m）∈Euclid ExtraaBp，那么可以找到一個(gè)常數(shù)C，確保過程1、2輸出分布的統(tǒng)計(jì)距離最多為2-ω（log m）/C。

過程1：v←h，y←Euclid Math OneDApmψ，以1/C的概率輸出（z，y）。

過程2：v←h，y←Euclid Math OneDApmv，ψ，以min（Euclid Math OneDApmψ（z）CEuclid Math OneDApmv，ψ（z））的概率輸出（z，y）。

拒絕采樣引理提供了一種采用高斯采樣但是不泄露私鑰的方法。在此方案中，簽名需要以一定概率輸出，這個(gè)概率說明簽名與均勻分布不可區(qū)分，需要重復(fù)C次輸出的簽名才是安全的。

1.8 Fiat-Shamir簽名框架

Fiat-Shamir簽名框架分為運(yùn)用高斯采樣的拒絕抽樣引理和運(yùn)用均勻采樣的filtering引理兩種。下文簡單地介紹一下這兩類框架。

a）Fiat-Shamir簽名框架使用拒絕抽樣引理［22～25］，采用高斯采樣獲得臨時(shí)密鑰?；舅枷朐谟冢o定概率分布函數(shù)F，若能找到一個(gè)常數(shù)C以及另外一個(gè)分布函數(shù)G，確保定義域中所有x都滿足F（x）≤CG（x）。而要做到不泄露私鑰的話，則要求所有的x←G要以F（x）/CG（x）的概率輸出。由于高斯采樣不能抵抗側(cè)信道攻擊，所以本文主要采用均勻采樣構(gòu)造簽名方案。

b）Fiat-Shamir簽名框架使用filtering引理，采用均勻采樣獲得私鑰和臨時(shí)密鑰，從而達(dá)到保護(hù)私鑰的目的。這類框架［21，26～29］的主簽名為y=Ax+e，如果‖Ax‖∞≤β，‖e‖∞≤γ（其中x為哈希簽名值，e為臨時(shí)性密鑰，A為私鑰），只有輸出‖y‖∞≤γ-β范圍內(nèi)的簽名，才能保障私鑰不被泄露。也就是說，只有過濾性的輸出簽名，簽名才是安全的。

2 方案定義及安全模型

根據(jù)文獻(xiàn)［2］定義，可截取簽名中CEAS表示內(nèi)容截取訪問結(jié)構(gòu)，簽名人可以通過CEAS控制消息M的截取規(guī)則，從而防止惡意截取。假設(shè)規(guī)定截取者至少截取CEAS對應(yīng)的所有子消息，比如M={M［1］，M［2］，M［3］，M［4］，M［5］}，若令CI（M′）={1，2，3}，M′={M［1］，M［2］，M［3］，*，*}，滿足CEAS∈CI（M′），則截取方式合法；令CI（M′）={1，2，4，5}，M′={M［1］，M［2］，*，M［4］，M［5］}，使得CEASCI（M′），則截取方式不合法。CI（M）表示對M中非空數(shù)據(jù)塊的索引集合。

2.1 強(qiáng)指定驗(yàn)證者的可截取簽名方案

定義9 VES包含五個(gè)概率多項(xiàng)式時(shí)間算法：

a）密鑰生成算法KenGen（1n）。給定安全參數(shù)n，生成主公鑰A以及簽名者Alice和指定驗(yàn)證者Bob的公私鑰對（Ya，Sa）和（Yb，Sb）。

b）簽名算法Sign（Yb，Sa，M）。輸入消息M，指定驗(yàn)證者Bob的公鑰Yb和簽名者Alice的私鑰Sa，輸出消息M的簽名σ。

c）截取算法ESExt（M，σ，CEAS）。輸入消息M、簽名σ和截取規(guī)則CEAS，輸出截取消息M′和截取簽名σE。

d）驗(yàn)證算法Verify（A，Ya，Sb，σE）。輸入主公鑰A、簽名者Alice的公鑰Ya，指定驗(yàn)證者Bob的私鑰Sb和截取簽名σE，輸出“0”或“1”。其中“0”表示截取簽名σE無效，“1”表示截取簽名σE有效。

e）模擬算法Simulation（A，Ya，Sb，σ，M）。輸入主公鑰A、簽名者Alice的公鑰Ya，指定驗(yàn)證者Bob的私鑰Sb、簽名σ以及消息M，返回與簽名σ計(jì)算不可區(qū)分的簽名σ′。

VES的正確性。對所有有效的公私鑰對（Ya，Sa），（Yb，Sb）和消息M，有

a）全局簽名σ的正確性：Verify（A，Ya，Sb，M，Sign（Yb，Sa，M））=1。

b）截取簽名σE的正確性：Verify（A，Ya，Sb，M′，ESExt（M，Sign（Yb，Sa，M），CEAS））=1。

2.2 安全模型

一個(gè)安全的強(qiáng)指定驗(yàn)證者的可截取簽名方案，必須同時(shí)滿足正確性、不可偽造性、不可轉(zhuǎn)移性、匿名性以及隱私性的要求。除了正確性以外，其他性質(zhì)都是通過挑戰(zhàn)者Euclid Math OneCAp和PPT敵手Euclid Math OneAAp之間的游戲進(jìn)行刻畫的。下面給出具體的定義：

定義10 不可偽造性是指除簽名者Alice和指定驗(yàn)證者Bob外，其他任何人都不能偽造一個(gè)有效的數(shù)據(jù)簽名對。假設(shè)在PPT時(shí)間內(nèi)，如果可以忽略敵手Euclid Math OneAAp贏得下面游戲的概率，那么在適應(yīng)性選擇消息攻擊下，強(qiáng)指定驗(yàn)證者的可截取簽名方案具備不可偽造性（EUF-CMA）。下面給出游戲的詳細(xì)描述：

a）挑戰(zhàn)者Euclid Math OneCAp執(zhí)行密鑰生成算法，獲得公私鑰對（Ya，Sa）和（Yb，Sb），并將公鑰（Ya，Yb）發(fā)送給敵手Euclid Math OneAAp。

b）敵手Euclid Math OneAAp適應(yīng)性地選取q個(gè)消息{M1，M2，…，Mq}詢問簽名預(yù)言機(jī)，挑戰(zhàn)者Euclid Math OneCAp運(yùn)行簽名算法返還給敵手q個(gè)簽名。

c）敵手Euclid Math OneAAp在PPT時(shí)間內(nèi)根據(jù)自己獲取的知識，輸出偽造的數(shù)據(jù)簽名對（M，σ）。

d）如果數(shù)據(jù)簽名對（M，σ）在進(jìn)行簽名驗(yàn)證時(shí)滿足Verify（A，Ya，Sb，M，Sign（Yb，Sa，M））=1，并且Euclid Math OneAAp從未對消息M進(jìn)行過提取詢問，則本文認(rèn)為Euclid Math OneAAp贏得了上述游戲。

定義11 不可轉(zhuǎn)移性是指持有驗(yàn)證者公鑰的人都能夠模擬出一個(gè)和真正簽名難以區(qū)分的簽名。假設(shè)在PPT時(shí)間內(nèi)，如果可以忽略敵手Euclid Math OneAAp贏得下面游戲的概率，那么在適應(yīng)性選擇消息攻擊下，強(qiáng)指定驗(yàn)證者的可截取簽名方案具備不可轉(zhuǎn)移性。游戲的具體描述如下：

a）挑戰(zhàn)者Euclid Math OneCAp執(zhí)行密鑰生成算法，獲得公私鑰對（Ya，Sa）和（Yb，Sb），并將公鑰（Ya，Yb）發(fā)送給敵手Euclid Math OneAAp。

b）敵手Euclid Math OneAAp適應(yīng)性地選取q個(gè)消息{M1，M2，…，Mq}，詢問簽名預(yù)言機(jī)，挑戰(zhàn)者Euclid Math OneCAp運(yùn)行簽名算法返還給敵手q個(gè)簽名。

c）敵手Euclid Math OneAAp詢問一個(gè)新的消息M，挑戰(zhàn)者Euclid Math OneCAp通過擲幣隨機(jī)選取參數(shù)b∈{0，1}。如果b=0，則執(zhí)行簽名算法，返回簽名σ=Sign（Yb，Sa，M）；如果b=1，則執(zhí)行模擬算法，返回簽名σ=Simulation（A，Ya，Sb，σ，M）。

d）敵手Euclid Math OneAAp收到簽名σ后，可以繼續(xù)詢問除M之外的任何新的消息。

e）敵手Euclid Math OneAAp輸出b′，如果b′=b，敵手贏得游戲，轉(zhuǎn)移攻擊成功。

不可轉(zhuǎn)移性確保了指定驗(yàn)證者簽名的兩個(gè)重要特性：首先，只有持有驗(yàn)證者私鑰的個(gè)體才能夠驗(yàn)證簽名的正確性；其次，指定驗(yàn)證者無法向任何第三方證明簽名是由Alice生成的。

定義12 匿名性是指沒有私鑰的個(gè)體無法向任何第三方說明簽名的出處，即敵手不能區(qū)分簽名來自Alice和Bob還是Cindy和Bob。假設(shè)在PPT時(shí)間內(nèi)，如果可以忽略敵手Euclid Math OneAAp贏得下面游戲的概率，那么在適應(yīng)性選擇消息攻擊下，強(qiáng)指定驗(yàn)證者的可截取簽名方案具備匿名性。游戲的具體描述如下：

a）挑戰(zhàn)者Euclid Math OneCAp執(zhí)行密鑰生成算法，獲得公私鑰對（Ya0，Sa0）（Ya1，Sa1）和（Yb，Sb），并將公鑰（Ya0，Ya1，Yb）發(fā)送給敵手Euclid Math OneAAp。

b）敵手Euclid Math OneAAp詢問任意消息Mi的簽名。挑戰(zhàn)者Euclid Math OneCAp執(zhí)行σi=Sign（Yb，Sa0，Mi）或σi=Sign（Yb，Sa1，Mi）返回給敵手Euclid Math OneAAp。

c）敵手Euclid Math OneAAp詢問一個(gè)新的消息M，挑戰(zhàn)者Euclid Math OneCAp通過擲幣隨機(jī)選取參數(shù)b∈{0，1}。簽名σ=Sign（Yb，Sab，M）。

d）敵手Euclid Math OneAAp收到簽名σ后，可以繼續(xù)詢問除M之外的任何新的消息。

e）敵手Euclid Math OneAAp輸出b′，如果b′=b，敵手贏得游戲。

定義13 隱私性是指被截取的消息不會泄露完整信息。假設(shè)在PPT時(shí)間內(nèi)，如果可以忽略敵手Euclid Math OneAAp獲取已被刪除的信息的優(yōu)勢，那么在適應(yīng)性選擇消息攻擊下，強(qiáng)指定驗(yàn)證者可截取簽名方案具備可截取簽名隱私性。游戲的具體描述如下：

a）挑戰(zhàn)者Euclid Math OneCAp執(zhí)行密鑰生成算法，獲得公私鑰對（Ya，Sa）和（Yb，Sb），并將公鑰（Ya，Yb）發(fā)送給敵手Euclid Math OneAAp。

b）敵手Euclid Math OneAAp自適應(yīng)地詢問簽名，然后輸出（i，X，M0，M1）。其中，數(shù)據(jù)M0和M1除了索引i對應(yīng)的數(shù)據(jù)塊不同之外，其余均相同，并且iX。

c）挑戰(zhàn)者Euclid Math OneCAp隨機(jī)選取b∈{0，1}，令M=Mb，然后輸出關(guān)于消息Mb的截取簽名σE。最后，C將σE發(fā)送給敵手Euclid Math OneAAp。

d）敵手Euclid Math OneAAp繼續(xù)詢問簽名，然后輸出b′。若b′=b，則Euclid Math OneAAp成功，返回“1”；否則，Euclid Math OneAAp失敗，返回“0”。

3 方案描述

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

本文方案由以下五個(gè)算法構(gòu)成：

算法1 密鑰生成算法

輸入：安全參數(shù)n。

輸出：公鑰A、Ya、Yb；私鑰Sa、Sb。

a）私鑰Sa，Sb←Euclid Math OneDApm×md;

b）公鑰A，Ya，Yb∈Rm×mq，且滿足ASb=Yb mod q，ATSa=Ya mod q；

c）哈希函數(shù)h：{0，1}→{r：r∈{-1，0，1}m，‖r‖1≤η}。

算法2 簽名算法

輸入：公鑰A、Ya、Yb；私鑰Sa；消息M；標(biāo)簽f。

輸出：消息M的簽名σ=（r，z，t，f）。

a）選取可逆t←Euclid Math OneDApmγ（γ≤q）；

b）選取k←Euclid Math OneDApmγ，f［i］←{0，1}m；

c）c=YTbk mod q，g［i］=M［i］⊕f［i］，i=1，2，…，N，r=h（c，g［i］i∈N），z=Sar+kt-1；

d）輸出消息M的簽名σ=（r，z，t，f）。

算法3 截取算法

輸入：消息M；簽名σ=（r，z，t，f）；截取規(guī)則CEAS。

輸出：截取消息M′和截取簽名σE=（r，z，t，g［i］i∈［N］＼X， f［i］i∈X）。

a）對于不在截取規(guī)則內(nèi)的消息塊M［i］，i∈［N］/X，計(jì)算g［i］=M［i］⊕f［i］；

b）截取者根據(jù)截取規(guī)則CEAS和消息M，輸出截取消息M′和截取簽名σE=（r，z，t，g［i］i∈［N］＼X， f［i］i∈X）。

算法4 驗(yàn)證算法

輸入：公鑰A、Ya、Yb；私鑰Sb；簽名σE=（r，z，t，g［i］i∈［N］＼X，f［i］i∈X）；截取消息M′。

輸出：0或1。

a）對于i∈X，計(jì)算g［i］=M［i］⊕f［i］；

b）如果h（c，g）≠h（STb（ATz-Yar）t mod q，g），返回0；

c）如果‖z‖∞>γ-β，返回0；

d）其他情況返回1。

算法5 模擬算法

輸入：公鑰A、Ya、Yb；私鑰Sb；簽名σ=（r，z，t，f）；消息M。

輸出：與簽名σ計(jì)算不可區(qū)分的簽名σ′。

a）隨機(jī)選取z′和r′，其中‖z′‖∞≤γ-β，‖r′‖1≤η；

b）選取f［i］′←{0，1}m，計(jì)算z=z′t-1，r=r′t-1；

c）計(jì)算STb（ATz-Yar）t=c=c′=STb（ATz′-Yar′）mod q；

d）輸出σ′=（r′，z′，t′，f′）。

3.2 正確性證明

a）全局簽名σ的正確性驗(yàn)證。首先驗(yàn)證‖z′‖∞≤γ-β是否成立。其次，驗(yàn)證

ATz=AT（Sar+kt-1）=ATSar+ATkt-1=Yar+ATkt-1

STb（ATz-Yar）=STbATkt-1=YTbkt-1

h（STb（ATz-Yar）t mod q，g）=h（YTbk，g）=h（c，g）。

b）截取簽名σE的正確性驗(yàn)證。首先驗(yàn)證CEASCI（M′）。其次驗(yàn)證‖z′‖∞≤γ-β。對于i∈X，計(jì)算g［i］=M［i］⊕f［i］。最后，驗(yàn)證h（c，g）=h（STb（ATz-Yar）t mod q，g）。后續(xù)論證過程與a）相同。

3.3 安全性分析

定理1 若ring-SIS2n，m，q，β設(shè)論成立，則在適應(yīng)性選擇消息攻擊下，本文方案具備不可偽造性。

證明 假設(shè)敵手Euclid Math OneAAp能在PPT時(shí)間內(nèi)產(chǎn)生一個(gè)能通過驗(yàn)證的數(shù)據(jù)簽名對（M，σ），那么敵手Euclid Math OneAAp可以計(jì)算：

a）STb（ATz-Yar）t=（YTbz-STbYar）t mod q。

b）（YTbz-STbYar）t（t）-1-YTbz=

-STbYarmod q=-YTbSar mod q。

如果‖Sar‖≤β（0<β<mdη），那么就可以說敵手Euclid Math OneAAp得出了ring-SIS2n，m，q，β問題的解。這與ring-SIS2n，m，q，β問題的難解性矛盾。

定理2 在自適應(yīng)選擇消息攻擊下，本文設(shè)計(jì)的方案具備不可轉(zhuǎn)移性。

證明 下面介紹挑戰(zhàn)者Euclid Math OneCAp和敵手Euclid Math OneAAp間進(jìn)行的游戲Game。

a）系統(tǒng)建立。挑戰(zhàn)者Euclid Math OneCAp執(zhí)行密鑰生成算法，獲得公私鑰對（Ya，Sa）和（Yb，Sb），并將公鑰（Ya，Yb）發(fā)送給敵手Euclid Math OneAAp。

b）詢問階段。敵手Euclid Math OneAAp在PPT時(shí)間內(nèi)可以適應(yīng)性進(jìn)行以下幾種詢問。

（a）敵手Euclid Math OneAAp適應(yīng)性選擇消息Mi，進(jìn)行簽名詢問。挑戰(zhàn)者Euclid Math OneCAp運(yùn)行算法σi=Sign（Yb，Sa，Mi），發(fā)送給敵手Euclid Math OneAAp。

（b）敵手Euclid Math OneAAp詢問一個(gè)新的消息M，挑戰(zhàn)者Euclid Math OneCAp通過擲幣選取參數(shù)b∈{0，1}，如果b=0，則返回簽名σ=Sign（Yb，Sa，M）；如果b=1，則返回簽名σ=Simulation（A，Ya，Sb，σ，M）。

（c）敵手Euclid Math OneAAp繼續(xù)詢問挑戰(zhàn)者Euclid Math OneCAp除M之外的消息。

c）區(qū)分輸出。敵手Euclid Math OneAAp輸出猜想比特b′。

下面計(jì)算兩種算法輸出簽名的概率分布。假設(shè)σ1=（r1，z1，t1，f）是隨機(jī)選取的一個(gè)有效簽名。

簽名算法輸出的簽名概率分布為

Pr［（r，z，t，f）=（r1，z1，t1，f）］=

Prk，t≠0r=h（YTbk mod q，g［i］i∈N）=r1t=t1z=Sar+kt-1=z1=1γm（γm-1）

模擬算法輸出的簽名概率分布為

Pr［（r，z，t，f）=（r1，z1，t1，f）］=

Prk′，t′≠0r=h（STb（ATz′-Yar′），g［i］i∈N）=r1t=r′r-1=t1z=z′rr′-1=z1=

1γm（γm-1）

所以，兩種算法輸出的簽名概率分布一樣，即敵手Euclid Math OneAAp不能區(qū)分這兩種情況。

定理3 在自適應(yīng)選擇消息攻擊下，本文方案具備匿名性。

證明 設(shè)計(jì)一種挑戰(zhàn)者Euclid Math OneCAp和敵手Euclid Math OneAAp之間的交互游戲Game如下。

a）系統(tǒng)建立。挑戰(zhàn)者Euclid Math OneCAp執(zhí)行密鑰生成算法，獲得公私鑰對（Ya0，Sa0）、（Ya1，Sa1）和（Yb，Sb），并將公鑰（Ya0，Ya1，Yb）發(fā)送給敵手Euclid Math OneAAp。

b）詢問階段。敵手Euclid Math OneAAp在PPT時(shí)間內(nèi)可以適應(yīng)性進(jìn)行以下幾種詢問。

（a）敵手Euclid Math OneAAp對任意消息Mi進(jìn)行簽名詢問。挑戰(zhàn)者Euclid Math OneCAp通過計(jì)算σi=Sign（Yb，Sa0，Mi）或σi=Sign（Yb，Sa1，Mi）回答敵手簽名。

（b）敵手Euclid Math OneAAp詢問一個(gè)新的消息M，挑戰(zhàn)者Euclid Math OneCAp通過擲幣隨機(jī)選取參數(shù)b∈{0，1}。簽名σ=Sign（Yb，Sab，M）。

（c）敵手Euclid Math OneAAp繼續(xù)詢問挑戰(zhàn)者Euclid Math OneCAp除M之外的消息。

c）區(qū)分輸出。敵手Euclid Math OneAAp輸出猜想比特b′。

下面分析b′=b即敵手Euclid Math OneAAp成功的概率。

Pr［b=b′］=

|Pr［Euclid Math OneDAp（STb（ATz-Ya0r）t）］-Pr［Euclid Math OneDAp（STb（ATz-Ya1r）t）］|=

|Pr［Euclid Math OneDAp（STbYa0rt）］-Pr［Euclid Math OneDAp（STbYa1rt）］|=

|Pr［Euclid Math OneDAp（STbATSa0rt）］-Pr［Euclid Math OneDAp（STbATSa1rt）］|=

|Pr［Euclid Math OneDAp（YTbSa0rt）］-Pr［Euclid Math OneDAp（YTbSa1rt）］|

因為Sa0rt和Sa1rt是關(guān)于公鑰YTb的兩個(gè)不同的解。如果敵手Euclid Math OneAAp能區(qū)分ring-SISq，2n，m，β分布與均勻分布，那么敵手Euclid Math OneAAp就能區(qū)分ring-SISq，2n，m，β不同的解。

定理4 在自適應(yīng)選擇消息攻擊下，本文方案具備隱私性。

證明 下面介紹挑戰(zhàn)者Euclid Math OneCAp與敵手Euclid Math OneAAp間進(jìn)行的游戲Game0和Game1。

Game0的具體過程如下：

a）系統(tǒng)建立。挑戰(zhàn)者Euclid Math OneCAp執(zhí)行密鑰生成算法，獲得公私鑰對（Ya，Sa）和（Yb，Sb），并將公鑰（Ya，Yb）發(fā)送給敵手Euclid Math OneAAp。

b）詢問階段。敵手Euclid Math OneAAp進(jìn)行簽名詢問，并輸出（i，X，M0，M1）。其中，iX且M0［i］≠M(fèi)1［i］；對任意的i∈X，有M0［i］=M1［i］。挑戰(zhàn)者Euclid Math OneCAp隨機(jī)選取b∈{0，1}，令M=Mb。當(dāng)i∈［N］，計(jì)算g［i］=M［i］⊕f［i］和數(shù)據(jù)M的簽名σ=（r，z，t， f）。其次，挑戰(zhàn)者Euclid Math OneCAp執(zhí)行截取算法，生成數(shù)據(jù)對（M，X）截取后的簽名σE=（r，z，t，g［i］i∈［N］＼X， f［i］i∈X ）。最后，挑戰(zhàn)者Euclid Math OneCAp將（〈M〉i∈X，σE）發(fā)送給敵手Euclid Math OneAAp。

c）區(qū)分輸出。敵手Euclid Math OneAAp輸出猜想比特b′。若b′=b，輸出1；否則，返回0。

Game1在Game0的基礎(chǔ)上改變挑戰(zhàn)階段，具體過程如下：

挑戰(zhàn)者Euclid Math OneCAp首先設(shè)置M。當(dāng)i∈X，令M［i］=M0［i］=M1［i］，即〈M〉i∈X=〈M0〉i∈X=〈M1〉i∈X；當(dāng)i∈［N］＼X，令M［i］=；其次，當(dāng)i∈X，計(jì)算g［i］=M［i］⊕f［i］；當(dāng)i∈［N］＼X，計(jì)算簽名σ=（r，z，t，f）。最后，挑戰(zhàn)者Euclid Math OneCAp輸出截取簽名（〈M〉i∈X，σE）。

下面分析敵手Euclid Math OneAAp成功的概率：

根據(jù)游戲的設(shè)置可知，在Game0和Game1中，有〈M〉i∈X=〈M0〉i∈X=〈M1〉i∈X。因此，M被截取的部分未泄露未被截取部分的數(shù)據(jù)。

總體來看，在自適應(yīng)選擇消息攻擊下，本文簽名方案具備隱私性。

4 比較分析

本文選取四種可截取簽名方案以及兩種強(qiáng)指定驗(yàn)證者簽名方案進(jìn)行比較分析，如表2所示。

首先是VES與四種可截取簽名方案之間的對比分析。在安全模型方面，文獻(xiàn)［4，5，7，10］均為EUF-CMA，在自適應(yīng)選擇消息攻擊下不能滿足不可偽造性，也無法有效抵抗量子攻擊。并且，對于可截取簽名而言，需要具備隱私性和不可偽造性這兩個(gè)基本的要求，而文獻(xiàn)［4，7］沒有給出簽名的隱私性證明。相比之下，VES不僅滿足可截取簽名的隱私性和不可偽造性，還具備抗量子攻擊能力，安全性更高。

然后是VES與兩種強(qiáng)指定驗(yàn)證者簽名方案之間的對比分析。由于文獻(xiàn)［9，30］兩個(gè)方案不具備可截取簽名的性質(zhì)，所以不支持對數(shù)據(jù)的替換、刪除、整合等合理操作，具有一定的局限性。而且文獻(xiàn)［15，16］兩個(gè)強(qiáng)指定驗(yàn)證者簽名方案必須選擇較大的參數(shù)來使用原像采樣函數(shù)和高斯采樣，這在一定程度上導(dǎo)致了簽名尺寸的增加，重復(fù)次數(shù)也會隨著高斯采樣的次數(shù)增加而增加。由于本文方案是基于均勻采樣的R-SIS假設(shè)，所以VES的簽名尺寸和重復(fù)次數(shù)都優(yōu)于其他方案。

另外，VES建立在R-SIS問題之上，環(huán)上的n次多項(xiàng)式可以生成隨機(jī)矩陣，且可以用NTT技術(shù)加速實(shí)現(xiàn)特定環(huán)上的多項(xiàng)式乘法，實(shí)現(xiàn)效率更高。而且，VES在一定程度上可以抵抗側(cè)信道攻擊。綜上，VES在簽名尺寸、公鑰長度以及實(shí)現(xiàn)效率上均具有明顯優(yōu)勢。

5 結(jié)束語

本文提出理想格上強(qiáng)指定驗(yàn)證者的可截取簽名方案，充分利用了多項(xiàng)式環(huán)結(jié)構(gòu)更加緊湊和格密碼的抗量子攻擊、便捷高效等特點(diǎn)，并給出安全性證明。 由于可截取簽名支持對完整簽名進(jìn)行截取操作，并且驗(yàn)證者不需要同簽名人進(jìn)行交互即可驗(yàn)證簽名的真?zhèn)?，拓寬了傳統(tǒng)數(shù)字簽名的應(yīng)用場景。 強(qiáng)指定驗(yàn)證者的可截取簽名解決了數(shù)字簽名的公開驗(yàn)證問題，相比于普通可截取簽名安全等級進(jìn)一步提高。 今后，將進(jìn)一步考慮將可截取簽名方案推廣到格上其他困難問題以及基于屬性的認(rèn)證方式等，亦或是結(jié)合其他截取控制規(guī)則構(gòu)造出更加高效的簽名方案。

參考文獻(xiàn)：

［1］Steinfeld R， Bull L， Zheng Yuliang. Content extraction signatures［C］//Proc of the 4th International Conference on Information Security and Cryptology. Berlin： Springer， 2002： 285-304.

［2］李旭， 杜小妮， 王彩芬， 等. 基于RSA的可截取簽名改進(jìn)方案［J］. 計(jì)算機(jī)工程與應(yīng)用， 2014， 50（24）： 96-99. （Li Xu， Du Xiao-ni， Wang Caifen， et al. Improved scheme of content extraction signatures based on RSA［J］. Computer Engineering and Applications， 2014， 50（24）： 96-99.）

［3］Wang Caifen， Li Yahong， Huang S Y， et al. A new forward secure content extraction signature scheme［C］//Proc of 12th International Conference on Fuzzy Systems and Knowledge Discovery. Piscataway， NJ： IEEE Press， 2015： 1698-1702.

［4］Ma Jinhua， Liu Jianghua， Huang Xinyi， et al. Authenticated data reduction with fine-grained control［J］. IEEE Trans on Emerging Topics in Computing， 2020， 8（2）： 291-302.

［5］Liu Jianghua， Ma Jinhua， Xiang Yang， et al. Authenticated medical documents releasing with privacy protection and release control［J］. IEEE Trans on Dependable and Secure Computing， 2021，18（1）： 448-459.

［6］李明祥， 鄭艷娟， 許明. 格基強(qiáng)指定驗(yàn)證者簽名方案［J］. 小型微型計(jì)算機(jī)系統(tǒng)， 2013， 34（10）： 4. （Li Mingxiang， Zheng Yanjuan， Xu Ming. Gejiqiang specifies the verifier signature scheme［J］. Small and Micro Computer Systems， 2013， 34（10）： 4.）

［7］Jakobsson M， Sako K， Impagliazzo R. Designated verifier proofs and their applications［C］//Proc of the 15th Annual International Confe-rence on Theory and Application of Cryptographic Techniques. Heidelberg： Springer-Verlag， 1996： 143-154.

［8］Saeednia S， Kpemer S， Markowitch O. An efficient strong designated verifier signature scheme［C］//Procs of the 6th International Confe-rence on Information Security and Cryptology. Berlin： Springer， 2003： 40-54.

［9］Wang Fenghe， Hu Yupu， Wang Baocang. Lattice-based strong designate verifier signature and its applications［J］. Malaysian Journal of Computer Science， 2012， 25（1）： 11-22.

［10］Jie Cai， Han Jiang， Zhang Pingyuan， et al. An efficient strong designated verifier signature based on R-SIS assumption［J］. IEEE Access， 2019， 7： 3938-3947.

［11］Goldreich O， Goldwasser S， Halevl S. Public-key crypto-systems from lattice reduction problems［C］//Proc of the 17th Annual International Cryptology Conference on Advances in Cryptology. Berlin： Springer， 1997： 112-131.

［12］NIST. NIST announces first four quantum-resistant crypto-graphic-algorithms［EB/OL］. （2022-07-05）. https：//www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms.

［13］李元曉， 周彥偉， 楊波. 一個(gè)改進(jìn)的強(qiáng)指定驗(yàn)證者簽密方案［J］. 計(jì)算機(jī)應(yīng)用研究， 2020， 37（2）： 518-520，534. （Li Yuanxiao， Zhou Yanwei， Yang Bo. Improved strong designated verifier signcryption scheme［J］. Applied Research of Computers， 2020， 37（2）： 518-520，534.）

［14］趙勇， 楊少軍， 張福泰， 等. 基于格的可截取簽名方案［J］. 密碼學(xué)報(bào)， 2022， 9（4）： 767-778. （Zhao Yong， Yang Shaojun， Zhang Futai， et al. A lattice-based extraction signature scheme［J］. Journal of Cryptologic Research， 2022， 9（4）： 767-778.）

［15］馮夢迪. 基于區(qū)塊鏈的電子病歷系統(tǒng)的研究與實(shí)現(xiàn)［D］. 沈陽： 遼寧大學(xué)， 2023. （Feng Mengdi. Research and implementation of blockchain-based electronic medical record system［D］. Shenyang： Liaoning University， 2023.）

［16］李曉璐. 基于區(qū)塊鏈的電子病歷共享及隱私保護(hù)研究［D］. 西安： 西安電子科技大學(xué)， 2019. （Li Xiaolu. Research on electronic medical record sharing and privacy protection based on blockchain［D］. Xi’an： Xidian University， 2019.）

［17］李亞輝. 基于區(qū)塊鏈的電子病歷共享系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［D］. 杭州： 浙江大學(xué)， 2021. （Li Yahui. Design and implementation of electronic medical record sharing system based on blockchain［D］. Hangzhou： Zhejiang University， 2021.）

［18］Lyubashevsky V， Micciancio D. Generalized compact knap-sacks are collision resistant［M］//Bugliesi M， Preneel B， Sassone V， et al. Automata， languages and programming. Berlin： Springer-Verlag， 2006： 144-155.

［19］Peikert C， Rosen A. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices［M］//Halevi S， Rabin T. Theory of Cryptography. Berlin： Springer， 2006： 145-166.

［20］王鳳和. 后量子安全的格公鑰密碼設(shè)計(jì)［D］. 西安： 西安電子科技大學(xué)， 2014. （Wang Fenghe. Design of lattice public-key crypto-graphy for post-quantum security［D］. Xi’an： Xidian University， 2014.）

［21］Markus R. Lattice-based blind signatures［C］//Proc of the 16th International Conference on the Theory and Application of Cryptology and Information Security. Berlin： Springer， 2010： 413-430.

［22］Vadim L. Lattice signatures without trapdoors［C］//Proc of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2012： 738-755.

［23］Leo D， Tancrede L， Vadim L， et al. Crystals-dilithium： digital signatures from module lattices［EB/OL］. （2018-09-10）. https：//eprint.iacr.org/2017/633.

［24］Leo D. Accelerating bliss： the geometry of ternary poly-nomials［EB/OL］. （2014-10-22）. https：//ia.cr/2014/874.

［25］Leo D， Alain D， Tancrede L， et al. Lattice signatures and bimodal Gaussians［C］//Proc of the 33rd Annual International Cryptology Conference. Berlin： Springer， 2013： 40-56.

［26］Thomas P， Leo D， Tim G. Enhanced lattice-based signatures on reconfigurable hardware［C］//Proc of the 16th International Workshop on Cryptographic Hardware and Embedded Systems. Berlin： Springer， 2014： 353-370.

［27］Erdem A， Nina B， Johannes B， et al. Revisiting TESLA in the quantum random oracle model［C］//Proc of the 8th International Workshop on Post-Quantum Cryptography. Cham： Springer， 2017： 143-162.

［28］Shi Bai， Galbraith S D. An improved compression technique for signatures based on learning with errors［M］//Benaloh J. Topics in Cryptology. Cham： Springer， 2014： 28-47.

［29］Vadim L. Fiat-shamir with aborts： applications to lattice and factoring-based signatures［C］//Proc of the 15th International Conference on the Theory and Application of Cryptology and Information Security. Berlin： Springer， 2009： 598-616.

［30］Geontae N， Ik R. Strong designated verifier signature scheme from lattices in the standard model［J］. Security and Communication Networks， 2017， 9（18）： 6202-6214.

［31］蔡杰. 基于格的指定驗(yàn)證者數(shù)字簽名方案及身份鑒別協(xié)議研究［D］. 濟(jì)南： 山東大學(xué)， 2020. （Cai Jie. Research on lattice based designated validator digital signature scheme and identity authentication protocol［D］. Jinan： Shandong University， 2020.）

［32］張平， 遲歡歡， 李金波， 等. 基于格的強(qiáng)指定驗(yàn)證者簽名方案［J］. 北京航空航天大學(xué)學(xué)報(bào)， 2023， 49（6）： 1294-1300. （Zhang Ping， Chi Huanhuan， Li Jinbo， et al. Lattice-based strongly designated verifier signature scheme［J］. Journal of Beijing University of Aeronautics and Astronautics， 2023， 49（6）： 1294-1300.）