王眾，韓益亮

?

密文長度可變的Simple Matrix加密方案

王眾，韓益亮

（武警工程大學(xué)密碼工程學(xué)院，陜西 西安 710086）

多變量公鑰密碼是抗量子密碼的可靠候選之一，其中的Simple Matrix方案是利用3個(gè)矩陣間的運(yùn)算來構(gòu)造的。提出了Simple Matrix方案的改進(jìn)版本，通過使用具有隨機(jī)二次多項(xiàng)式的可改變形式的扁平矩陣進(jìn)行構(gòu)造，使秩攻擊對(duì)新的方案不可行，且代數(shù)攻擊對(duì)新方案的攻擊至少和求解一組隨機(jī)二次方程一樣困難。新的方案將密文與明文的比例改進(jìn)為大于等于兩倍，打破了固定不變的密文與明文比例，使其擁有一個(gè)靈活的明密文比，以適應(yīng)不同的需求。

多變量公鑰密碼；Simple Matrix方案；明密文比；安全性分析

1 引言

公鑰密碼在當(dāng)今的計(jì)算機(jī)安全領(lǐng)域扮演著十分重要的角色。傳統(tǒng)的公鑰加密方案主要基于經(jīng)典數(shù)論的相關(guān)知識(shí)，比較典型的有RSA、ECC（elliptic curves cryptography）、DSA（digital signature algorithm）、屬性基的公鑰密碼等[1]。1994年，Shor[2]提出了一種在量子計(jì)算機(jī)上運(yùn)行的多項(xiàng)式時(shí)間算法（Shor算法），使分解大整數(shù)和求解Abel群上的離散對(duì)數(shù)問題在多項(xiàng)式時(shí)間內(nèi)不再困難，其時(shí)間復(fù)雜度大概為(log3)（表示比特?cái)?shù)為的數(shù)），這給基于經(jīng)典數(shù)論問題的傳統(tǒng)公鑰密碼學(xué)帶來了威脅。而且隨著計(jì)算機(jī)硬件技術(shù)的快速發(fā)展，計(jì)算機(jī)的計(jì)算能力大幅提升，在繼傳統(tǒng)計(jì)算機(jī)出現(xiàn)并普及后，又出現(xiàn)了以量子位為計(jì)算單位的計(jì)算機(jī)——量子計(jì)算機(jī)。在不久的將來，大型的量子計(jì)算機(jī)出現(xiàn)后，大部分傳統(tǒng)的公鑰密碼將很容易被攻破。

目前，主要的抗量子密碼有：基于編碼的密碼體制、基于格的密碼體制（LWE, learning with errors）、基于Hash函數(shù)的密碼體制以及基于多變量的密碼體制[3]。為什么這些密碼體制能夠有效地抵抗量子計(jì)算機(jī)的攻擊？因?yàn)樗鼈兌际窃贜P難問題的基礎(chǔ)上構(gòu)建起來的，而量子計(jì)算機(jī)相比于普通計(jì)算機(jī)在求解這一類問題上并沒有顯著的優(yōu)勢?？沽孔用艽a中的基于多變量的密碼體制，相比于傳統(tǒng)的公鑰密碼，不僅能夠有效地抵抗量子計(jì)算攻擊，而且在運(yùn)行的效率方面有更多的優(yōu)勢，并消耗更少的資源[4]。盡管存在許多實(shí)用的多變量簽名方案，但有效和安全的多變量加密方案的數(shù)量還是有限的[5]。

在PQCrypto 2013會(huì)議上，Cheng等[6]提出了一種新的多變量公鑰加密方案Simple Matrix（簡稱為ABC密碼方案），它可以抵抗大部分針對(duì)多變量公鑰密碼方案的攻擊，但是它的解密錯(cuò)誤率卻不可忽視。2014年，Ding等提出了對(duì)Simple Matrix方案的改進(jìn)，即Cubic Simple Matrix密碼方案[7]，使原來組成公鑰的二次多變量多項(xiàng)式變?yōu)槿味嘧兞慷囗?xiàng)式。這一改進(jìn)，可以有效地抵抗秩攻擊[8]，并且使代數(shù)攻擊[8]的困難性與解決隨機(jī)二次多項(xiàng)式系統(tǒng)的困難性相近。Simple Matrix方案與Cubic Simple Matrix方案都將密文與明文的比例控制在兩倍關(guān)系，使其應(yīng)用起來不夠靈活，不能滿足多種需求。本文提出了一種新的基于Simple Matrix的密碼方案，在保證安全性、可靠性的同時(shí)，改變明文與密文之間的兩倍固定關(guān)系，提供了一種靈活可變的明文密文比例。

2 多變量公鑰密碼系統(tǒng)以及Simple Matrix方案

2.1 雙極系統(tǒng)

目前，多變量密碼方案可分為雙極模式（bipolar）、混合模式（mixed）、多項(xiàng)式同構(gòu)模式（IP, isomorphisms of polynomials）以及多元二次模式（MQ, multivariate quadratic）[10]。其中，大部分的多變量公鑰密碼是基于雙極系統(tǒng)來構(gòu)造的，混合模式的較少[11]，而另外2種則更少。

雙極系統(tǒng)的公鑰包括2部分：一是系統(tǒng)所在有限域以及它的域結(jié)構(gòu)；二是公鑰映射的個(gè)多項(xiàng)式。私鑰則為隨機(jī)選取的可逆線性仿射變換1和2，以及中心映射[12]。

2.2 混合系統(tǒng)

其中，1：K→K和2：K→K的定義與雙極系統(tǒng)中所定義的可逆線性映射相同，3則是一個(gè)K到K的可逆線性映射。

混合系統(tǒng)的公鑰包括：1) 系統(tǒng)所在有限域以及其域結(jié)構(gòu)；2) 構(gòu)成公鑰映射的多項(xiàng)式方程。

2.3 Simple Matrix方案

然后，定義3個(gè)小矩陣、、維度均為′，如下所示。

Simple Matrix算法的加密過程如下。

Simple Matrix算法的解密過程如下。

若矩陣、1、2均不可逆，則無法解密。

4) 利用可逆線性映射對(duì)進(jìn)行運(yùn)算，進(jìn)而得到明文。

3 Simple Matrix方案改進(jìn)版本

3.1 構(gòu)造思想

從第2節(jié)的介紹中，可以看出Simple Matrix算法中的密文與明文比例被固定為兩倍的關(guān)系，這會(huì)導(dǎo)致方案不夠靈活，不能滿足多種需求。本節(jié)提出一種改進(jìn)版本，使密文與明文之間的比例更加靈活，并將其公鑰由原來的二次多項(xiàng)式組成改為由三次多項(xiàng)式組成，提供了更高的安全性。

3.2 加密解密過程

2) 解密過程如下。

若矩陣不可逆則解密失敗。

4 安全性分析

4.1 秩攻擊

秩攻擊是對(duì)多變量公鑰密碼比較有效的一種攻擊方法，它分為低秩攻擊（MinRank attack）[13]與高秩攻擊（HighRank attack）[14]。

在高秩攻擊中，攻擊者則是找到關(guān)于中心多項(xiàng)式中出現(xiàn)次數(shù)最少的變量的線性組合。例如，Rainbow方案[15]中最后一層中的油變量，就是出現(xiàn)次數(shù)最少的變量，通過對(duì)每一層重復(fù)這種攻擊，攻擊者可以恢復(fù)可逆仿射變換，最終恢復(fù)明文。

然而，在改進(jìn)版的Simple Matrix方案中，矩陣的元素是隨機(jī)選擇的多元二次多項(xiàng)式。因此，它們的秩接近于，不能使用低秩攻擊。并且所有變量出現(xiàn)在每個(gè)中心多項(xiàng)式中的次數(shù)大約相同，這就不能使用高秩攻擊。因此，可以得到結(jié)論，秩攻擊不適用于改進(jìn)版的Simple Matrix方案。

4.2 代數(shù)攻擊

5 效率分析

5.1 明文密文比例分析

密文與明文的比例可表示為

5.2 攻擊效率

下面通過實(shí)驗(yàn)比較直接攻擊對(duì)原始版Simple Matrix方案以及改進(jìn)版Simple Matrix方案的攻擊效果，(,)分別代表密文與明文規(guī)模，為方便比較抵抗直接攻擊的能力，令改進(jìn)版Simple Matrix的密文與明文比為兩倍，與原始方案保持一致，2種方案均在域GF(256)上進(jìn)行。實(shí)驗(yàn)對(duì)比結(jié)果如表1所示。

表1 直接攻擊效果對(duì)比

通過實(shí)驗(yàn)對(duì)比可以發(fā)現(xiàn)改進(jìn)版Simple Matrix方案比Simple Matrix方案的求解復(fù)雜度更大，耗時(shí)更長，安全性更高，并且隨著密文明文規(guī)模的擴(kuò)大，消耗的時(shí)間呈指數(shù)增長。

6 結(jié)束語

Simple Matrix方案是多變量公鑰密碼中較新的密碼體制，巧妙運(yùn)用了3個(gè)矩陣間的運(yùn)算來構(gòu)造中心映射。本文對(duì)原始的Simple Matrix方案進(jìn)行改進(jìn)，將原來公鑰映射中的二次多項(xiàng)式用三次多項(xiàng)式代替，可以有效地對(duì)秩攻擊等攻擊方法做有效的防御，提升了方案的安全性，并打破原始Simple Matrix方案中密文與明文長度兩倍的固定關(guān)系，減少了明文與密文之間的一些聯(lián)系，使方案更加靈活可靠。但是該改進(jìn)方案中，密文長度大于等于兩倍的明文長度，還需要進(jìn)一步改進(jìn)，使密文長度可以小于兩倍的明文長度甚至小于一倍的明文長度。下一步工作是擴(kuò)大明密文比例的取值范圍，并提供一個(gè)加解密效率更高的方案。

[1] RIVEST R L, SHAMIR A, ADLEMAN, L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 21(2), 120-126: 1978.

[2] SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[C]//Quantum Entanglement and Quantum Information-Proceedings of CCAST. 1999: 303-332.

[3] BERNSTEIN D J, BUCHMANN J, DAHMEN E. Post quantum cryptography[M]. Berlin Heidelberg: Springer, 2010.

[4] BOGDANOV A, EISENBARTH T, RUPP A, et al. Time-area optimized publickey engines: MQ-cryptosystems as replacement for elliptic curves?[C]//Cryptographic Hardware and Embedded Systems–CHES 2008. 2008:45-61.

[5] DING J, SCHMIDT D. Rainbow, a new multivariable polynomial signature scheme[C]//International Conference on Applied Cryptography and Network Security. 2005:164-175.

[6] CHENG T, DIENE A, TANG S, et al. Simple matrix scheme for encryption[C]//International Workshop on Post-Quantum Cryptography. 2013:231-242.

[7] DING J, PETZOLDT A, WANG L C. The cubic simple matrix encryption scheme[C]//Post-Quantum Cryptography. 2014:76-87.

[8] KIPNIS A, SHAMIR A. Cryptanalysis of the HFE public key cryptosystem[C]//Advances in Cryptology—CRYPTO’99. 1999: 19-30.

[9] SAKUMOTO K, SHIRAI T, HIWATARI H. Public-key identification schemes based on multivariate quadratic polynomials[J]. Technical Report of Ieice Isec, 2011, 111:706-723.

[10] PATARIN J. Asymmetric cryptography with a hidden monomial[C]//Advances in Cryptology—CRYPTO ’96. 1996:45-60.

[11] DING J, GOWER J E, SCHMIDT D S. Multivariate public key cryptosystems[M]. US : Springer US, 2006.

[12] 丁斗博. 多變量公鑰密碼中TTS方案的分析與改進(jìn)[D]. 西安：西安電子科技大學(xué), 2013.

DING D B. Analysis and improvement on the multivariate quadratic TTS scheme[D]. Xi’an: Xidian University, 2013.

[13] GOUBIN L, COURTOIS N. Cryptanalysis of the TTM Cryptosystem[C]//International Conference on the Theory and Application of Cryptology and Information Security. 2000: 44-57.

[14] COPPERSMITH D, STERN J, VAUDENAY S. Attacks on the birational permutation signature schemes[C]//Advances in Cryptology—CRYPTO’ 93. 1993:435-443.

[15] DING J, SCHMIDT D. Rainbow, a new multivariable polynomial signature scheme[C]//Applied Cryptography and Network Security. 2005:164-175.

[16] COURTOIS N, KLIMOV A, PATARIN J, et al. Efficient algorithms for solving overdefined systems of multivariate polynomial equations[C]//Advances in Cryptology—EUROCRYPT 2000. 2000: 392-407.

[17] FAUGERE J C. A new efficient algorithm for computing Gr?bner bases without reduction to zero (F5)[C]//The 2002 International Symposium on Symbolic and Algebraic Computation. 2002:75-83.

[18] FAUGERE J C. A new efficient algorithm for computing Grobner bases (F4)[J]. Journal of Pure and Applied Algebra,1999,139: 61-88.

[19] DING J, BUCHMANN J. Solving degree and degree of regularity for polynomial systems over a finite fields[C]//The First International Conference on Symbolic Computation and Cryptography (SCC 2008). 2008.

[20] MOHAMED M S E, CABARCAS D, DING J, et al. MXL 3: an efficient algorithm for computing gr?bner bases of zero-dimensional ideals[C]//International Conference on Information Security and Cryptology. 2009:87-100.

Simple Matrix encryption scheme with variable ciphertext length

WANG Zhong, HAN Yiliang

Engineering University of PAP, College of Cryptographic Engineering, Xi’an 710086, China

Multivariable public key cryptography is one of the reliable candidates for anti-quantum cryptography. The Simple Matrix scheme is constructed using the operations between three matrices. An improved version of the Simple Matrix scheme was proposed. It is constructed by using two flat matrices with random quadratic polynomials, so that the rank attacks is infeasible for the new scheme, and the algebraic attacks breaks the system is at least as hard as solving a set of random quadratic equations. The new scheme will improve the proportion of ciphertext and plaintext to 2 times or more, break the fixed proportion of ciphertext and plaintext, so that it has a flexible proportion to adapt to different needs.

multivariable public key cryptography, Simple Matrix scheme, the proportion of plaintext and ciphertext, security analysis

TN918.4

A

10.11959/j.issn.2096-109x.2018032

2018-03-10；

2018-04-01

韓益亮，hanyil@163.com

國家自然科學(xué)基金資助項(xiàng)目（No.61572521）

王眾（1995-），男，山東泰安人，武警工程大學(xué)碩士生，主要研究方向?yàn)榭沽孔用艽a。

韓益亮（1977-），男，甘肅會(huì)寧人，武警工程大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榭沽孔用艽a。

The National Natural Science Foundation of China (No.61572521)