The use of codes defined by sparse characteristic matrices, like QC-LDPC and QC-MDPC codes, has become an established solution to design secure and efficient code-based public-key encryption schemes, as also witnessed by the ongoing NIST post-quantum cryptography standardization process. However, similar approaches have been less fortunate in the context of code-based digital signatures, since no secure and efficient signature scheme based on these codes is available to date. The main limitation of previous attempts in this line of research has been the use of sparse signatures, which produces some leakage of information about the private key. In this paper, we propose a new code-based digital signature scheme that overcomes such a problem by publishing signatures that are abnormally dense, rather than sparse. This eliminates the possibility of deducing information from the sparsity of signatures, and follows a recent trend in code-based cryptography exploiting the hardness of the decoding problem for large-weight vectors, instead of its classical version based on small-weight vectors. In this study we focus on one-time use and provide some preliminary instances of the new scheme, showing that it achieves very fast signature generation and verification with reasonably small public keys.
翻译:使用诸如QC-LDPC和QC-MDPC等稀有特征矩阵定义的代码,已成为设计安全、高效的基于代码的公用钥匙加密办法的既定解决办法,目前正在进行的NIST后分子加密标准化进程也证明了这一点;然而,在基于代码的数字签字方面,类似的方法并不那么幸运,因为迄今为止还没有以这些代码为基础的安全和高效的签名办法;这一研究领域以往尝试的主要局限是使用稀疏的签名,这导致关于私人钥匙的一些信息泄漏。在本文件中,我们提出了一个新的基于代码的数字签名办法,通过出版异常密集而不是稀疏的签名克服了这样一个问题。这消除了从签名的广度中提取信息的可能性,并遵循了基于代码的加密的最新趋势,利用了大量病媒解密问题的难度,而不是基于小量病媒的经典版本。在这项研究中,我们侧重于一次性使用,并提供了一些新的基于代码的数字签名的初步实例,表明它能够以快速生成的方式实现快速的公用钥匙。