应对反应攻击的级联中密度准循环奇偶校验码公钥方案

doi:10.11772/j.issn.1001-9081.2021010023

《计算机应用》唯一官方网站 ›› 2021, Vol. 41 ›› Issue (11): 3274-3280.DOI: 10.11772/j.issn.1001-9081.2021010023

应对反应攻击的级联中密度准循环奇偶校验码公钥方案

巫光福(), 戴子恒

江西理工大学信息工程学院，江西赣州 341000

收稿日期:2021-01-07 修回日期:2021-04-21 接受日期:2021-04-28 发布日期:2021-05-12 出版日期:2021-11-10
通讯作者: 巫光福
作者简介:戴子恒（1995—），男，湖南津市人，硕士研究生，主要研究方向：信道编码、密码学与信息安全。
基金资助:
国家自然科学基金资助项目(11461031);江西省教育厅科技类重点项目(GJJ170492)

Cascaded quasi-cyclic moderate-density parity-check code based public key scheme for resisting reaction attack

Guangfu WU(), Ziheng DAI

School of Information Engineering，Jiangxi University of Science and Technology，Ganzhou Jiangxi 341000，China

Received:2021-01-07 Revised:2021-04-21 Accepted:2021-04-28 Online:2021-05-12 Published:2021-11-10
Contact: Guangfu WU
About author:DAI Ziheng， born in 1995， M. S. candidate. His research interests include channel coding， cryptography and information security.
Supported by:
the National Natural Science Foundation of China(11461031);the Science and Technology Key Project of the Education Department of Jiangxi Province(GJJ170492)

摘要/Abstract

摘要：

基于中密度准循环奇偶校验（QC-MDPC）码的McEliece公钥密码（PKC）方案具有较小的密钥量，利于存储，是一类在抵抗量子攻击上发展前景良好的公钥密码体制。然而目前存在一种反应攻击对其安全性产生了较大威胁。攻击者选取特殊的错误图样对大量消息进行加密以获得接收者反馈的译码失败情况，然后通过分析译码失败率与私钥结构的关系从而破解出私钥，该攻击被称为密钥恢复攻击。为应对此攻击，提出了一种将QC-MDPC码与喷泉码进行级联的公钥方案。该方案利用喷泉码的“无码率性”生成大量的加密包来取代反馈重发（ARQ）结构，使攻击者无法获取反馈信息。分析结果表明，所提出的方案能有效抗击密钥恢复攻击，同时还能保证在其他攻击下的安全性。

关键词: 中密度准循环奇偶校验码, 量子攻击, 密钥恢复攻击, 喷泉码, 公钥密码体制

Abstract:

The McEliece Public Key Cryptography （PKC） based on Quasi-Cyclic Moderate-Density Parity-Check （QC-MDPC） code is a promising scheme to resist quantum attack with small key size， so it is easy to storage. However， a reaction attack has a great threat to its security currently. The attacker selects some special error patterns to encrypt numerous messages to obtain the decoding failure feedback from the receiver， and then cracks the private key by analyzing the relationship between the decoding failure rate and the private key structure. This attack is called key recovery attack. In response to this attack， a new public key scheme cascading QC-MDPC code and fountain code was proposed. In the scheme， the “rateless characteristic” of fountain code was used to generate abundant encrypted packets which were used to substituted for the Automatic Repeat-reQuest （ARQ） structure， so that the attacker was not able to achieve the feedback information. The analysis results show that the proposed scheme can effectively resist key recovery attack and guarantee the security under other attacks as well.

Key words: Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC) code, quantum attack, key recovery attack, fountain code, Public Key Cryptography (PKC)

中图分类号:

TP309.7

巫光福, 戴子恒. 应对反应攻击的级联中密度准循环奇偶校验码公钥方案[J]. 计算机应用, 2021, 41(11): 3274-3280.

Guangfu WU, Ziheng DAI. Cascaded quasi-cyclic moderate-density parity-check code based public key scheme for resisting reaction attack[J]. Journal of Computer Applications, 2021, 41(11): 3274-3280.

图/表 9

图1 QC-MDPC码的校验矩阵H

Fig. 1 Check matrix H of QC-MDPC code

表1 不同安全级别下的QC-MDPC码参数

Tab. 1 Parameters of QC-MDPC code under different security levels

安全级别	n	k	w	t
80-bit	9 602	4 801	90	84
128-bit	19 714	9 857	142	134
256-bit	65 542	32 771	274	264

图2 LT码编码示意图

Fig. 2 Schematic diagram of LT code encoding

图3 Raptor码编码示意图

Fig. 3 Schematic diagram of Raptor code encoding

表2 三种度分布函数的比较

Tab. 2 Comparison of three degree distribution functions

δ a v g

度一分布

f 1 (1) = 1

n l n (n / γ)

理想孤子分布

f I (δ) = 1 / n, δ = 1 1 / δ ⋅ (δ - 1), δ = 2,3, …, n

ln（n）

鲁棒孤子分布

$f R (δ) = f I (δ) + ρ (δ) ∑ δ = 1 n (f I (δ) + ρ (δ))$

$ρ (δ) = s / n δ, δ = 1, 2, …, n / s - 1 s l n (s / γ) / n, δ = n / s 0, δ > n / s$

$s = α l n (n / δ) n$

n + O (n ⋅ l n 2 (n / γ))

O (l n (n / γ))

表2 三种度分布函数的比较

Tab. 2 Comparison of three degree distribution functions

度分布函数

分布函数f

编码分组数x

平均度数

δ a v g

度一分布

f 1 (1) = 1

n l n (n / γ)

理想孤子分布

f I (δ) = 1 / n, δ = 1 1 / δ ⋅ (δ - 1), δ = 2,3, …, n

ln（n）

鲁棒孤子分布

$f R (δ) = f I (δ) + ρ (δ) ∑ δ = 1 n (f I (δ) + ρ (δ))$

$ρ (δ) = s / n δ, δ = 1, 2, …, n / s - 1 s l n (s / γ) / n, δ = n / s 0, δ > n / s$

$s = α l n (n / δ) n$

n + O (n ⋅ l n 2 (n / γ))

O (l n (n / γ))

图4 Raptor码的编译码系统流程

Fig. 4 Flow chart of Raptor code encoding/decoding system

图5 本文方案实现流程

Fig. 5 Realization flow chart of proposed scheme

图6 方案译码开销与译码成功率关系

Fig. 6 Relation between decoding overhead and decoding success rate

表3 不同抵抗GJS攻击方案的特性比较

Tab. 3 Characteristic comparison of different schemes against GJS attack

方案	密钥量（128-bit）	密钥类型	抗击特点
级联QC-MDPC码	约 $108$	静态密钥	利用喷泉码隐藏原公钥结构
ParQ	32 752	静态密钥	平行密钥封装后译码失败率达到安全标准
CAKE	65 542	动态密钥	消息传输过程不断更新密钥
BIKE-1	65 504	静/动态密钥	在CAKE基础上使用更优译码器来保证译码失败率可忽略

表3 不同抵抗GJS攻击方案的特性比较

Tab. 3 Characteristic comparison of different schemes against GJS attack

方案	密钥量（128-bit）	密钥类型	抗击特点
级联QC-MDPC码	约 $108$	静态密钥	利用喷泉码隐藏原公钥结构
ParQ	32 752	静态密钥	平行密钥封装后译码失败率达到安全标准
CAKE	65 542	动态密钥	消息传输过程不断更新密钥
BIKE-1	65 504	静/动态密钥	在CAKE基础上使用更优译码器来保证译码失败率可忽略

参考文献 24

1	BERNSTEIN D J， LANGE T. Post-quantum cryptography ［J］. Nature， 2017， 549（7671）： 188-194. 10.1038/nature23461
2	ALAGIC G， ALPERIN-SHERIFF J， APON D， et al. Status report on the second round of the NIST post-quantum cryptography standardization process： NISTIR 8309 ［R］. Gaithersburg： National Institute of Standards and Technology， 2020. 10.6028/nist.ir.8240
3	MCELIECE R J. A public-key cryptosystem based on algebraic coding theory： DSN progress report 42-44 ［R］. Pasadena： Jet Propulsion Laboratory， 1978： 114-116.
4	GALLAGER R. Low-density parity-check codes ［J］. IRE Transactions on Information Theory， 1962， 8（1）： 21-28. 10.1109/tit.1962.1057683
5	MONICO C， ROSENTHAL J， SHOKROLLAHI A. Using low density parity check codes in the McEliece cryptosystem ［C］// Proceedings of the 2000 IEEE International Symposium on Information Theory. Piscataway： IEEE， 2000： 215. 10.1109/isit.2000.866513
6	BALDI M， CHIARALUCE F， GARELLO R， et al. Quasi-cyclic low-density parity-check codes in the McEliece cryptosystem ［C］// Proceedings of the 2007 IEEE International Conference on Communications. Piscataway： IEEE， 2007： 951-956. 10.1109/icc.2007.161
7	MISOCZKI R， TILLICH J P， SENDRIER N， et al. MDPC-McEliece： new McEliece variants from moderate density parity-check codes ［C］// Proceedings of the 2013 IEEE International Symposium on Information Theory. Piscataway： IEEE， 2013： 2069-2073. 10.1109/isit.2013.6620590
8	GUO Q， JOHANSSON T， STANKOVSKI P. A key recovery attack on MDPC with CCA security using decoding errors ［C］// Proceedings of the 2016 International Conference on the Theory and Application of Cryptology and Information Security， LNCS10031. Berlin： Springer， 2016： 789-815.
9	BYERS J W， LUBY M， MITZENMACHER M， et al. A digital fountain approach to reliable distribution of bulk data ［J］. ACM SIGCOMM Computer Communication Review， 1998， 28（4）： 56-67. 10.1145/285243.285258
10	LUBY M. LT codes ［C］// Proceedings of the 2002 43rd Annual IEEE Symposium on Foundations of Computer Science. Piscataway： IEEE， 2002： 271-280. 10.1109/sfcs.2002.1181950
11	SHOKROLLAHI A. Raptor codes ［J］. IEEE Transactions on Information Theory， 2006， 52（6）： 2551-2567. 10.1109/tit.2006.874390
12	ZHANG M R. Major automatic repeat request protocols generalization and future develop direction ［C］// Proceedings of the 6th International Conference on Information Management， Innovation Management and Industrial Engineering. Piscataway： IEEE， 2013： 5-8. 10.1109/iciii.2013.6703196
13	BALDI M， BIANCHI M， CHIARALUCE F. Security and complexity of the McEliece cryptosystem based on quasi-cyclic low-density parity-check codes ［J］. IET Information Security， 2013， 7（3）： 212-220. 10.1049/iet-ifs.2012.0127
14	MUKHERJEE A. Hybrid ARQ schemes ［M/OL］// TAFAZOLLI R， CHATZIMISIOS P， WANG C L. Wiley 5G Ref： The Essential 5G Reference Online. （2020-05-16）［2020-11-23］..
15	EATON E， LEQUESNE M， PARENT A， et al. QC-MDPC： a timing attack and a CCA2 KEM ［C］// Proceedings of the 2018 International Conference on Post-Quantum Cryptography， LNCS10786. Cham： Springer， 2018： 47-76.
16	李艳霞.无线通信中的喷泉码技术研究［D］.成都：电子科技大学，2019：23-24.
	LI Y X. Research on fountain codes technology in wireless communication ［D］. Chengdu： University of Electronic Science and Technology of China， 2019：23-24.
17	孙玉情.QC-MDPC McEliece密码体制研究［D］.西安：西安电子科技大学，2019：35-44. 10.19734/j.issn.1001-3695.2018.04.0349
	SUN Y Q. Research on QC-MDPC McEliece cryptosystem ［D］. Xi’an： Xidian University， 2019：35-44. 10.19734/j.issn.1001-3695.2018.04.0349
18	MAY A， MEURER A， THOMAE E. Decoding random linear codes in Õ（2^0.054ⁿ）［C］// Proceedings of the 2011 International Conference on the Theory and Application of Cryptology and Information Security， LNCS7073. Berlin： Springer， 2011： 107-124.
19	OTMANI A， TILLICH J P， DALLOT L. Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes ［J］. Mathematics in Computer Science， 2010， 3（2）： 129-140. 10.1007/s11786-009-0015-8
20	BARDET M， DRAGOI V， LUQUE J G， et al. Weak keys for the quasi-cyclic MDPC public key encryption scheme ［C］// Proceedings of the 2016 International Conference on Cryptology in Africa， LNCS9646. Cham： Springer， 2016： 346-367.
21	FABŠIČ T， HROMADA V， STANKOVSKI P， et al. A reaction attack on the QC-LDPC McEliece cryptosystem ［C］// Proceedings of the 2017 International Workshop on Post-Quantum Cryptography， LNCS10346. Cham： Springer， 2017： 51-68.
22	BARRETO P S L M， GUERON S， GÜNEYSU T， et al. CAKE： Code-based Algorithm for Key Encapsulation ［C］// Proceedings of the 2017 IMA International Conference on Cryptography and Coding， LNCS10655. Cham： Springer， 2017： 207-226.
23	ARAGON N， BARRETO P， BETTAIEB S， et al. BIKE： bit flipping key encapsulation ［EB/OL］. （2017-12-22）［2020-11-23］. .
24	SENDRIER N， VASSEUR V. About low DFR for QC-MDPC decoding ［C］// Proceedings of the 2020 International Conference on Post-Quantum Cryptography， LNCS12100. Cham： Springer， 2020： 20-34.

[1]	郭阳楠, 蒋文保, 叶帅. 可监管的区块链匿名交易系统模型[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2757-2764.
[2]	张栖, 聂旭云. 立方多变量公钥密码体制的最小秩分析[J]. 计算机应用, 2020, 40(7): 1965-1969.
[3]	曹震寰, 顾小卓, 顾梦鹤. 面向Ad Hoc网络的无证书认证组密钥协商协议[J]. 计算机应用, 2019, 39(2): 476-482.
[4]	蓝锦佳, 韩益亮, 杨晓元. 基于多变量密码体制的签密方案[J]. 计算机应用, 2015, 35(2): 401-406.
[5]	李艳红高德智冯文文. 盲化的基于无证书的可验证加密签名方案[J]. 计算机应用, 2013, 33(12): 3519-3521.
[6]	孙华孟坤. 标准模型下可证安全的有效无证书签密方案[J]. 计算机应用, 2013, 33(07): 1846-1850.
[7]	葛荣亮高德智梁景玲张云. 无证书代理盲签名方案的安全性分析及改进[J]. 计算机应用, 2012, 32(03): 705-706.
[8]	杨磊鑫杜伟章. 基于QC-LDPC码的Niederreiter公钥密码体制[J]. 计算机应用, 2011, 31(07): 1906-1908.
[9]	向新银. 可认证的无证书密钥协商协议[J]. 计算机应用, 2008, 28(12): 3165-3167.

应对反应攻击的级联中密度准循环奇偶校验码公钥方案

Cascaded quasi-cyclic moderate-density parity-check code based public key scheme for resisting reaction attack

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 24

相关文章 9

编辑推荐

Metrics