On Succinct Arguments and Witness Encryption from Groups
On Succinct Arguments and Witness Encryption from Groups
复制标题
关于简洁论证和群体见证加密
DOI：
10.1007/978-3-030-56784-2_26
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Wu, D.J.
中科院分区：
文献类型：
--
作者：
Barta, O.;Ishai, Y.;Ostrovsky, R.;Wu, D.J.
简洁的非交互式参数（SNARG）使证明的声明与非常低的沟通。最近，在理论和实践上都有大量的工作在用非常短的证明来构造SNARG。目前，简洁性方面的最新技术是由Groth（Eurocrypt 2016）从双线性映射中构建的SNARG，其中证明仅由3个群元素组成。在这项工作中，我们首先构建了一个具有逆多项式可靠性的具体有效的指定验证者（预处理）SNARG，其中证明仅由标准（通用）群中的2个群元素组成。这导致了50%的减少，在具体的证明大小相比，格罗斯的建设。我们遵循Bitansky等人的方法。(TCC 2013）描述了一个从线性PCP到预处理模型中的SNARG的编译器。我们的改进是基于一个新的线性PCP packingtechnique，使我们能够构建1-查询线性PCP，然后可以编译成一个SNARG（使用ElGamal加密的通用组）。我们的新SNARG的一个吸引人的特点是，验证者可以预先计算一个statement-independentlookup表在离线阶段，验证证明，然后只需要2个指数和一个单一的表查找。这使得我们新的指定验证者SNARG在需要快速验证和最小通信的设置中具有吸引力。然后，我们转向证明由一个单群元素组成的构造参数的问题。在这里，我们首先表明，任何（可能是交互式的）参数的语言，其中验证算法是“通用的”（即，仅执行一般的组操作），并且证明由单个组元素组成，这意味着对的见证验证方案。然后，我们表明，根据一个尚未证实的，但高度合理的，假设的硬度近似的最小距离的线性代码，我们可以构建一个2-消息简洁的论点，证明由一个单一的组元素。在同样的假设下，我们在一般群模型下得到了一个证人加密方案.沿着的方式，我们表明，在一个概念上相似的，但provenhardness近似结果，有一个2-消息简洁的论点与可忽略不计的合理性错误，证明者的消息组成的只是2组元素。在这两种情况下，我们得到简洁的参数（和线性PCP）与lineardecision程序。我们的建设规避了以前的下限Groth对这样的论点系统的线性决策程序依赖onimperfect完整性。也就是说，我们的构造具有消失但不可忽略的完整性误差，而Groth的下界隐含地假设基本论点的完整性误差可以忽略。因此，我们的技术突出了新的途径，设计线性PCP，简洁的参数，证人加密方案。
Succinct non-interactive arguments (SNARGs) enable proofs ofstatements with very low communication. Recently, there has been significant work in both theory and practice on constructing SNARGs with very short proofs. Currently, the state-of-the-art in succinctness is due to Groth (Eurocrypt 2016) who constructed a SNARG frombilinearmaps where the proof consists of just 3 group elements.In this work, we first construct a concretely-efficient designated-verifier (preprocessing) SNARG with inverse polynomial soundness, where the proof consists of just 2 group elements in astandard(generic) group. This leads to a 50% reduction in concrete proof size compared to Groth’s construction. We follow the approach of Bitansky et al. (TCC 2013) who describe a compiler from linear PCPs to SNARGs in the preprocessing model. Our improvement is based on a newlinear PCP packingtechnique that allows us to construct 1-query linear PCPs which can then be compiled into a SNARG (using ElGamal encryption over a generic group). An appealing feature of our new SNARG is that the verifier can precompute astatement-independentlookup table in an offline phase; verifying proofs then only requires 2 exponentiations and a single table lookup. This makes our new designated-verifier SNARG appealing in settings that demand fast verification and minimal communication.We then turn to the question of constructing arguments where the proof consists of asinglegroup element. Here, we first show that any (possibly interactive) argument for a languagewhere the verification algorithm is “generic” (i.e., only performs generic group operations) and the proof consists of a single group element, implies awitness encryptionscheme for. We then show that under a yet-unproven, but highly plausible, hypothesis on the hardness of approximating the minimal distance of linear codes, we can construct a 2-message laconic argument forwhere the proof consists of a single group element. Under the same hypothesis, we obtain a witness encryption scheme forin the generic group model. Along the way, we show that under a conceptually-similar butprovenhardness of approximation result, there is a 2-message laconic argument forwith negligible soundness error where the prover’s message consists of just 2 group elements. In both settings, we obtain laconic arguments (and linear PCPs) withlineardecision procedures. Our constructions circumvent a previous lower bound by Groth on such argument systems with linear decision procedures by relying onimperfect completeness. Namely, our constructions have vanishing but not negligible completeness error, while the lower bound of Groth implicitly assumes negligible completeness error of the underlying argument. Our techniques thus highlight new avenues for designing linear PCPs, succinct arguments, and witness encryption schemes.
登录
查看更多内容
关于轮有效论证系统
DOI：
10.1007/11523468_12
发表时间：
2005
期刊：
The Southeast Asian journal of tropical medicine and public health
影响因子：
--
作者：
H. Wee
通讯作者：
H. Wee
DOI：
10.1145/3406325.3451070
发表时间：
2021-06
期刊：
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Romain Gay;R. Pass
通讯作者：
Romain Gay;R. Pass
多证明者交互式证明的简洁论证及其效率优势
影响因子：
3
作者：
Nir Bitansky;A. Chiesa
通讯作者：
A. Chiesa
基于格的 SNARG 及其在更有效的混淆中的应用
DOI：
--
发表时间：
2017
期刊：
International Conference on the Theory and Application of Cryptographic Techniques
影响因子：
--
作者：
D. Boneh;Yuval Ishai;A. Sahai;David J. Wu
通讯作者：
David J. Wu
DOI：
10.4230/lipics.icalp.2022.28
发表时间：
2020
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Zvika Brakerski;Nico Döttling;Sanjam Garg;Giulio Malavolta
通讯作者：
Zvika Brakerski;Nico Döttling;Sanjam Garg;Giulio Malavolta