论文标题
通过具有限制错误的识别方案通往基于代码的签名的新途径
A New Path to Code-based Signatures via Identification Schemes with Restricted Errors
论文作者
论文摘要
在本文中，我们介绍了综合征解码问题（SDP）的变体，我们称为受限的SDP（R-SDP），其中在基础有限字段的子集中定义了搜索矢量的条目。我们通过减少经典SDP证明了R-SDP的NP完整性，并描述了解决此类问题的算法。我们以传统编码理论结果的方式研究了这种新解码视角下随机代码的属性，并评估求解随机R-SDP实例的复杂性。作为一个具体应用，我们描述了基于SDP的零知识识别（ZK-ID）方案如何可以调整以依靠R-SDP，并表明这导致了紧凑的公钥以及大大降低通信成本。因此，这些方案为通过富裕的菲亚特 - 沙米尔转型从身份方案得出的基于代码的数字签名方案的构建提供了改进的基础。
In this paper we introduce a variant of the Syndrome Decoding Problem (SDP), that we call Restricted SDP (R-SDP), in which the entries of the searched vector are defined over a subset of the underlying finite field. We prove the NP-completeness of R-SDP, via a reduction from the classical SDP, and describe algorithms which solve such new problem. We study the properties of random codes under this new decoding perspective, in the fashion of traditional coding theory results, and assess the complexity of solving a random R-SDP instance. As a concrete application, we describe how Zero-Knowledge Identification (ZK-ID) schemes based on SDP can be tweaked to rely on R-SDP, and show that this leads to compact public keys as well as significantly reduced communication costs. Thus, these schemes offer an improved basis for the construction of code-based digital signature schemes derived from identification schemes through the well-know Fiat-Shamir transformation.
