Seminar by Professor Fan Haining, Tsinghua University, China, RTP Harvard Room

Time: 23 Jan 2025, 2.00pm to 3.00pm

Venue: Research Techno Plaza (RTP), Level 2, Harvard Room

Title: Symmetries in Algebraic Computation

Bio: Haining Fan received both his B.Sc. and M.Sc. degrees in Computer Science from the Institute of Communications Engineering in 1992 and 1996, respectively. He earned his Ph.D. in Computer Science from Tsinghua University in 2005. From 2005 to 2006, Dr. Fan was a post-doctoral fellow at the University of Waterloo. He joined Tsinghua University in 2008 and he is now an Associate Professor in the Department of Computer Science. 

Dr. Fan’s research interests focus on cryptographic computation and computer arithmetic. He 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, he was 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. His work on the 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.

Abstract: Symmetry is an important property in algorithm design. In this talk, I will introduce four algorithms, which are used commonly in hardware and software implementation of cryptographic schemes. The first one is Montgomery’s modular multiplication algorithm. I will give a systematic explanation of this algorithm. The second one is an asymmetric Karatsuba formula used to design subquadratic multiplication algorithm. These two algorithms are derived from a generalized division algorithm. The third one is the additive FFT in finite field, serving as the counterpart to the widely used multiplicative FFT. Lastly, I will present a new additive inversion formula in finite field, which complements the popular multiplicative inversion formula based on Fermat’s little theorem. The elegant symmetry inherent in the last three algorithms provides opportunities for designing new and efficient algorithms.