一種理想格上高效盲簽名方案

摘 要：為了更好地保護(hù)用戶隱私安全，使簽名具有抗量子性，使用拒絕抽樣定理以及高低順序位關(guān)系提出了一種理想格上安全高效的盲簽名方案。該方案無(wú)須復(fù)雜的陷門函數(shù)，通過(guò)簡(jiǎn)單的計(jì)算即可實(shí)現(xiàn)盲簽名功能。通過(guò)分析可知，該方案安全性規(guī)約于格上ISIS_n，m，q，η（s）困難問(wèn)題，具有盲性以及one-more（OM）不可偽造性，且公私鑰短，簽名長(zhǎng)度僅為llodq，具有安全高效的優(yōu)勢(shì)。

關(guān)鍵詞：隱私安全；盲簽名；理想格；高低位關(guān)系；拒絕抽樣定理

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

文章編號(hào)：1001-3695（2022）11-042-3461-04

doi：10.19734/j.issn.1001-3695.2022.04.0196

Efficient blind signature scheme on ideal lattice

Huang Xiuju^a，Du Yunfei^b，Li Zichen^a

（a.School of Information Engineering，b.School of Basic Education，Beijing Institute of Graphic Communication，Beijing 102600，China）

Abstract：In order to protect users’ privacy better and make signatures resistant to quantum attack，this paper proposed a secure and efficient blind signature scheme on ideal lattice by using the rejection sampling theorem and the relationship between high and low order bits.This blind signature function could be achieved through simple calculations without trapdoor functions.The security of the scheme is based on short integer solution（ISIS_n，m，q，η（s）） assumption，and this scheme has the characte-ristics of blindness and one-more （OM） unforgeability.Besides，the public and private keys are short and the signature length is only llodq.In general，the scheme is efficient and safe.

Key words：privacy security；blind signature；ideal lattice；high and low bit relation；rejection sampling theorem

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61370188）；北京市教委科研計(jì)劃資助項(xiàng)目（KM202010015009，KM202110015004）；北京印刷學(xué)院博士啟動(dòng)金資助項(xiàng)目（27170120003/020）；北京印刷學(xué)院科研創(chuàng)新團(tuán)隊(duì)項(xiàng)目（Eb202101）；北京印刷學(xué)院校內(nèi)學(xué)科建設(shè)項(xiàng)目（21090121021）；北京印刷學(xué)院重點(diǎn)教改項(xiàng)目（22150121033/009）；北京印刷學(xué)院科研基礎(chǔ)研究一般項(xiàng)目（Ec202201）；北京市教育委員會(huì)科技一般項(xiàng)目（KM202110015001）

作者簡(jiǎn)介：黃秀菊（1994-），女，河北滄州人，碩士研究生，主要研究方向?yàn)槊艽a學(xué)、數(shù)字簽名、格密碼、隱私計(jì)算；杜云飛，男，河南新鄉(xiāng)人，講師，博士，主要研究方向?yàn)閼?yīng)用數(shù)學(xué)、密碼學(xué)；李子臣（1965-），男（通信作者），河南人，教授，博導(dǎo)，博士，主要研究方向?yàn)樾畔踩?shù)字水印、數(shù)字簽名、密碼學(xué)（lizc2020@163.com）．

0 引言

1982年，Chaum^［1］首次提出盲簽名概念，并設(shè)計(jì)了一種不可追蹤交易方式。盲簽名要求簽名者對(duì)盲化后信息進(jìn)行簽名，用戶去盲處理后可得到對(duì)應(yīng)信息的簽名，從而保護(hù)了簽名信息。在不知道盲化因子的前提下簽名者找不到盲化信息與信息的關(guān)系，且對(duì)于去盲后簽名，簽名者不知什么時(shí)候進(jìn)行的簽名，且其他人無(wú)法偽造簽名，因此盲簽名具有盲性與OM-不可偽造性，被廣泛應(yīng)用于電子投票^［2，3］、電子現(xiàn)金^［4，5］等場(chǎng)景。1994年，Camenish等人^［6］提出了第一個(gè)基于離散對(duì)數(shù)的盲簽名方案。自此，許多基于離散對(duì)數(shù)問(wèn)題，整數(shù)分解問(wèn)題的盲簽名方案被大量提出^［7，8］。隨著盲簽名發(fā)展，盲簽名擴(kuò)展概念被提出，比如1998年，Lysyanskaya等人^［9］提出群盲簽名概念，把盲簽名與群簽名巧妙結(jié)合在一起，可以應(yīng)用到多銀行共同開發(fā)電子現(xiàn)金等場(chǎng)景。1996年，Abe等人^［10］提出了部分盲簽名的概念，解決了完全盲簽名被非法使用等問(wèn)題。2000年，Lin等人^［11］將代理簽名和盲簽名相結(jié)合首次提出代理盲簽名。這些概念的提出豐富了盲簽名使用場(chǎng)景，使得盲簽名發(fā)揮出重要功能。

量子計(jì)算機(jī)的發(fā)展使得基于經(jīng)典數(shù)論問(wèn)題的盲簽名方案面臨挑戰(zhàn)，其安全性將被降低，大量基于格的抗量子密碼算法被提出^{［12～14］}。2010年，Rückert^［15］利用原像抽樣單向函數(shù)提出了第一個(gè)格盲簽名方案，其安全性依賴于ISVP問(wèn)題，且簽名可能失敗。隨后，王鳳和等人^［16］也利用原像抽樣函數(shù)構(gòu)造一個(gè)輪最優(yōu)的盲簽名算法，僅通過(guò)兩輪即可實(shí)現(xiàn)盲簽名方案，且性能高于文獻(xiàn)［15］，滿足盲性與不可偽造性。2017年，文獻(xiàn)［17］使用原像抽樣算法與格基派生算法，通過(guò)相應(yīng)地構(gòu)造減少交互次數(shù)，僅需要兩輪即可生成盲簽名，但同時(shí)格上陷門生成以及派生過(guò)程會(huì)增加計(jì)算開銷。2018年，文獻(xiàn)［18］ 基于UTRN提出了一種基于身份的抗量子盲簽名方案，使用拒絕抽樣定理保障簽名密鑰的安全性，具有高效、密鑰緊湊的優(yōu)勢(shì)，且稱其在隨機(jī)預(yù)言機(jī)上是安全的。2020年，文獻(xiàn)［19］找出了文獻(xiàn)［18］的一個(gè)安全漏洞，并在文獻(xiàn)［18］的基礎(chǔ)上進(jìn)行改進(jìn)與完善。2021年，Li等人^［20］提出了一種基于區(qū)塊鏈系統(tǒng)的格上盲簽名，該方案使用雙峰高斯抽樣以及拒絕抽樣定理，提高了簽名成功的概率，具有盲性以及OM不可偽造性。安全性和效率是任何密碼系統(tǒng)的兩個(gè)重要目標(biāo)。在保證安全性的前提下提高效率，獲取更短的簽名和公鑰，是密碼學(xué)者不斷探索的一個(gè)話題。2014年，文獻(xiàn)［21］提出了第一個(gè)基于環(huán)格的，具有相對(duì)較小公鑰的短簽名標(biāo)準(zhǔn)模型構(gòu)造。2016年，Zhang等人^［22］基于格上可編程哈希函數(shù)，提出了一種改進(jìn)的短簽名方案且實(shí)現(xiàn)了針對(duì)選定消息攻擊下的不可偽造性。NIST自2016年開始公開征集后量子算法至今已進(jìn)入第四輪篩選，Dilithium^［23］成為簽名方案中極具競(jìng)爭(zhēng)力的角逐者。該方案使用緊湊且安全的Fiat-Shamir 方案，利用拒絕抽樣定理以及高低順序位，在保證安全性的前提下得到極小的公鑰以及簽名的長(zhǎng)度，提高了方案的效率。

本文在文獻(xiàn)［23］的基礎(chǔ)上進(jìn)行設(shè)計(jì)，提出了一種格上高效盲簽名方案，根據(jù)格上困難問(wèn)題ISIS_n，m，q，η（s）生成密鑰對(duì)，使用兩個(gè)盲化因子對(duì)信息進(jìn)行盲化，使得簽名者無(wú)法區(qū)分信息以及盲化后信息，保證了算法的盲性。使用拒絕抽樣定理保證了簽名者私鑰的安全性。使用向量高低位關(guān)系進(jìn)行簽名，減小了所需存儲(chǔ)空間、提高了算法效率。通過(guò)分析，該方案公私鑰以及簽名長(zhǎng)度短，滿足盲性與不可偽造性。

1 基礎(chǔ)知識(shí)

1.1 格和格上困難問(wèn)題

1.2 拒絕抽樣定理

filtering定理，即涉及均勻分布的拒絕抽樣算法。只有當(dāng)且僅當(dāng)簽名者輸出的簽名落在一個(gè)固定的區(qū)間之內(nèi)，簽名的輸出分布就會(huì)服從該區(qū)間上的均勻分布，故不會(huì)泄露私鑰的信息。

1.4 一般分叉引理

2000年，Pointcheval和Stern^［24］為了證明隨機(jī)預(yù)言機(jī)下簽名算法的安全性，引入分叉引理，如圖1所示。q_i表示敵手對(duì)預(yù)言機(jī)的第i次查詢，h_i表示對(duì)第i次查詢的回復(fù)。整個(gè)過(guò)程，挑戰(zhàn)者進(jìn)行兩次查詢，l次查詢之前，兩次查詢結(jié)果相同；l次查詢后，查詢分叉并得到兩組合法簽名，最終挑戰(zhàn)者利用這兩組同一查詢的不同簽名解決該方案所基于的困難問(wèn)題。該分叉定理僅適用于一般簽名不適應(yīng)帶有特殊屬性的簽名。2006年，Bellare提出了一般分叉引理，如圖1所示。

1.5 盲簽名定義

盲簽名由三個(gè)多項(xiàng)式算法（KG，Sign，Verify）構(gòu)成，其中sign由簽名者與需要簽名者交互完成，具體步驟如下：

a）密鑰生成KG（1ⁿ）。生成公私鑰對(duì)用于簽名與驗(yàn)簽。

b）簽名算法sign（sk，M）。該算法包含消息盲化階段、簽名階段與去盲階段三部分。消息盲化即需要簽名者選取盲化因子μ對(duì)自己的信息M進(jìn)行處理，獲得盲化后信息M′，且簽名者不能根據(jù)盲化后M′獲取初始信息M。簽名過(guò)程為簽名者使用自己私鑰對(duì)盲化后信息M′進(jìn)行簽名。去盲過(guò)程為需要簽名者使用自己的盲化因子μ對(duì)簽名去盲，從而獲得簽名者對(duì)M的簽名s。

c）驗(yàn)證算法verify（pk，s，M）。使用簽名者公鑰pk對(duì)M的簽名s進(jìn)行驗(yàn)證，若驗(yàn)證通過(guò)，則輸出1，否則輸出0。

2 盲簽名方案的設(shè)計(jì)

4 效率分析

該方案采用拒絕抽樣定理以及高低位順序關(guān)系設(shè)計(jì)盲簽名方案，沒(méi)有使用復(fù)雜的陷門函數(shù)，運(yùn)算簡(jiǎn)單，提高了運(yùn)算效率。該方案沒(méi)有大量采樣隨機(jī)參數(shù)，僅保存一個(gè)安全參數(shù)ζ←{0，1}²⁵⁶就可以得到其余參數(shù)，節(jié)省了存儲(chǔ)空間。本文從公鑰長(zhǎng)度、私鑰長(zhǎng)度、簽名長(zhǎng)度以及交互輪數(shù)四個(gè)角度與其他方案進(jìn)行比較。文獻(xiàn)［13］提出了一種基于SIS的簽名方案，通過(guò)拒絕抽樣定理保障私鑰的安全性。文獻(xiàn)［16］安全性規(guī)約于SIS，通過(guò)原像抽樣函數(shù)進(jìn)行簽名，僅需兩輪交互，且有效解決了簽名失敗問(wèn)題。文獻(xiàn)［19］安全性可規(guī)約于最短向量問(wèn)題，且由表1可知，相對(duì)于文獻(xiàn)［13，16，19］，該方案具有較小的公鑰長(zhǎng)度與私鑰長(zhǎng)度，需要三輪交互。整體來(lái)看，本文方案在具有相同安全性能的前提下，簽名長(zhǎng)度較短，公鑰長(zhǎng)度與私鑰長(zhǎng)度有很大優(yōu)勢(shì)，計(jì)算開銷與通信開銷較小，整體效率較高。

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

本文根據(jù)拒絕抽樣定理以及高低位順序關(guān)系提出了一種基于理想格的完全盲簽名方案。通過(guò)分析，該方案具有盲性與不可偽造性，且較其他方案相比，公私鑰長(zhǎng)度較短，簽名長(zhǎng)度達(dá)到l log q，節(jié)省存儲(chǔ)空間，且不需要制造陷門函數(shù)，提高了運(yùn)算速度。該方案安全性最后歸納于格上SIS困難問(wèn)題，具有抗量子性。下一步，將對(duì)部分盲簽名進(jìn)行深入研究，以提高部分盲簽名的安全性與效率。

參考文獻(xiàn)：

［1］Chaum D.Blind signatures for untraceable payments［C］//Advances in Cryptology-Crypto.Boston：Springer，1982：199-203.

［2］邵清，洪郝潔，李斌.基于ElGamal強(qiáng)盲簽名的區(qū)塊鏈電子投票方案研究［J］.小型微型計(jì)算機(jī)系統(tǒng)，2021，42（11）：2400-2421.（Shao Qing，Hong Haojie，Li Bin.Research on blockchain electronic voting scheme based on elgamal strong blind signature［J］.Journal of Chinese Computer Systems，2021，42（11）：2400-2421.）

［3］Jason P C，Yuichi K.Evoting system based on the bitcoin protocol and blind signatures［J］.Trans on Mathematical Modeling and Its Applications，2017，10（1）：14-22.

［4］李舟軍，張江霄，馮春輝，等.電子現(xiàn)金協(xié)議研究綜述［J］.計(jì)算機(jī)科學(xué)與探索，2017，11（11）：1701-1712.（Li Zhoujun，Zhang Jiangxiao，F(xiàn)eng Chunhui，et al. Survey on e-cash scheme［J］.Journal of Frontiers of Computer Science and Technology，2017，11（11）：1701-1712.）

［5］Aboud S J.Anonymous and non-repudiation e-payment protocol［J］.American Journal of Applied Sciences，2010，4（8）：17-33.

［6］Camenisch J L，Piveteau J M，Stadler M A.Blind signatures based on the discrete logarithm problem［C］//Proc of Workshop on the Theory and Application of Cryptographic Techniques.Berlin：Springer，1994：428-432.

［7］王興威，侯書會(huì).一種改進(jìn)的高效的代理盲簽名方案 ［J］.計(jì)算機(jī)科學(xué)，2019，46（6）：358-361.（Wang Xingwei，Hou Shuhui.Improved efficient proxy blind signature scheme［J］.Computer Science，2019，46（6）：358-361.）

［8］Nayak S K，Mohanty S，Majhi B.CLB-ECC：certificateless blind signature using ECC［J］.Journal of Information Processing Systems，2017，13（4）：970-986.

［9］Lysyanskaya A，Ramzan Z.Group blind digital signature：a scalable solution to electronic cash［C］//Proc of International Conference on Financial Cryptography.Berlin：Springer，1998：184-197.

［10］Abe M，F(xiàn)ujisaki E.How to date blind signatures［C］//Proc of International Conference on the Theory and Application of Cryptology and Information Security.Berlin：Springer，1996：244-251.

［11］Lin W D，Jan J K.A security personal learning tools using a proxy blind signature scheme［C］//Proc of International Conference on Chinese Language Computing.2000：273-277.

［12］Rawal S，Padhye S.Cryptanalysis of ID based proxy-blind signature scheme over lattice［J］.Information amp; Communications Technology Express，2020，6（1）：20-22.

［13］Zhang Pingyuan，Jiang Han，Zhang Zhihui，et al. A new post-quantum blind signature from lattice assumptions［J］.IEEE Access，2018，6：27251-27258.

［14］Shim K A，An Y.Cryptanalysis of lattice-based blind signature and blind ring signature schemes［J］.IEEE Access，2021，9：134427-134434.

［15］Rückert M.Lattice-based blind signatures ［C］//Proc of International Conference on the Theory and Application of Cryptology and Information Security.Berlin：Springer，2010：413-430.

［16］王鳳和，胡予濮，王春曉.基于格的盲簽名方案［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2010，35（5）：550-553.（Wang Fenghe，Hu Yupu，Wang Chunxiao.Blind signature scheme based on lattice［J］.Geomatics and Information Science of Wuhan University，2010，35（5）：550-553.）

［17］湯永利，周錦，劉琨，等.標(biāo)準(zhǔn)模型下格上基于身份的盲簽名方案［J］.計(jì)算機(jī)科學(xué)與探索，2017，11（12）：1965-1971.（Tang Yongli，Zhou Jin，Liu Kun，et al. Lattice-based identity-based blind signature scheme in standard model［J］.Journal of Frontiers of Computer Science and Technology，2017，11（12）：1965-1971.）

［18］Zhu Hongfei，Tan Yuan，Zhu Liehuang，et al. An identity-based anti-quantum privacy-preserving blind authentication in wireless sensor networks［J］.Sensors，2018，18（5）：1663.

［19］Singh S，Padhye S.Identity based blind signature scheme over NTRU lattices ［J］.Information Processing Letters，2020，155（3）：105898.

［20］Li Chaoyang，Tian Yuan，Chen Xiubo，et al. An efficient anti-quantum lattice-based blind signature for blockchain-enabled systems［J］.Information Sciences，2021，546：253-264.

［21］Ducas L，Micciancio D.Improved short lattice signatures in the stan-dard model［C］//Proc of Annual Cryptology Conference.Berlin：Springer，2014：335-352.

［22］Zhang Jiang，Chen Yu，Zhang Zhenfeng.Programmable hash functions from lattices：short signatures and IBEs with small key sizes［C］//Proc of Annual International Cryptology Conference.Berlin：Springer，2016：303-332.

［23］Soni B，Basu K，Nabeel M，et al.CRYSTALS-Dilithium［M］//Hardware Architectures for Post-Quantum Digital Signature Schemes.Cham：Springer，2020：13-30.

［24］Pointcheval D，Stern J.Security arguments for digital signatures and blind signatures［J］.Journal of Cryptology，2000，13（3）：361-396.