理想格上強指定驗證者的可截取簽名方案

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

關鍵詞：可截取簽名； 強指定驗證者簽名； 理想格； ring-SIS

中圖分類號：TP391 文獻標志碼：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 引言

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

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

格密碼具有抵抗量子計算攻擊、實現簡單高效等優點，是目前應用比較廣泛的后量子密碼之一。Goldreich等人［11］在1997年提出了基于格的數字簽名方案。此后，格簽名一直是數字簽名領域研究的熱點。特別是，在美國國家標準與技術研究院（National Institute of Standards and Technology，NIST）經過三輪嚴格評選后，公布了首批三種后量子簽名標準算法［12］，基于格的方案占據兩個席位。

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

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

1 預備知識

1.1 符號

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

1.2 格與理想格

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

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

其中：稱B為Λ的一組基。m表示格的維數，而n表示格的秩。當m=n時，該格被稱為滿秩格。

定義2 設Euclid ExtrabBp［x］是全體整系數多項式構成的多項式環，給定次數為n的分圓多項式f（x）∈Euclid ExtrabBp［x］，R=Euclid ExtrabBp［x］/（f（x））為分圓多項式環。給定素數q=1 mod 2n，Rq=R/qR=Euclid ExtrabBpq［x］/（f（x））為模f（x）和q的整數多項式環。

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

定義3 標準格是由一組格基構成的，而理想格充分使用了理想格基的循環性，一個主格基就可構成。理想格與多項式環Euclid ExtrabBp［x］/f（x）相對應。

定義4 設q是一個素數，可以定義多項式環上模格如下：

Λ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 對任意正實數s，向量c∈Euclid ExtraaBpn，n維高斯函數定義為：ρ（x）=exp（-π（‖x-c‖/s）2），x∈Euclid ExtraaBpn。

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

1.4 ring-SIS

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

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

‖x‖∞≤β

若將環R變為整數Euclid ExtrabBp，則可以得到經典SIS問題。與SIS 問題相比，ring-SIS問題因其獨特的多項式環結構使得結構更加緊湊，計算更加高效。

1.5 統計距離

定義8 假設X和Y是離散集合D上的兩個隨機變量，定義Δ（X，Y）=12∑x∈D|Pr［X=x］-Pr［Y=x］|為X和Y之間的統計距離。

對于任意的函數f，統計距離滿足Δ（f（X），f（Y））≤Δ（X，Y）［20］。

1.6 Filtering引理

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

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

1.7 拒絕采樣引理

引理2［22］ 設V是Euclid ExtrabBpm的一個子集，且任意v∈V都滿足‖v‖≤T。h是一個概率分布，可以將V映射到Euclid ExtraaBp。令ψ=ω（Tlog m）∈Euclid ExtraaBp，那么可以找到一個常數C，確保過程1、2輸出分布的統計距離最多為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）。

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

1.8 Fiat-Shamir簽名框架

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

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

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

2 方案定義及安全模型

根據文獻［2］定義，可截取簽名中CEAS表示內容截取訪問結構，簽名人可以通過CEAS控制消息M的截取規則，從而防止惡意截取。假設規定截取者至少截取CEAS對應的所有子消息，比如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中非空數據塊的索引集合。

2.1 強指定驗證者的可截取簽名方案

定義9 VES包含五個概率多項式時間算法：

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

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

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

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

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

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 安全模型

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

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

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

b）敵手Euclid Math OneAAp適應性地選取q個消息{M1，M2，…，Mq}詢問簽名預言機，挑戰者Euclid Math OneCAp運行簽名算法返還給敵手q個簽名。

c）敵手Euclid Math OneAAp在PPT時間內根據自己獲取的知識，輸出偽造的數據簽名對（M，σ）。

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

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

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

b）敵手Euclid Math OneAAp適應性地選取q個消息{M1，M2，…，Mq}，詢問簽名預言機，挑戰者Euclid Math OneCAp運行簽名算法返還給敵手q個簽名。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 方案描述

3.1 方案設計

本文方案由以下五個算法構成：

算法1 密鑰生成算法

輸入：安全參數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）哈希函數h：{0，1}→{r：r∈{-1，0，1}m，‖r‖1≤η}。

算法2 簽名算法

輸入：公鑰A、Ya、Yb；私鑰Sa；消息M；標簽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）；截取規則CEAS。

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

a）對于不在截取規則內的消息塊M［i］，i∈［N］/X，計算g［i］=M［i］⊕f［i］；

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

算法4 驗證算法

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

輸出：0或1。

a）對于i∈X，計算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。

輸出：與簽名σ計算不可區分的簽名σ′。

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

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

c）計算STb（ATz-Yar）t=c=c′=STb（ATz′-Yar′）mod q；

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

3.2 正確性證明

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

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的正確性驗證。首先驗證CEASCI（M′）。其次驗證‖z′‖∞≤γ-β。對于i∈X，計算g［i］=M［i］⊕f［i］。最后，驗證h（c，g）=h（STb（ATz-Yar）t mod q，g）。后續論證過程與a）相同。

3.3 安全性分析

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

證明 假設敵手Euclid Math OneAAp能在PPT時間內產生一個能通過驗證的數據簽名對（M，σ），那么敵手Euclid Math OneAAp可以計算：

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 在自適應選擇消息攻擊下，本文設計的方案具備不可轉移性。

證明 下面介紹挑戰者Euclid Math OneCAp和敵手Euclid Math OneAAp間進行的游戲Game。

a）系統建立。挑戰者Euclid Math OneCAp執行密鑰生成算法，獲得公私鑰對（Ya，Sa）和（Yb，Sb），并將公鑰（Ya，Yb）發送給敵手Euclid Math OneAAp。

b）詢問階段。敵手Euclid Math OneAAp在PPT時間內可以適應性進行以下幾種詢問。

（a）敵手Euclid Math OneAAp適應性選擇消息Mi，進行簽名詢問。挑戰者Euclid Math OneCAp運行算法σi=Sign（Yb，Sa，Mi），發送給敵手Euclid Math OneAAp。

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

（c）敵手Euclid Math OneAAp繼續詢問挑戰者Euclid Math OneCAp除M之外的消息。

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

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

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

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不能區分這兩種情況。

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

證明 設計一種挑戰者Euclid Math OneCAp和敵手Euclid Math OneAAp之間的交互游戲Game如下。

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

b）詢問階段。敵手Euclid Math OneAAp在PPT時間內可以適應性進行以下幾種詢問。

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

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

（c）敵手Euclid Math OneAAp繼續詢問挑戰者Euclid Math OneCAp除M之外的消息。

c）區分輸出。敵手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是關于公鑰YTb的兩個不同的解。如果敵手Euclid Math OneAAp能區分ring-SISq，2n，m，β分布與均勻分布，那么敵手Euclid Math OneAAp就能區分ring-SISq，2n，m，β不同的解。

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

證明 下面介紹挑戰者Euclid Math OneCAp與敵手Euclid Math OneAAp間進行的游戲Game0和Game1。

Game0的具體過程如下：

a）系統建立。挑戰者Euclid Math OneCAp執行密鑰生成算法，獲得公私鑰對（Ya，Sa）和（Yb，Sb），并將公鑰（Ya，Yb）發送給敵手Euclid Math OneAAp。

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

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

Game1在Game0的基礎上改變挑戰階段，具體過程如下：

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

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

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

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

4 比較分析

本文選取四種可截取簽名方案以及兩種強指定驗證者簽名方案進行比較分析，如表2所示。

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

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

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

5 結束語

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

參考文獻：

［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］. 計算機工程與應用， 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］李明祥， 鄭艷娟， 許明. 格基強指定驗證者簽名方案［J］. 小型微型計算機系統， 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］李元曉， 周彥偉， 楊波. 一個改進的強指定驗證者簽密方案［J］. 計算機應用研究， 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］. 密碼學報， 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］馮夢迪. 基于區塊鏈的電子病歷系統的研究與實現［D］. 沈陽： 遼寧大學， 2023. （Feng Mengdi. Research and implementation of blockchain-based electronic medical record system［D］. Shenyang： Liaoning University， 2023.）

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

［17］李亞輝. 基于區塊鏈的電子病歷共享系統的設計與實現［D］. 杭州： 浙江大學， 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］王鳳和. 后量子安全的格公鑰密碼設計［D］. 西安： 西安電子科技大學， 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］蔡杰. 基于格的指定驗證者數字簽名方案及身份鑒別協議研究［D］. 濟南： 山東大學， 2020. （Cai Jie. Research on lattice based designated validator digital signature scheme and identity authentication protocol［D］. Jinan： Shandong University， 2020.）

［32］張平， 遲歡歡， 李金波， 等. 基于格的強指定驗證者簽名方案［J］. 北京航空航天大學學報， 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.）