Name:Haining FAN

Title: Associate Professor

Email: fhn@tsinghua.edu.cn

Education background

Bachelor of Computer Science, Institute of Communications Engineering, Nanjing, China, 1992;

Master of Military Science, Institute of Communications Engineering, Nanjing, China, 1996;

Ph.D. in Computer Science, Tsinghua University, Beijing, China, 2005.

Areas of Research Interests/ Research Projects

Computer Arithmetic

Research Status

I have been dedicating myself to designing efficient computer arithmetic algorithms since the early 1990s. In collaboration with my coauthors, we had designed the unique best quadratic and subquadratic bit-parallel multipliers over most binary extension fields, which are used in Cryptography and Error-correcting Codes. In 2007, we were the first to use the Toeplitz matrix-vector product to multiply elements in finite fields, surpassing the Karatsuba algorithm in both space and time complexity. Our work on the overlap-free even-odd-splitting Karatsuba algorithm earned the IET Information Security Premium Award in 2012. This algorithm was later employed to evaluate the hardware efficiency of candidate algorithms during the NIST Post-Quantum Cryptography standardization process in 2023.

Academic Achievement

Survey and Book Chapter

[1] M. Hasan and Haining Fan: 《Handbook of Finite Fields》, Ch. 16.7, “Binary extension field arithmetic for hardware implementations”，CRC press, 2013 （Compiled by 88 international contributors.）

[2] Haining Fan and M. Hasan, “A survey of some recent bit-parallel GF(2^n) multipliers,” Finite Fields and Their Applications, vol. 32, pp. 5-43, March 2015 （Invited by the “Twenty Year Anniversary Edition”.）

Research Papers

[1] Haining Fan, Simple multiplication algorithm for a class of GF(2^n); IEE Electronics Letters, vol. 32, no.7, pp.636-637, 1996.

[2] Haining Fan and Yiqi Dai, Key function of normal basis multipliers in GF(2^n); IEE Electronics Letters, vol. 38, no.23, pp. 1431-1432, Nov. 2002.

[3] Haining Fan and Yiqi Dai, Low complexity bit-parallel normal bases multipliers for GF(2^n); IEE Electronics Letters, vol. 40, no.1, pp. 24-26, Jan. 2004.

[4] Haining Fan and Yiqi Dai, Normal basis multiplication algorithm for GF(2^n); IEE Electronics Letters, vol. 40, no.18, pp. 1112-1113, Aug. 2004.

[5] Haining Fan and Yiqi Dai, Fast bit-parallel GF(2^n) multiplier for all trinomials; IEEE Transactions on Computers, vol. 54, no. 4, pp. 485-490, Apr. 2005.

[6] Haining Fan, Duo Liu and Yiqi Dai, Two Software Normal Basis Multiplication Algorithms for GF(2^n); Tsinghua Science and Technology, vol. 11, no.3, pp. 264-270, 2006.

[7] Haining Fan and M. Hasan, Relationship between GF(2^m) Montgomery and Shifted Polynomial Basis Multiplication Algorithms; IEEE Transactions on Computers, vol. 55, no. 9, pp. 1202-1206, Sept. 2006.

[8] Haining Fan and M. Hasan, Fast Bit Parallel Shifted Polynomial Basis Multipliers in GF(2^n); IEEE Transactions on Circuits & Systems I: regular papers, vol.53, no.12, pp.2606-2615, 2006.

[9] Haining Fan and M. Hasan, A New Approach to Subquadratic Space Complexity Parallel Multipliers for Extended Binary Fields; IEEE Transactions on Computers, vol. 56, no. 2, pp. 224-233, Feb. 2007.

[10] Haining Fan and M. Hasan, Comments on ‘Five, Six, and Seven-Term Karatsuba-Like Formulae’; IEEE Transactions on Computers, vol. 56, no. 5, pp. 716-717, May 2007.

[11] Haining Fan and M. Hasan, Subquadratic computational complexity schemes for extended binary field multiplication using optimal normal bases; IEEE Transactions on Computers, vol. 56, no. 10, pp. 1435-1437, Oct. 2007.

[12] Haining Fan and M. Hasan, Alternative to the Karatsuba algorithm for software implementations of GF(2^n) multiplications; IET Information security, vol. 3, no. 2, pp. 60-65, 2009.

[13] Haining Fan, Jiaguang Sun, Ming Gu and Kwok-Yan Lam，Overlap-free Karatsuba-Ofman polynomial multiplication algorithms; IET Information security, vol. 4, no. 1, pp. 8-14, 2010. (Patent：ZL 2010 1 0279491.X Subquadratic polynomial multipliers based on the divide-and-conquer approach.)

[14] Haining Fan, Jiaguang Sun, Ming Gu and Kwok-Yan Lam, Obtaining More Karatsuba-Like Formulae over the Binary Field; IET Information security, vol. 6, no. 1, pp. 14-19, 2012.

[15] Cheng Su and Haining Fan, Impact of Intel's new instruction sets on software implementation of GF(2)[x] multiplication; Information Processing Letters, vol. 112, pp. 497-502, 2012.

[16] Xi Xiong and Haining Fan, GF(2^n) bit-parallel squarer using generalised polynomial basis for new class of irreducible pentanomials, IET Electronics Letters，Vol. 50，No. 9，pp. 655–656，2014.

[17] Jiangtao Han and Haining Fan, GF(2^n) Shifted Polynomial Basis Multipliers Based on Subquadratic Toeplitz Matrix-Vector Product Approach for All Irreducible Pentanomials, IEEE Transactions on Computers, vol. 64, pp. 862-867, March, 2015.

[18] Yongjia Wang, Xi Xiong and Haining Fan, GF(2^n) redundant representation using matrix embedding for irreducible trinomials, International Journal of Foundations of Computer Science, vol. 27, pp. 463-478，2016.

[19] Haining Fan, A Chinese Remainder Theorem Approach to Bit-Parallel GF(2^n) Polynomial Basis Multipliers for Irreducible Trinomials, IEEE Transactions on Computers, vol. 65, no.2, pp. 343-352，2016.

[20] Jiajun Zhang, Haining Fan, Low space complexity CRT-based bit-parallel GF(2^n) polynomial basis multipliers for irreducible trinomials, Integration - the VLSI Journal, vol. 58, pp. 55-63, 2017.

[21] Haining Fan, A trace based GF(2^n) inversion algorithm, IACR Cryptology ePrint Archive 2020-482, 2020.