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

王眾，韓益亮

?

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

王眾，韓益亮

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

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

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

1 引言

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

目前，主要的抗量子密碼有：基于編碼的密碼體制、基于格的密碼體制（LWE, learning with errors）、基于Hash函數的密碼體制以及基于多變量的密碼體制[3]。為什么這些密碼體制能夠有效地抵抗量子計算機的攻擊？因為它們都是在NP難問題的基礎上構建起來的，而量子計算機相比于普通計算機在求解這一類問題上并沒有顯著的優勢。抗量子密碼中的基于多變量的密碼體制，相比于傳統的公鑰密碼，不僅能夠有效地抵抗量子計算攻擊，而且在運行的效率方面有更多的優勢，并消耗更少的資源[4]。盡管存在許多實用的多變量簽名方案，但有效和安全的多變量加密方案的數量還是有限的[5]。

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

2 多變量公鑰密碼系統以及Simple Matrix方案

2.1 雙極系統

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

雙極系統的公鑰包括2部分：一是系統所在有限域以及它的域結構；二是公鑰映射的個多項式。私鑰則為隨機選取的可逆線性仿射變換1和2，以及中心映射[12]。

2.2 混合系統

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

混合系統的公鑰包括：1) 系統所在有限域以及其域結構；2) 構成公鑰映射的多項式方程。

2.3 Simple Matrix方案

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

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

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

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

4) 利用可逆線性映射對進行運算，進而得到明文。

3 Simple Matrix方案改進版本

3.1 構造思想

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

3.2 加密解密過程

2) 解密過程如下。

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

4 安全性分析

4.1 秩攻擊

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

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

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

4.2 代數攻擊

5 效率分析

5.1 明文密文比例分析

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

5.2 攻擊效率

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

表1 直接攻擊效果對比

通過實驗對比可以發現改進版Simple Matrix方案比Simple Matrix方案的求解復雜度更大，耗時更長，安全性更高，并且隨著密文明文規模的擴大，消耗的時間呈指數增長。

6 結束語

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

[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方案的分析與改進[D]. 西安：西安電子科技大學, 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

國家自然科學基金資助項目（No.61572521）

王眾（1995-），男，山東泰安人，武警工程大學碩士生，主要研究方向為抗量子密碼。

韓益亮（1977-），男，甘肅會寧人，武警工程大學教授、博士生導師，主要研究方向為抗量子密碼。

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