多變量體制下的代理簽密方案

摘 要：目前大多數代理簽密方案的安全性主要是基于傳統密碼體制下的，隨著量子計算技術的發展，傳統密碼體制下的代理簽密方案受到嚴重威脅，構造抗量子計算的代理簽密方案具有重要意義。多變量公鑰密碼是抗量子計算密碼的主要候選者之一，鑒于此，提出多變量密碼體制下的代理簽密方案，利用有限域上求解非線性多變量多項式方程組問題和多項式同構問題保證了其安全性。分析表明該方案計算速度快、通信代價低，并具有抗量子計算的能力。

關鍵詞：多變量密碼；代理簽密；多項式方程組問題；多項式同構問題；抗量子攻擊

中圖分類號：TP309.7 文獻標志碼：A

文章編號：1001-3695（2022）07-040-2167-05

doi：10.19734/j.issn.1001-3695.2021.12.0662

基金項目：陜西省自然科學基金基礎研究計劃重點項目（2020JZ-54）

作者簡介：俞惠芳（1972-），女（通信作者），青海樂都人，教授，碩導，博士，主要研究方向為密碼學與信息安全（327766891@qq.com）；張帥（1996-），男，山東聊城人，碩士研究生，主要研究方向為多變量公鑰密碼學．

Proxy signcryption scheme based on multivariate cryptosystem

Yu Huifang?，Zhang Shuai

（School of Cyberspace Security，Xi’an University of Posts amp; Telecommunications，Xi’an 710121，China）

Abstract：At present，the security of most proxy signcryption schemes is mainly based on traditional cryptosystem.However，with the development of quantum computing technology，traditional proxy signcryption schemes face serious threat.Hence，it is of great value to construct a proxy signcryption scheme against the quantum attacks.Multivariate public key cryptography （MPKC） is one candidate of post-quantum cryptography.This paper proposed a signcryption scheme based on multivariate cryptosystem.Security of new scheme relied on the multivariate quadratic （MQ） problem and the isomorphism of polynomials （IP） problem.The scheme has quick computation speed with low communication overhead and ability against the quantum computing attacks.

Key words：multivariate；proxy signcryption；multivariate quadratic problem；isomorphism of polynomials problem；anti-quantum attacks

在現實生活中，大部分人都有過找領導簽字的經歷，如果領導外出不能及時回來，就會委托其他人代替自己進行簽字處理，這就是代理簽名。如果這個代理簽名中包含隱私信息，一旦在傳輸過程中被他人攔截，就會造成損失。以前人們解決這個問題的方案是首先對代理簽名的結果進行加密，然后發送給接收者，接收者先進行解密再進行驗證，這樣做提高了計算的開銷和密文的擴展率。為此，Gamage等人^[1]在1999年結合代理簽名和簽密首次提出一個代理簽密方案，經授權后代理簽密者直接對消息進行簽密后發送給接收者。當數字簽名在公開信道上進行傳輸時，簽密能保證其保密性和不可偽造性等安全屬性；代理簽密亦是如此，能保證代理簽名的安全傳輸。代理簽密能在一個邏輯步驟內完成加密及代理簽名的操作，計算和通信的代價都低于傳統的方法。后來，研究人員陸續提出各種代理簽密方案^[2～8]。文獻[2]提出一個基于身份的代理簽密方案；文獻[3]提出安全性更強的基于身份的簽密和代理簽密方案；文獻[4]提出的代理簽密方案在隨機諭言機模型下滿足代理簽密的安全特性，在各方面具有更高的效率，但它們不具備抗量子計算的能力。隨著量子計算技術^[9]的迅速發展，這些傳統密碼體制下的代理簽密面臨著嚴峻的安全威脅，所以需要研究抗量子計算的代理簽密。

Shor算法^[10]是一種搜索破譯算法，在多項式時間內可攻破傳統的公鑰密碼。面對量子計算技術的威脅，能抗量子攻擊的多公鑰變量密碼體制^[11]成為抗量子密碼體制方面^[12～14]的研究熱點，其安全性依賴于有限域上的二次多變量多項式方程組（MQ）問題和多項式同構（IP）問題，這兩類問題都被證明是非確定性多項式（NP）困難問題。多公鑰變量密碼以其運算速度快、所需計算資源少的優勢，得到廣泛的應用。1988年，首個Matsumoto-Imai多變量加密方案^[15]被提出；文獻[16]提出一種快速多變量密碼體制，當時被選為低耗能卡的安全標準，但在2007年被文獻[17]提出的方法攻破；文獻[18]提出基于多層Matsumoto-Imai方案，利用一種改進的中心映射進行簽密操作，在隨機諭言機模型下具有不可偽造性和機密性。隨著密碼體制的不斷發展，研究人員構造出很多安全性更高的多變量密碼方案，但目前還沒有基于多變量的代理簽密方案被提出。

本文結合代理簽密和多變量密碼的技術理論，提出基于多變量的代理簽密方案。本文方案具有多變量密碼體制的計算效率高、開銷小的特點，能抗量子計算的攻擊，還可以有效保護代理簽密者的代理權，避免代理簽密權的濫用，最終達到保護原始簽密者利益的目的。本文方案具有適應性選擇密文攻擊下的保密性（IND-CCA2）和適應性選擇消息攻擊下的不可偽造性（EUF-CMA）^[19]。

1 基礎知識

1.1 MQ問題和IP問題

多變量密碼可以抗量子計算的攻擊，其公鑰為有限域K上含有r個方程、n個未知數的一組非線性多變量多項式，一般形式如下：

6 性能分析

為了更直觀地體現多變量密碼體制下的代理簽密的抗量子計算的性能優勢，本章將對本文方案與文獻[6，8]中的方案的簽密階段和解簽密階段花費的計算時間進行比較。運算量的描述中，忽略一些計算開銷小的運算，主要密碼操作的計算開銷如表1所示。

7 結束語

本文主要對多變量公鑰密碼體制下的代理簽密進行研究，依托多變量上的困難問題實現了方案的代理授權和代理簽密的目標，同時提高了計算效率和代理的安全性。在隨機諭言機模型中已經證明所提方案滿足不可區分性和不可偽造性。由于所提方案的整個過程都用到了許可證書mw，任意第三方都可以用此證書和用戶公鑰驗證密文是否是由代理簽密者產生的、代理簽密者能否遵守簽密權限范圍，所以該方案還滿足不可否認性、防止濫用性和公開驗證性等。本文方案具有抗量子計算的特性，在密碼學應用領域具有很好的實用前景。下一步需要針對多變量密碼體制下無證書環簽密方案進行研究，以便更好地應用于實際場景中。

參考文獻：

［1］Gamage C，Leiwo J，Zheng Yuliang.An efficient scheme for secure message transmission using proxy-signcryption[C]//Proc of the 22nd Australasian Computer Science Conference.Berlin：Springer-Verlag，1999：420-431.

[2]Li Xiangxue，Chen Kefei.Identity based proxy-signcryption scheme from pairings[C]//Proc of IEEE International Conference on Ser-vices Computing.Washington DC：IEEE Computer Society，2004：494-497.

[3]冀會芳，韓文報，趙龍.基于身份的簽密和代理簽密方案[J].信息工程大學學報，2010，11（4）：458-461.（Ji Huifang，Han Wenbao，Zhao Long.Identity based signcryption and proxy signcryption schemes[J].Journal of Information Engineering University，2010，11（4）：458-461.）

[4]王琴.一種基于身份的代理簽密體制[J].計算機工程，2011，37（19）：120-121，125.（Wang Qin.Proxy signcryption system based on identity[J].Computer Engineering，2011，37（19）：120-121，125.）

[5]Zhu Hongfei，Wang Ye，Wang Chonghua，et al.An efficient identity-based proxy signcryption using lattice[J].Future Generation Computer Systems，2021，117（4）：321-327.

[6]Li Li，Zhou Siqin，Choo R K K，et al.An efficient and provably-secure certificateless proxy-signcryption scheme for electronic prescription system[J].Security and Communication Networks，2018，2018：article ID 7524102.

[7]湯鵬志，張慶蘭，楊俊芳，等.一種新的無證書多代理簽密方案[J].鄭州大學學報：理學版，2016，48（2）：40-46.（Tang Pengzhi，Zhang Qinglan，Yang Junfang，et al.A new certificateless multi-proxy signcryption scheme[J].Journal of Zhengzhou University：Natural Science Edition，2016，48（2）：40-46.）

[8]周才學.標準模型下基于身份的廣義代理簽密[J].密碼學報，2016，3（3）：307-320.（Zhou Caixue.Identity-based generalized proxy signcryption in the standard model[J].Journal of Cryptologic Research，2016，3（3）：307-320.）

[9]王潮，姚皓南，王寶楠，等.量子計算密碼攻擊進展[J].計算機學報，2020，43（9）：1691-1707.（Wang Chao，Yao Haonan，Wang Bao-nan，et al.Progress in quantum computing cryptography attacks[J].Chinese Journal of Computers，2020，43（9）：1691-1707.）

[10]Shor P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J].Siam Review，1999，41（2）：124-134.

[11]韓益亮.多變量公鑰密碼進展[J].信息技術與網絡安全，2021，40（8）：1-8，16.（Han Yiliang.Advances in multivariate public-key cryptosystem[J].Information Technology and Network Security，2021，40（8）：1-8，16.

[12]何詩洋，李暉，李鳳華.面向格基密碼體制的高效硬件實現研究綜述[J].密碼學報，2021，8（6）：1019-1038.（He Shiyang，Li Hui，Li Fenghua.A survey on high-efficiency hardware implementation for lattice-based cryptosystem[J].Journal of Cryptologic Research，2021，8（6）：1019-1038.）

[13]Sendrier N.Code-based cryptography：state of the art and perspectives[J].IEEE Security amp; Privacy，2017，15（4）：44-50.

[14]Butin D.Hash-based signatures：state of play[J].IEEE Security amp; Privacy，2017，15（4）：37-43.

[15]Matsumoto T，Imai H.Public quadratic polynomial-tuples for efficient signature-verification and message-encryption[C]//Proc of Workshop on the Theory and Application of Cryptographic Techniques.Berlin：Springer-Verlag，1988：419-453.

[16]Preneel B.New European schemes for signature，integrity and encryption（NESSIE）：a status report[C]//Proc of International Workshop on Practice amp; Theory in Public Key Cryptosystems：Public Key Cryptography.Berlin：Springer-Verlag，2002：195-216.

[17]Dubois V，Fouque P A，Shamir A，et al.Practical cryptanalysis of SFLASH[C]//Proc of the 27th International Cryptology Conference on Advances in Cryptology.Berlin：Springer-Verlag，2007：1-12.

[18]藍錦佳，韓益亮，楊曉元.基于多變量密碼體制的簽密方案[J].計算機應用，2015，35（2）：401-406.（Lan Jinjia，Han Yiliang，Yang Xiaoyuan.Signcryption scheme based on multivariate cryptosystem[J].Journal of Computer Applications，2015，35（2）：401-406.）

[19]俞惠芳，楊波.可證安全的無證書混合簽密[J].計算機學報，2015，38（4）：804-813.（Yu Huifang，Yang Bo.Provably secure certificateless hybrid signcrytion[J].Chinese Journal of Computers，2015，38（4）：804-813.）