Compact Ring Signatures from Learning With Errors
Compact Ring Signatures from Learning With Errors
复制标题
DOI：
10.1007/978-3-030-84242-0_11
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Rohit Chatterjee;Sanjam Garg;Mohammad Hajiabadi;Dakshita Khurana;Xiao Liang;Giulio Malavolta;Omkant Pandey;Sina Shiehian
中科院分区：
文献类型：
--
作者：
Rohit Chatterjee;Sanjam Garg;Mohammad Hajiabadi;Dakshita Khurana;Xiao Liang;Giulio Malavolta;Omkant Pandey;Sina Shiehian
环签名允许用户代表一组签名者对消息进行签名，同时隐藏签名者的真实身份。由于环签名所保证的匿名性程度与环的大小成正比，密码学中的一个重要目标是研究作为环成员数目的函数来最小化签名大小的构造。在这项工作中，我们从(普通)带错误学习(LWE)问题出发，提出了第一个紧致环签名方案(签名的大小与环的大小成对数增长)。构造是在标准模型中进行的，并且它不依赖于普通的随机字符串或随机先知启发式。与Backeset等人[Eurocrypt‘2019]的工作不同，我们的方案不依赖于双线性对，这使得我们可以证明在假设LWE的量子硬度的情况下，该方案是后量子安全的。我们方案的核心是关于NPcoNP的紧凑且统计见证不可区分的ZAP证明的新构造，我们基于简单的LWE假设证明了该证明是可靠的。在我们的工作之前，已知的统计Zap(对于所有NP)只假设LWE是亚指数的。我们相信，这一方案在未来可能会有更多的应用。
Ring signatures allow a user to sign a message on behalf of a “ring” of signers, while hiding the true identity of the signer. As the degree of anonymity guaranteed by a ring signature is directly proportional to the size of the ring, an important goal in cryptography is to study constructions that minimize the size of the signature as a function of the number of ring members.In this work, we present the first compact ring signature scheme (i.e., where the size of the signature grows logarithmically with the size of the ring) from the (plain) learning with errors (LWE) problem. The construction is in the standard model and it does not rely on a common random string or on the random oracle heuristic. In contrast with the prior work of Backeset al.[EUROCRYPT’2019], our scheme does not rely on bilinear pairings, which allows us to show that the scheme is post-quantum secure assuming the quantum hardness of LWE.At the heart of our scheme is a new construction of compact and statistically witness indistinguishable ZAP arguments for NPcoNP, that we show to be sound based on the plain LWE assumption. Prior to our work, statistical ZAPs (for all of NP) were known to exist only assumingsub-exponentialLWE. We believe that this scheme might find further applications in the future.