臺灣博碩士論文加值系統

解多變量系統的問題在許多領域，包含代數攻擊和多變量密碼學，都具有重要的地位。然而，現存的演算法如 F4/F5 和 XL 雖然對於具有某些特性的系統效果特別顯著，但在面對一般的系統時，通常都無法有效率地解決問題，甚至會帶來嚴重的記憶體匱乏的問題。

基於上述的理由，我們便開始尋求另一個適合一般系統的解決方案，也就是窮舉搜尋 (exhaustive search) 的方式。在這篇論文中，我們提出並深入研究了一個窮舉搜尋的演算法 GGCE (generalized Gray code enumeration)，用以解佈於二元體的多項式系統。這個演算法不僅相當易於平行化，對於解低次數的系統也有非常好的表現。對於這個演算法理論上的效能和記憶體需求等重要議題，在之後也會有深入的分析。

以實際面而言，我們將 GGCE 實作於顯示卡及 CPU 上。經過適當的最佳化之後，我們發現 GGCE 不僅在理論上相當有效率，實際的表現甚至遠勝過現有的演算法。換句話說，在面對一般系統時，窮舉搜尋可能是最好的解法。

簡而言之，我們提出了一個不同於以往的策略來解多變量系統。GGCE 證明了窮舉搜尋本身的強大能力，對於需要解多變量系統的眾多領域，勢必也會產生相當的影響。

Abstract i
Contents iii
List of Figures v
List of Tables vi
1 Introduction vii
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
2 Gray Code Enumeration and Partial Evaluation xi
2.1 Notational Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . xi
2.2 Gray Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
2.3 Naïve Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
2.4 Basic Gray Code Enumeration . . . . . . . . . . . . . . . . . . . . . . xiv
2.5 Generalized Gray Code Enumeration . . . . . . . . . . . . . . . . . . xvi
2.6 Partial Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi
3 Variants and Analysis xxiv
3.1 Early-abort Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiv
3.1.1 In Naïve Evaluation . . . . . . . . . . . . . . . . . . . . . . . . xxiv
3.1.2 In GGCE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiv
3.2 Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . xxvi
4 Implementations xxviii
4.1 On NVIDIA GPUs, with CUDA . . . . . . . . . . . . . . . . . . . . . xxviii
4.1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxviii
4.1.2 Register Usage . . . . . . . . . . . . . . . . . . . . . . . . . . xxix
4.1.3 Unrolling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxx
4.1.4 Testing with Conditional Move . . . . . . . . . . . . . . . . . xxxi
4.1.5 Re-enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . xxxii
4.2 On x86-64 CPUs, with SSE2 Intrinsics . . . . . . . . . . . . . . . . . xxxiii
4.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxiii
4.2.2 Batched Enumeration . . . . . . . . . . . . . . . . . . . . . . . xxxiii
4.2.3 Batched Filtering . . . . . . . . . . . . . . . . . . . . . . . . . xxxiv
5 Experiment Results xxxv
Bibliography xxxviii

[1] B.-Y. Yang and J.-M. Chen All in the XL Family: Theory and Practice. Proc.
7th International Conference on Information Security and Cryptology, volume
3506, Lecture Notes in Computer Science, pages 67-86, 2004.
[2] Gregory V. Bard Algebraic Cryptanalysis. Springer-Verlag, New York, first
edition, 2009.
[3] N. T. Courtois and Gregory V. Bard Algebraic Cryptanalysis of the Data
Encryption Standard. Available at http://eprint.iacr.org/2006/402/.
[4] G. V. Bard, N. T. Courtois, and C. Jefferson. Efficient methods for conver-
sion and solution of sparse systems of low-degree multivariate polynomials over
GF(2) via SAT-solvers. http://eprint.iacr.org/2007/024.
[5] M. Bardet, J.-C. Faugère, and B. Salvy. On the complexity of Grobner basis
computation of semi-regular overdetermined algebraic equations. In Proc. Int’l
Conference on Polynomial System Solving, pp. 71–74, 2004. INRIA report RR-
5049.
[6] M. Bardet, J.-C. Faugère, B. Salvy, and B.-Y. Yang. Asymptotic expansion
of the degree of regularity for semi-regular systems of equations. Proc. MEGA
2005, 2005.
[7] C. Berbain, H. Gilbert, and J. Patarin. QUAD: A practical stream cipher with
provable security. Eurocrypt 2006, LNCS 4004, pp. 109–128.
[8] D. J. Bernstein, T.-R. Chen, C.-M. Cheng, T. Lange, and B.-Y. Yang. ECM
on graphics cards. Eurocrypt 2009, LNCS 5479, pp. 483–501.
[9] Luk Bettale, Jean-Charles Faugère and Ludovic Perret. Hybrid approach for
solving multivariate systems over finite fields, J. Math. Crypto. 3:3(2009)
pp. 177–197.
[10] C. Bouillaguet, J.-C. Faugère, P.-A. Fouque, and L. Perret. Differential-
algebraic algorithms for the isomorphism of polynomials problem.
http://eprint.iacr.org/2009/583
[11] C. Bouillaguet, P.-A. Fouque, A. Joux, and J. Treger. A family of weak keys
in HFE (and the corresponding practical key-recovery). http://eprint.iacr.
org/2009/619.
[12] B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restk-
lassenringes nach einem nul ldimensionalen Polynomideal. PhD thesis, Inns-
bruck, 1965.
[13] Johannes Buchmann, Daniel Cabarcas, Jintai Ding and Mohamed Saied Emam
Mohamed. Flexible Partial Enlargement to Accelerate Gröbner Basis Compu-
tation over F􏰀 , Africacrypt 2010, LNCS 6055, pp. 69–81.
[14] N. Courtois, G. V. Bard, and D. Wagner. Algebraic and slide attacks on Keeloq.
FSE 2008, LNCS 5086, pp. 97–115.
[15] N. Courtois, L. Goubin, and J. Patarin. SFLASH: Primitive specification (sec-
ond revised version), 2002. https://www.cosic.esat.kuleuven.be/nessie
[16] N. T. Courtois, A. Klimov, J. Patarin, and A. Shamir. Efficient algorithms
for solving overdefined systems of multivariate polynomial equations. Euro-
crypt 2000, LNCS 1807, pp. 392–407. Extended ver.: http://www.minrank.
org/xlfull.pdf.
[17] N. de Bruijn. Asymptotic methods in analysis. 2nd edition. Bibliotheca Math-
ematica. Vol. 4. Groningen: P. Noordhoff Ltd. XII, 200 p. , 1961.
[18] J.-C. Faugère. A new efficient algorithm for computing Grobner bases (F4 ). J.
of Pure and Applied Algebra, 139(1999), pp. 61–88.
[19] J.-C. Faugère. A new efficient algorithm for computing Grobner bases without
reduction to zero (F5 ). ACM ISSAC 2002, pp. 75–83.
[20] J.-C. Faugère and A. Joux. Algebraic cryptanalysis of Hidden Field Equations
(HFE) using Gröbner bases. CRYPTO 2003, LNCS 2729, pp. 44–60.
[21] A. Fog. Instruction Tables. Copenhagen University, College of Engineering, Feb
2010. Lists of Instruction Latencies, Throughputs and micro-operation break-
downs for Intel, AMD, and VIA CPUs, http://www.agner.org/optimize/
instruction_tables.pdf.
[22] J. Patarin. Asymmetric cryptography with a hidden monomial. Crypto 1996,
LNCS 1109, pp. 45–60.
[23] J. Patarin. Hidden Field Equations (HFE) and Isomorphisms of Polynomials
(IP): two new families of asymmetric algorithms. Eurocrypt 1996, LNCS 1070,
pp. 33–48. Extended ver.: http://www.minrank.org/hfe.pdf.
[24] J. Patarin, N. Courtois, and L. Goubin. QUARTZ, 128-bit long digital signa-
tures http://www.minrank.org/quartz/. CT-RSA 2001, LNCS 2020, pp. 282–
297.
[25] J. Patarin, L. Goubin, and N. Courtois. Improved algorithms for Isomorphisms
of Polynomials. Eurocrypt 1998, LNCS 1403, pp. 184–200. Extended ver.:
http://www.minrank.org/ip6long.ps.
[26] H. Raddum. MRHS equation systems. SAC 2007, LNCS 4876, pp. 232–245.
[27] M. Sugita, M. Kawazoe, L. Perret, and H. Imai. Algebraic cryptanalysis of
58-round SHA-1. FSE 2007, LNCS 4593, pp. 349–365.
[28] B.-Y. Yang and J.-M. Chen. Theoretical analysis of XL over small fields. ACISP
2004, LNCS 3108, pp. 277–288.
[29] B.-Y. Yang, J.-M. Chen, and N. Courtois, On Asymptotic Security Estimates
in XL and Gröbner Bases-Related Algebraic Cryptanalysis, ICICS 2004, LNCS
3269, pp. 401-413.