Abstract: Fast and efficient privacy amplification plays an important role in high throughput quan- tum key distribution (QKD) system. In general, implementation of privacy amplification relies on large integer multiplication, binary matrix multiplication or polynomial multiplication over finite field. Espe- cially, privacy amplification based on polynomial multiplication has the advantage of low requirement on random number, while has relatively high implementation complexity. In this work, Toom-3 algorithm over finite field with four elements is developed and the corresponding explicit formula is derived, then a new privacy amplification method based on Toom-3 algorithm is presented. The time complexity of the method is O(n1.465), which indicates that the method is suitable for parallel computing and hardware implementaiton.

Key words: quantum optics, privacy amplification, Toom-3 algorithm, quantum key distribution, finite field