Identification Scheme Based on the Binary Syndrome Decoding Problem Using High-Density Parity-Check Matrices
Identification Scheme Based on the Binary Syndrome Decoding Problem Using High-Density Parity-Check Matrices
复制标题
DOI：
10.1109/asiajcis.2019.00008
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
M. Hirotomo;Haruka Ito;Youji Fukuta;M. Mohri;Yoshiaki Shiraishi
中科院分区：
文献类型：
--
作者：
M. Hirotomo;Haruka Ito;Youji Fukuta;M. Mohri;Yoshiaki Shiraishi
大多数密码系统、识别和签名方案都依赖于离散对数问题和素因数分解问题。如果量子计算机出现，这些问题将通过肖尔的量子分解算法得到解决。基于代码的密码学是后量子密码学之一。有几种密码学可以通过使用具有循环结构的公共矩阵来减少密钥大小，但是已经提出了一些以循环结构为弱点的攻击。在本文中，我们提出了一种使用高密度奇偶校验（HDPC）矩阵的基于代码的识别方案。所提出的方案是基于二进制校正子解码（BSD）问题的Stern 识别方案的改进。在所提出的方案中，我们将 HDPC 矩阵应用于 BSD 问题，以防止使用迭代解码算法的攻击。此外，为了防止使用循环结构的攻击，我们构造了具有不同大小的循环子矩阵的多个块行的HDPC矩阵。此外，我们还评估了安全级别、密钥大小、计算成本和针对现有攻击的安全性。
Most of cryptosystems, identification and signature schemes rely on the discrete logarithm problem and the prime factorization problem. These problems would be broken through Shor's quantum factorization algorithm in the case that quantum computers would come to exist. Code-based cryptography is one of post-quantum cryptography. There are several cryptography to reduce the key size by using the public matrix with the circulant structure, but some attacks have been proposed with the circulant structure as a weak point. In this paper, we propose a code-based identification scheme using high-density parity-check (HDPC) matrices. The poposed scheme is an improvement of Stern's identification scheme based on the binary syndrome decoding (BSD) problem. In the proposed scheme, we apply HDPC matrices to the BSD problem in order to prevent attacks using iterative decoding algorithm. Also, to prevent attack using circulant structure, we construct HDPC matrices of multiple block-row with circulant submatrices of different size. Furthermore, we evaluate the security level, key size, computational cost and security against existing attacks.