請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/1127
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 鄭振牟(Chen-Mou Cheng) | |
dc.contributor.author | Ming-Shing Chen | en |
dc.contributor.author | 陳明興 | zh_TW |
dc.date.accessioned | 2021-05-12T09:32:58Z | - |
dc.date.available | 2018-09-01 | |
dc.date.available | 2021-05-12T09:32:58Z | - |
dc.date.copyright | 2018-08-10 | |
dc.date.issued | 2018 | |
dc.date.submitted | 2018-08-07 | |
dc.identifier.citation | [ABH10] Martin R. Albrecht, Gregory V. Bard, and William Hart. Algorithm 898: Efficient multiplication of dense matrices over GF(2). ACM Trans.Math. Softw., 37(1):9:1–9:14, 2010.
[AH74] Alfred V. Aho and John E. Hopcroft. The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1974. [AJ86] Leonard M. Adleman and Hendrik W. Lenstra Jr. Finding irreducible polynomials over finite fields. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 350–355. ACM, 1986. [Anv11] H. Peter Anvin. The mathematics of RAID-6, 2011. http://kernel. org/pub/linux/kernel/people/hpa/raid6.pdf. [ASI08] A.A. Al-Shaikhi and J. Ilow. Packet loss recovery codes based on vandermonde matrices and shift operators. In Information Theory, 2008. ISIT 2008. IEEE International Symposium on, pages 1058–1062, July 2008. [BC14] Daniel J. Bernstein and Tung Chou. Faster binary-field multiplication and faster binary-field macs. In Antoine Joux and Amr M. Youssef, editors, Selected Areas in Cryptography - SAC 2014 - 21st International Conference, Montreal, QC, Canada, August 14-15, 2014, Revised Selected Papers, volume 8781 of Lecture Notes in Computer Science, pages 92–111. Springer, 2014. [BCS13] Daniel J. Bernstein, Tung Chou, and Peter Schwabe. fast constant-time code-based cryptography. Mcbits: In Guido Bertoni and Jean-Sébastian Coron, editors, Cryptographic Hardware and Embedded Systems – CHES 2013, Lecture Notes in Computer Science. Springer-Verlag Berlin Heidelberg, 2013. Document ID: 801a97c500b3ac879d77bcecf054ce5, http://cryptojedi.org/papers/#mcbits. [BD08] Johannes Buchmann and Jintai Ding, editors. Post-Quantum Cryptography, Second International Workshop, PQCrypto 2008, Cincinnati,OH, USA, October 17-19, 2008, Proceedings, volume 5299 of Lecture Notes in Computer Science. Springer, 2008. [BDL + 11] Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. High-speed high-security signatures. In Bart Preneel and Tsuyoshi Takagi, editors, CHES, volume 6917 of Lecture Notes in Computer Science, pages 124–142. Springer, 2011. [Ber08] Daniel J Bernstein. Fast multiplication and its applications. Algorithmic number theory, 44:325–384, 2008. [BFSY05] 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. In P. Gianni, editor, MEGA 2005 Sardinia (Italy), 2005. [BGP06] Côme Berbain, Henri Gilbert, and Jacques Patarin. QUAD: A practical stream cipher with provable security. In Serge Vaudenay, editor, EUROCRYPT, volume 4004 of Lecture Notes in Computer Science, pages 109–128. Springer, 2006. [BGTZ08] Richard P Brent, Pierrick Gaudry, Emmanuel Thomé, and Paul Zimmermann. Faster multiplication in gf (2)(x). Lecture Notes in Computer Science, 5011:153–166, 2008. [BL16] Daniel J. Bernstein and Tanja Lange. eBACS: Ecrypt benchmarking of cryptographic systems. http://bench.cr.yp.to, July 2016. Accessed May 10, 2017. [BM06] Joseph Bonneau and Ilya Mironov. Cache-collision timing attacks against AES. In Louis Goubin and Mitsuru Matsui, editors, Cryptographic Hardware and Embedded Systems - CHES 2006, 8th International Workshop, Yokohama, Japan, October 10-13, 2006, Proceedings, volume 4249 of Lecture Notes in Computer Science, pages 201–215. Springer, 2006. [Can89] David G. Cantor. On arithmetical algorithms over finite fields. J. Comb. Theory Ser. A, 50(2):285–300, March 1989. [CCC + 08] Anna Inn-Tung Chen, Chia-Hsin Owen Chen, Ming-Shing Chen, Chen-Mou Cheng, and Bo-Yin Yang. Practical-sized instances of multivariate PKCs: Rainbow, TTS, and lIC-derivatives. In Buchmann and Ding [BD08], pages 95–108. [CCC + 09] Anna Inn-Tung Chen, Ming-Shing Chen, Tien-Ren Chen, Chen-Mou Cheng, Jintai Ding, Eric Li-Hsiang Kuo, Frost Yu-Shuang Lee, and Bo-Yin Yang. SSE implementation of multivariate PKCs on modern x86 CPUs. In CHES 2009, pages 33–48, Lausanne, Switzerland, September 2009. [CCK + 17] Ming-Shing Chen, Chen-Mou Cheng, Po-Chun Kuo, Wen-Ding Li, and Bo-Yin Yang. Faster multiplication for long binary polynomials. CoRR, abs/1708.09746, 2017. [CJL 16] L. Chen, S. Jordan, Y.K. Liu, D. Moody, R. Peralta, R. Perlner, and D. Smith-Tone. Report on post-quantum cryptography. https://doi.org/10.6028/NIST.IR.8105, 2016. [CK91] David G. Cantor and Erich Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica, 28:693–701, 1991. [CKPS00] Nicolas T. Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir. Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In Advances in Cryptology — EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 392–407. Bart Preneel, ed., Springer, 2000. Extended Version: http://www.minrank.org/xlfull.pdf. [CLP + 18] Ming-Shing Chen, Wen-Ding Li, Bo-Yuan Peng, Bo-Yin Yang, and Chen-Mou Cheng. Implementing 128-bit secure MPKC signatures. IEICE Transactions, 101-A(3):553–569, 2018. [CLRS09] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. [CYC13] Ming-Shing Chen, Bo-Yin Yang, and Chen-Mou Cheng. Raidq: A software-friendly, multiple-parity raid. In Presented as part of the 5th USENIX Workshop on Hot Topics in Storage and File Systems, Berkeley, CA, 2013. USENIX. [DS05] Jintai Ding and Dieter Schmidt. Rainbow, a new multivariable polynomial signature scheme. In Conference on Applied Cryptography and Network Security — ACNS 2005, volume 3531 of Lecture Notes in Computer Science, pages 164–175. Springer, 2005. [DY08] Jintai Ding and Bo-Yin Yang. Multivariate public key cryptography. In Post Quantum Cryptography (Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen, eds.), pages 193–241. Springer-Verlag Berlin, 1st edition, 2008. ISBN 3-540-88701-6. [DYC + 08] Jintai Ding, Bo-Yin Yang, Chia-Hsin Owen Chen, Ming-Shing Chen, and Chen-Mou Cheng. New differential-algebraic attacks and reparametrization of rainbow. In Applied Cryptography and Network Security, volume 5037 of Lecture Notes in Computer Science, pages 242–257. Springer, 2008. cf. http://eprint.iacr.org/2008/108. [Fau02] Jean-Charles Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F 5 ). In International Symposium on Symbolic and Algebraic Computation — ISSAC 2002, pages 75–83. ACM Press, July 2002. [GG13] Joachim von zur Gathen and Jrgen Gerhard. Modern Computer Algebra. Cambridge University Press, New York, NY, USA, 3rd edition, 2013. [GJ79] Michael R. Garey and David S. Johnson. Computers and Intractability — A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979. ISBN 0-7167-1044-7 or 0-7167-1045-5. [GK14] Shay Gueron and Michael E. Kounavis. Intel(r) carry-less multiplication instruction and its usage for computing the gcm mode(rev.2.02), April 2014. https://software.intel.com/sites/default/files/managed/72/cc/clmul-wp-rev-2.02-2014-04-20.pdf. [GM10] Shuhong Gao and Todd D. Mateer. Additive fast fourier transforms over finite fields. IEEE Trans. Information Theory, 56(12):6265–6272, 2010. [GRU14] S.M. Gunther, M. Riemensberger, and W. Utschick. Efficient gf arithmetic for linear network coding using hardware simd extensions. In Network Coding (NetCod), 2014 International Symposium on, pages 1–6, June 2014. [HvdHL16] David Harvey, Joris van der Hoeven, and Grégoire Lecerf. Fast polynomial multiplication over F 2 60 . In Sergei A. Abramov, Eugene V. Zima, and Xiao-Shan Gao, editors, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2016, Waterloo, ON, Canada, July 19-22, 2016, pages 255–262. ACM, 2016. [HvdHL17] David Harvey, Joris van der Hoeven, and Grégoire Lecerf. Faster polynomial multiplication over finite fields. J. ACM, 63(6):52:1–52:23, 2017. [Int15] Intel. Intel architecture instruction set extensions programming reference, August 2015. https://software.intel.com/sites/default/files/managed/07/b7/319433-023.pdf. [LANH16] Sian-Jheng Lin, Tareq Y. Al-Naffouri, and Yunghsiang S. Han. Fft algorithm for binary extension finite fields and its application to reed–solomon codes. IEEE Trans. Inf. Theor., 62(10):5343–5358, October 2016. [LCH14] Sian-Jheng Lin, Wei-Ho Chung, and Yunghsiang S. Han. Novel polynomial basis and its application to reed-solomon erasure codes. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 316–325. IEEE Computer Society, 2014. [LCK + 18] Wen-Ding Li, Ming-Shing Chen, Po-Chun Kuo, Chen-Mou Cheng, and Bo-Yin Yang. Frobenius additive fast fourier transform. In Manuel Kauers, Alexey Ovchinnikov, and Éric Schost, editors, Proceedings of the 2018 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2018, New York, NY, USA, July 16-19, 2018, pages 263–270. ACM, 2018. [LF04] Jérome Lacan and Jérome Fimes. Systematic mds erasure codes based on vandermonde matrices. IEEE Communications Letters, 8(9):570–572, 2004. [LK16] Daniel Lemire and Owen Kaser. Faster 64-bit universal hashing using carry-less multiplications. J. Cryptographic Engineering, 6(3):171–185, 2016. [LLY08] Feng-Hao Michael Liu, Chi-Jen Lu, and Bo-Yin Yang. Secure PRNGs from specialized polynomial maps over any GF(q). In Buchmann and Ding [BD08], pages 95–106. [LN86] Rudolf Lidl and Harald Niederreiter. Introduction to Finite Fields and Their Applications. Cambridge University Press, New York, NY, USA, 1986. [Nat01] National Institute of Standards and Technology. Announcing the advanced encryption standard (aes), 2001. federal information processing standards publication 197. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf, 2001. [oST16] National Institute of Standards and Technology. Submission requirements and evaluation criteria for the post-quantum cryptography standardization process,2016. http://csrc.nist.gov/groups/ST/post-quantum-crypto/documents/call-for-proposals-final-dec-2016.pdf. [PBB10] Albrecht Petzoldt, Stanislav Bulygin, and Johannes Buchmann. Selecting parameters for the rainbow signature scheme. In Nicolas Sendrier, editor, PQCrypto, volume 6061 of Lecture Notes in Computer Science, pages 218–240. Springer, 2010. [PD05] James S. Plank and Ying Ding. Note: Correction to the 1997 tutorial on Reed-Solomon coding. Software: Practice and Experience, 35(2):189–194, February 2005. [PGM13] J. S. Plank, K. M. Greenan, and E. L. Miller. Screaming fast Galois Field arithmetic using Intel SIMD instructions. In FAST 2013, San Jose, CA, USA, February 2013. [Pla97] James S. Plank. A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems. Software: Practice and Experience, 27(9):995–1012, September 1997. [Riz97] Luigi Rizzo. Effective erasure codes for reliable computer communication protocols. SIGCOMM Comput. Commun. Rev., 27(2):24–36, April 1997. [Sch77] Arnold Schönhage. Schnelle multiplikation von polynomen über körpern der charakteristik 2. Acta Informatica, 7(4):395–398, 1977. [Sch11] Peter Schwabe. High-Speed Cryptography and Cryptanalysis. PhD thesis, Eindhoven University of Technology, 2011.http://cryptojedi.org/users/peter/thesis/. [Sho97] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, October 1997. [vdHL17] Joris van der Hoeven and Robin Larrieu. The frobenius FFT. In Michael A. Burr, Chee K. Yap, and Mohab Safey El Din, editors, Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2017, Kaiserslautern, Germany, July 25-28, 2017, pages 437–444. ACM, 2017. [vdHLL17] Joris van der Hoeven, Robin Larrieu, and Grégoire Lecerf. Implementing fast carryless multiplication. In Johannes Blömer, Ilias S. Kotsireas, Temur Kutsia, and Dimitris E. Simos, editors, Mathe-matical Aspects of Computer and Information Sciences - 7th International Conference, MACIS 2017, Vienna, Austria, November 15-17, 2017, Proceedings, volume 10693 of Lecture Notes in Com- puter Science, pages 121–136. Springer, 2017. [War12] Henry S. Warren. Hacker’s Delight. Addison-Wesley Professional, 2nd edition, 2012. [Wol04] Christopher Wolf. Efficient public key generation for HFE and variations. In Ed Dawson and Wolfgang Klemm, editors, Cryptographic Algorithms and their Uses - 2004, International Workshop, Gold Coast, Australia, July 5-6, 2004, Proceedings, pages 78–93. Queensland University of Technology, 2004. [YC05] Bo-Yin Yang and Jiun-Ming Chen. Building secure tame-like multivariate public-key cryptosystems: The new TTS. In ACISP 2005, volume 3574 of Lecture Notes in Computer Science, pages 518–531. Springer, July 2005. [YCBC07] Bo-Yin Yang, Owen Chia-Hsin Chen, Daniel J. Bernstein, and Jiun-Ming Chen. Analysis of QUAD. In Alex Biryukov, editor, FSE,volume 4593 of Lecture Notes in Computer Science, pages 290–307. Springer, 2007. [YCC04] Bo-Yin Yang, Jiun-Ming Chen, and Nicolas Courtois. On asymp-totic security estimates in XL and Gröbner bases-related algebraic cryptanalysis. In ICICS 2004, volume 3269 of Lecture Notes in Computer Science, pages 401–413. Springer, Oct. 2004. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/handle/123456789/1127 | - |
dc.description.abstract | 本論文旨在研究使用現代電腦的向量指令集及無進位乘法來建構特徵值為二的有限體乘法,以及各種不同有限體乘法的應用。我們討論了有限體的不同表示法,以及在這些表示法之下,基於現代電腦考量下的有限體乘法的實現方法。
我們呈現了四種應用,分別對應到不同的有限體乘法實現方式。 最先呈現的應用是設計給磁碟陣列(RAID)使用的錯誤更正碼(erasure correcting code),此種錯誤更正碼現在標準磁碟陣列的錯誤更正碼的推廣,並且能有效的提昇標準編碼在四個冗餘(checksum)時的磁碟數量,從最大支援二十八磁碟推展到可支援九十六個磁碟。在這裡我們展示了使用向量指令實現有限體乘法的標準作法。 第二個應用是實作一種可以抵抗量子電腦攻擊的多變量公鑰密碼系統(MPKCs)--Rainbow,在這應用中我們主要討論在安全軟體的要求下時,有限體乘法的實現方式,以及實現多變量密碼時的矩陣乘法,多元二次多項式組的求值,和求解線性方程組時的程式寫法。 第三是討論加法性快速傅立葉變換(additive FFT)的程式實現,我們介紹使用additive FFT來求多項式的值的方法,以及如何實作一個高效率的additive FFT的方式。在這裡我們使用了乘有限體的子體(subfield)中的元素的加速方法。 最後一個應用是實作係數只能為一或零的多項式(Boolean Polynomial)的乘法器,在這裡我們結合了additive FFT及Frobenius FFT的技巧,提出了一個可以帶比較少的點至多項式就能計算乘法的的方法,並且展示了在additive FFT上帶那樣的點,就等於刪節了一些計算的FFT(truncated additive FFT),還有這些演算法的實現方式。這裡使用的有限體乘法是單純的使用硬體的無進位乘法來實現。這個應用同時也是我們再做更大的有限體乘法的關鍵元件。 | zh_TW |
dc.description.abstract | We study the multiplication in the extension fields of characteristic 2 with the vector instruction set and carryless multiplication on modern computers and their applications. We describe the representations of fields in polynomial forms and vector spaces and the implementations for these representations.
We present four applications corresponding to 4 different implementations of field multiplication. The first application is an erasure correcting code-- RAIDq, an extension of currently standard code in RAID-6, for the RAID. It supports a RAID system of 96 disks for the case of 4 checksums while it can only be 28 disks for current code. We show the standard implementations for multiplication in binary fields in the application. In the second application, we implement the Rainbow, a derivate of MPKCs which is believed a candidate of post-quantum cryptography. We discuss the implementation of multiplication under the requirement of secure software. We also present matrix-vector multiplication, evaluating quadratic systems, and solving linear equations under the crypto consideration. In the third application, we introduce the additive FFT for evaluating polynomials at a particular set and implement an efficient additive FFT as well. We utilize the acceleration for multiplying subfield elements in the implementation. The last application presents a multiplier for Boolean polynomials. We give a specific set for evaluating polynomials with the additive FFT, allowing to derive other values of polynomials by Frobenius map. We show the multiplication of Boolean polynomials by evaluating polynomials at the particular set. The evaluation can be performed with a truncated additive FFT. We implement the field multiplication with the instruction of carrayless multiplication here. The last application can also be a critical component for multiplication in the fields of larger size. | en |
dc.description.provenance | Made available in DSpace on 2021-05-12T09:32:58Z (GMT). No. of bitstreams: 1 ntu-107-D98921021-1.pdf: 1319930 bytes, checksum: b90e6bbd8332f887ebcc3bc04aec57a7 (MD5) Previous issue date: 2018 | en |
dc.description.tableofcontents | 1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 The Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 Codes for RAID . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.2 MPKCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.3 The Additive FFT and its Implementations . . . . . . . . . . 4 1.2.4 Multiplying Boolean Polynomials . . . . . . . . . . . . . . . . 5 1.3Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Preliminaries 7 2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 The Construction of Binary Fields . . . . . . . . . . . . . . . . . . . . 8 2.2.1 The Polynomial Constructions . . . . . . . . . . . . . . . . . . 8 2.2.2 Finite Field as Linear Space . . . . . . . . . . . . . . . . . . . 13 2.3 Selected Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.1 Bit Operations: Multiplications in F 2 and F 4 . . . . . . . . . . 18 2.3.2 Instruction for Multiplying Boolean Polynomials . . . . . . . . 18 2.3.3 Exploiting Data-level Parallelism . . . . . . . . . . . . . . . . 19 2.3.4 SIMD Table Lookup Instruction . . . . . . . . . . . . . . . . . 20 2.4Fast Linear Algebra with Vector Instructions . . . . . . . . . . . . . . 21 2.4.1 Matrix Transpose . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.2 Linear Transformation over F 2 . . . . . . . . . . . . . . . . . . 22 3 Multiplication in Binary Fields 27 3.1 Multiplication in F 2 m for m ≤ 16 . . . . . . . . . . . . . . . . . . . . 27 3.1.1 Field Multiplication as Linear Transformation . . . . . . . . . 28 3.1.2 Multiplication in F 256 . . . . . . . . . . . . . . . . . . . . . . . 29 3.1.3 Multiplication in F 256 2 . . . . . . . . . . . . . . . . . . . . . . 31 3.2 Multiplication in Tower Fields . . . . . . . . . . . . . . . . . . . . . . 34 3.2.1 Multiplication in F16 and F256 . . . . . . . . . . . . . . . . . . 35 3.2.2 Decomposing Field Multiplication over F256 . . . . . . . . . . 35 3.2.3 Subfield Multiplication in Tower Fields . . . . . . . . . . . . . 36 3.2.4 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3 Constant-time Multiplication in Binary Fields . . . . . . . . . . . . . 38 3.3.1 Multiplication with Logarithm Tables . . . . . . . . . . . . . . 38 3.3.2 Generating Multiplication Tables On-the-fly . . . . . . . . . . 39 3.4 Multiplication in F2m for m = 64 and 128 . . . . . . . . . . . . . . . . 41 4 Codes for RAID 45 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.1.1 The Problem of Plank’s Code . . . . . . . . . . . . . . . . . . 46 4.1.2 Our Solution: the RAIDq Code . . . . . . . . . . . . . . . . . 47 4.1.3 Chapter Overview . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2 Extending RAID-6 for More Checksums . . . . . . . . . . . . . . . . 48 4.2.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2.2 Plank’s code . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.2.3 About MDS property of Plank’s code . . . . . . . . . . . . . . 50 4.2.4 Plank’s Code for RAID: the Successful Cases . . . . . . . . . . 51 4.2.5 Plank’s Code for RAID: the 4th Checksums . . . . . . . . . . 51 4.2.6 RAIDq with 4 Checksums . . . . . . . . . . . . . . . . . . . . 52 4.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.3.1 Encoding and decoding Plank’s codes . . . . . . . . . . . . . . 53 4.3.2 Implementing the Encoder . . . . . . . . . . . . . . . . . . . . 54 4.3.3 Erasure Decoder . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.4 Experiments and Discuss . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.4.1 The Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.4.3 Discuss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5 Implementing MPKCs 63 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.1.1 The Requirements on Post-Quantum Security . . . . . . . . . 63 5.1.2 Challenge in Cryptographic Software . . . . . . . . . . . . . . 64 5.1.3 Chapter Objectives . . . . . . . . . . . . . . . . . . . . . . . . 64 5.1.4 Chapter Overview . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.2 Backgrounds on MPKC Signatures . . . . . . . . . . . . . . . . . . . 65 5.2.1 MPKCs and its Security . . . . . . . . . . . . . . . . . . . . . 65 5.2.2 Recap of MPKC Signatures . . . . . . . . . . . . . . . . . . . 66 5.2.3 The Rainbow Signature . . . . . . . . . . . . . . . . . . . . . 67 5.3 Implementing Components for Rainbow . . . . . . . . . . . . . . . . . 70 5.3.1 Matrix-vector Multiplication . . . . . . . . . . . . . . . . . . . 71 5.3.2 Evaluating Quadratic Systems . . . . . . . . . . . . . . . . . . 71 5.3.3 Solving Linear Equations . . . . . . . . . . . . . . . . . . . . . 74 5.4 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.4.1 The Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6 Additive FFT 79 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.1.1 FFTs over Binary Fields . . . . . . . . . . . . . . . . . . . . . 80 6.1.2 The Development of Additive FFTs . . . . . . . . . . . . . . . 81 6.1.3 Overview of this chapter . . . . . . . . . . . . . . . . . . . . . 82 6.2 Subspace Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6.3 The Additive FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.3.1 The novelpoly Basis w.r.t. Subspace Polynomials . . . . . . . 84 6.3.2 Evaluating Polynomials in the novelpoly Basis . . . . . . . . . 85 6.3.3 Converting Polynomial Bases . . . . . . . . . . . . . . . . . . 88 6.3.4 The addFFT Algorithm . . . . . . . . . . . . . . . . . . . . . 91 6.4 Implementing the Additive FFT . . . . . . . . . . . . . . . . . . . . . 91 6.4.1 Performing the Butterflies . . . . . . . . . . . . . . . . . . . . 92 6.4.2 Performing the Basis Conversion . . . . . . . . . . . . . . . . 93 7 Multiplication of Boolean Polynomials 97 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 7.1.1 Previous Multiplications for Boolean Polynomials . . . . . . . 98 7.1.2 The Practical Complexity Model . . . . . . . . . . . . . . . . 99 7.1.3 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . 100 7.1.4 Chapter Overview . . . . . . . . . . . . . . . . . . . . . . . . . 100 7.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 7.2.1 The FFT Based Multiplication of Polynomials . . . . . . . . . 101 7.2.2 The Frobenius cross-section . . . . . . . . . . . . . . . . . . . 101 7.3 The Multiplication with Frobenius Cross-section and Additive FFT . 102 7.3.1 The Partition of Evaluating Points . . . . . . . . . . . . . . . 102 7.3.2 Truncated Additive FFT . . . . . . . . . . . . . . . . . . . . . 106 7.3.3 Encoding: the First l m Layers of the Truncated Butterfly . 107 7.3.4 Multiplying Boolean polynomials . . . . . . . . . . . . . . . . 109 7.4 The Implementation and Benchmarks . . . . . . . . . . . . . . . . . . 110 7.4.1 The Implementation . . . . . . . . . . . . . . . . . . . . . . . 110 7.4.2 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Bibliography 115 | |
dc.language.iso | en | |
dc.title | 現代電腦中的有限體乘法及其應用 | zh_TW |
dc.title | Multiplication in Binary Fields on Modern Computers and its Applications | en |
dc.type | Thesis | |
dc.date.schoolyear | 106-2 | |
dc.description.degree | 博士 | |
dc.contributor.oralexamcommittee | 韓永祥(Yunghsiang S. Han),鍾偉和(Wei-Ho Chung),楊柏因(Bo-Yin Yang),鐘楷閔(Kai-Min Chung) | |
dc.subject.keyword | 乘法,有限體,磁碟陣列,多變量公鑰密碼,快速傅立葉變換,Boolean多項式, | zh_TW |
dc.subject.keyword | Multiplication,Finite Field,RAID,MPKC,FFT,Boolean Polynomial, | en |
dc.relation.page | 123 | |
dc.identifier.doi | 10.6342/NTU201801305 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2018-08-08 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-107-1.pdf | 1.29 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。