多變數公開金鑰密碼系統之設計問題

Design Issues of Multivariate Quadratic Public Key Cryptosystems

胡裕華(Yuh-Hua Hu)

指導教授 ： 賴飛羆

國立臺灣大學/電機資訊學院/資訊工程學研究所/博士(2008年)

https://doi.org/10.6342/NTU.2008.02535

摘要

許多公開金鑰系統是值基於單變數低次多項式，但多項式的反函數為高次的多項式。因此計算此多項式的反元素是相當費時的，而多變數公開金鑰系統(MQPKC)可以克服此類的問題。第一個多變數公開金鑰系統被Fell 和Diffe[33]所提出。到目前為止，有數十個多變數公開金鑰系統已經被提出，然而大多數都被破解了。

如何設計一個安全又有效率的MQPKC 仍是一個未知的問題。為了瞭解如何設計MQPKC，我們研究了目前已提出的MQPKC 及已知的攻擊方法。藉由學習兩個已知的解方程組的演算法的過程中，我們發展出另一個更有效率的解方程組演算法，此外這個方法也可以檢驗MQPKC 可能的弱點。

同時我們也提出攻擊Multi-Sets UOV 類簽章的方法；也發展目前最有效率的解多變數二次方程組的演算法，因此我們算出為了達到2 的80 次方的安全性，在有限體個數為256 的條件下，至少要30 個變數及方程式，在有限體個數為16 的條件下，至少要34 個變數及方程式。

最後我們推論出設計MQPKC 的準則，以使得所設計的MQPKC 可以被有系統的檢驗及不會再被已知的方法所攻擊。

關鍵字

多變數二次方程式 ； 密碼系統 ； 簽章 ； XLT ； Multi-Sests UOV ； MQ ； XL

並列摘要

Many public key cryptosystems are based on univariate polynomials with low degree but the inverse of the polynomials are high degree polynomials. Thus it is time consuming to compute the inverse of the polynomials. Multivariate Quadratic Public Key Cryptosystem (MQPKC) can overcome this problem.

The first MQPKC was proposed by Fell and Diffie [33]. Until now, there have been dozens of MQPKCs proposed. However most of them were broken. How to design a secure and practical MQPKC is still unknown. In order to study how to design a MQPKC, we survey the multivariate public key cryptosystems and the attacks against these cryptosystems. By studying the two algorithms for equations solving, we develop a more efficient algorithm for equations solving. Moreover, this algorithm can be used for examining the possible defects of MQPKCs.

We also propose the attack against Multi-Sets UOV, e.g. TRMS, TTS, and Rainbow, and study the more efficient algorithm, XFLT , for solving the quadratic equations. Consequently, the minimum numbers of equations and variables for the security level 280 are 30 over GF(256) and 34 over GF(16).

Finally we deduce and study criteria for building MQPKCs such that the new MQPKCs are examined systematically and are not attacked by the previous methods.

並列關鍵字

multivariate quadratic ； cryptosystem signature ； XLT ； Multi-Sets ； UOV ； MQ ； XL

參考文獻

[4] Come Berbain, Henri Gilbert and Jacques Patarin, QUAD, A Practical Stream Cipher with Provable security, Advances in Cryptology - EUROCRYPT 2006, Lecture Notes in Computer Science 4004, Springer-Verlag (2006) pp. 109-128.

[5] An Braeken, ChristopherWolf and Bart Preneel, A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes, The Cryptographers' Track at the RSA Conference 2005, Lecture Notes in Computer Science 3376, Springer-Verlag (2005) pp. 29-43.

[6] Nicolas Courtois, The security of Hidden Field Equations(HFE), The Cryptographers?Track at the RSA Conference 2001, Lecture Notes in Computer Science 2020, Springer-Verlag (2001) pp. 266-281.

[7] Nicolas Courtois, Higher Order Correlation Attacks, XL Algorithm and Cryptanalysis of Toyocrypt, Information Security and Cryptology - ICISC 2002, Lecture Notes in Computer Science 2587, Springer-Verlag (2003) pp. 182-199.

[8] Nicolas Courtois, Generic Attacks and the Security of Quartz, Public Key Cryptography - PKC 2003, Lecture Notes in Computer Science 2567, Springer-Verlag (2003) pp. 351-364.