量子电子学报 ›› 2021, Vol. 38 ›› Issue (4): 477-484.

• 量子光学 • 上一篇    下一篇

四元域上多项式乘法 Toom-3 算法及其在量子密钥分发中的应用

黄观金1, 周华旭1, 陈创波1, 高 鹏1, 凌 杰2∗   

  1. ( 1 南方电网调峰调频发电有限公司信息通信分公司, 广东 广州 510700; 2 安徽问天量子科技股份有限公司, 安徽 芜湖 210042 )
  • 收稿日期:2020-06-22 修回日期:2020-10-12 出版日期:2021-07-28 发布日期:2021-07-27
  • 通讯作者: E-mail: lingjie@qasky.com
  • 作者简介:黄观金( 1982 - ), 广东湛江人, 硕士, 高级工程师, 主要从事保密通信, 网络安全, 无线通信方面的研究。 E-mail: huanggj@em.pgc.csg

Toom-3 algorithm for polynomial multiplication over finite field F4 and its application on quantum key distribution

HUANG Guanjin1, ZHOU Huaxu1, CHEN Chuangbo1, GAO Peng1, LING Jie2∗   

  1. ( 1 CSG Power Generation Company Information Communication Branch, Guangzhou 510700, China; 2 Anhui Qasky Quantum Technology Co. Ltd, Wuhu 241002, China )
  • Received:2020-06-22 Revised:2020-10-12 Published:2021-07-28 Online:2021-07-27

摘要: 快速高效的安全增强方法在高速量子密钥分发 (QKD) 系统中有着相当重要的作用。实现安全增强一 般需要进行大数乘法、矩阵乘法或有限域乘法。其中基于有限域乘法的安全增强方法具有对随机数的数量需 求最低的优势, 但是其具体算法的复杂度相对偏高。提出了一种在四元域上实现多项式乘法的 Toom-3 算法, 并 推导了详细计算公式, 进而给出了一种新的基于四元域上多项式乘法的安全增强方法。该方法的时间复杂度为 O(n1.465), 表明其具有较好的复杂度并适合并行计算与硬件实现。

关键词: 量子光学, 安全增强, Toom-3 算法, 量子密钥分发, 有限域

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

中图分类号: