基于Polar码的Niederreiter公钥密码体制  

Niederreiter Public Key Cryptosystem Based on Polar Codes

作　　者：杨超 肖东亮[1] 顾珍珍 储汪兵 YANG Chao;XIAO Dong-Liang;GU Zhen-Zhen;CHU Wang-Bing(College of Information and Electrical Engineering,China Agricultural University,Beijing 100083,China)

机构地区：[1]中国农业大学信息与电气工程学院,北京100083

出　　处：《密码学报》2018年第6期623-630,共8页Journal of Cryptologic Research

基　　金：国家自然科学基金(61271273;61671324)~~

摘　　要：近几年量子计算机取得了飞速发展,这势必会对传统密码学产生一定的影响,而基于纠错码的公钥密码体制被认为是一类可以抵抗量子攻击的密码体制.本文首先回顾了基于各种纠错码的公钥密码体制的研究背景,其次重点介绍了Polar码的SC快速译码算法,利用SC译码算法,提出了基于Polar码的Niederreiter公钥密码体制,其安全性建立在大矩阵分解困难性与线性分组码的译码是NP完全问题的双重基础上.该密码体制比基于其他纠错码的Niederreiter公钥密码体制复杂度更小、实现效率更高;通过仿真和安全性、计算效率上的分析得出该体制能抵御多种攻击,如解方程攻击、选择明文攻击和选择密文攻击等,是一种工作因子能达到2^(82)的密码体制,可以用在需要传输的信息量小,而对安全性要求高的场景.Quantum computers have made rapid progress in recent years,which is bound to have certain impact on traditional cryptography.Public-key cryptosystems based on error-correcting codes are considered to be a class of cryptosystems that can resist quantum attacks.This paper first reviews the research background of public-key cryptosystems based on various error-correcting codes,then the SC fast decoding algorithm of polar codes is introduced in detail.Using the SC decoding algorithm,a Niederreiter public key cryptosystem based on polar codes is designed.The security of the cryptosystem is based on the difficulty of large matrix decomposition and the NP-complete problem of decoding linear block codes,which are known as fundamental hard problems.The designed cryptosystem is less complex and more efficient than the Niederreiter public key cryptosystems based on other errorcorrecting codes,and can resist many kinds of attacks,such as equation-solving attack,chosen plaintext attack and chosen ciphertext attack.It is a cryptosystem with working factor up to 282,and can be used in scenarios where the amount of data to be transmitted is small and the security level is high.

关 键 词：公钥密码 Niederreiter体制 Polar码 SC译码算法 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]