請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10807
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 鄭振牟 | |
dc.contributor.author | Tung Chou | en |
dc.contributor.author | 周彤 | zh_TW |
dc.date.accessioned | 2021-05-20T22:00:34Z | - |
dc.date.available | 2010-07-21 | |
dc.date.available | 2021-05-20T22:00:34Z | - |
dc.date.copyright | 2010-07-21 | |
dc.date.issued | 2010 | |
dc.date.submitted | 2010-07-15 | |
dc.identifier.citation | [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. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10807 | - |
dc.description.abstract | 解多變量系統的問題在許多領域,包含代數攻擊和多變量密碼學,都具有重要的地位。然而,現存的演算法如 F4/F5 和 XL 雖然對於具有某些特性的系統效果特別顯著,但在面對一般的系統時,通常都無法有效率地解決問題,甚至會帶來嚴重的記憶體匱乏的問題。
基於上述的理由,我們便開始尋求另一個適合一般系統的解決方案,也就是窮舉搜尋 (exhaustive search) 的方式。在這篇論文中,我們提出並深入研究了一個窮舉搜尋的演算法 GGCE (generalized Gray code enumeration),用以解佈於二元體的多項式系統。這個演算法不僅相當易於平行化,對於解低次數的系統也有非常好的表現。對於這個演算法理論上的效能和記憶體需求等重要議題,在之後也會有深入的分析。 以實際面而言,我們將 GGCE 實作於顯示卡及 CPU 上。經過適當的最佳化之後,我們發現 GGCE 不僅在理論上相當有效率,實際的表現甚至遠勝過現有的演算法。換句話說,在面對一般系統時,窮舉搜尋可能是最好的解法。 簡而言之,我們提出了一個不同於以往的策略來解多變量系統。GGCE 證明了窮舉搜尋本身的強大能力,對於需要解多變量系統的眾多領域,勢必也會產生相當的影響。 | zh_TW |
dc.description.provenance | Made available in DSpace on 2021-05-20T22:00:34Z (GMT). No. of bitstreams: 1 ntu-99-R97921069-1.pdf: 460400 bytes, checksum: 3d6ec08d66f40d8bef199097ef5febe4 (MD5) Previous issue date: 2010 | en |
dc.description.tableofcontents | 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 | |
dc.language.iso | en | |
dc.title | 解佈於二元體之多項式方程組之快速窮舉法 | zh_TW |
dc.title | Fast Exhaustive Search for Polynomial Systems over F2 | en |
dc.type | Thesis | |
dc.date.schoolyear | 98-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 楊柏因,呂及人,顏嵩銘 | |
dc.subject.keyword | 顯示卡,代數攻擊,多變量密碼學,窮舉搜尋,平行化, | zh_TW |
dc.subject.keyword | algebraic cryptanalysis,multivariate cryptography,multivariate polynomials,solving systems of equations,exhaustive search,parallelization,CUDA,Graphic Processing Units (GPUs), | en |
dc.relation.page | 35 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2010-07-16 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf | 449.61 kB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。