Designated Verifier/Prover and Preprocessing NIZKs from Diffie-Hellman Assumptions
Designated Verifier/Prover and Preprocessing NIZKs from Diffie-Hellman Assumptions
复制标题
DOI：
10.1007/978-3-030-17656-3_22
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Shuichi Katsumata;R. Nishimaki;Shota Yamada;Takashi Yamakawa
中科院分区：
文献类型：
--
作者：
Shuichi Katsumata;R. Nishimaki;Shota Yamada;Takashi Yamakawa
在非交互零知识(NIZK)证明中，证明者可以非交互地说服验证者相信陈述，而无需透露任何额外信息。到目前为止，在公共参考串模型(CRS-NIZK)中已经从各种假设中提供了许多NIZK的构造，然而如何利用无配对群或格等工具来构造NIZK仍然是一个长期悬而未决的问题。最近，Kim和Wu(Crypto‘18)在这个问题上取得了很大的进展，并在预处理模型(PP-NIZKs)中的一种称为NIZKs的松弛模型中构造了第一个基于格的NIZK。在该模型中，存在一个可信的独立于语句的预处理阶段，在该阶段为证明者和验证者生成秘密信息。根据秘密信息能否公开，PP-NIZK捕获CRS-NIZK、指定验证者NIZK(DV-NIZK)和指定证明者NIZK(DP-NIZK)作为特例。Kim和Wu留下了一个悬而未决的问题，那就是我们是否可以从弱无配对基团假设(如DDH)中构造这样的NIZK。进一步地，基于Diffie-Hellman(DH)型假设的NIZK的所有构造(无论是在无对偶群还是在对偶群上)都要求证明大小具有乘法开销，其中|C|是计算关系的回路的大小。我们的结果总结如下：DV-NIZK是基于CDH假设的自由配对群。这是首次在无配对群上构造这类NIZK，解决了Kim和Wu(密码‘18)提出的公开问题。DP-NIZK在配对群上的DH型假设下证明长度较短。这里，证明大小具有加性开销而不是乘性开销。这是第一次构造这样的NIZK(包括CRS-NIZK)，它不依赖于LWE假设、全同态加密、不可分辨混淆或不可证伪假设。PP-NIZK基于DDH假设在无配对群上具有较短的证明长度。这是第一个从弱的和静态的DH型假设(如DDH)获得短证明大小的PP-NIZK。与上述DP-NIZK类似，证明大小为。这也是对Kim和Wu(Crypto‘18)提出的公开问题的一种解决方案。
In a non-interactive zero-knowledge (NIZK) proof, a prover can non-interactively convince a verifier of a statement without revealing any additional information. Thus far, numerous constructions of NIZKs have been provided in the common reference string (CRS) model (CRS-NIZK) from various assumptions, however, it still remains a long standing open problem to construct them from tools such as pairing-free groups or lattices. Recently, Kim and Wu (CRYPTO’18) made great progress regarding this problem and constructed the first lattice-based NIZK in a relaxed model called NIZKs in the preprocessing model (PP-NIZKs). In this model, there is a trusted statement-independent preprocessing phase where secret information are generated for the prover and verifier. Depending on whether those secret information can be made public, PP-NIZK captures CRS-NIZK, designated-verifier NIZK (DV-NIZK), and designated-prover NIZK (DP-NIZK) as special cases. It was left as an open problem by Kim and Wu whether we can construct such NIZKs from weak paring-free group assumptions such as DDH. As a further matter, all constructions of NIZKs from Diffie-Hellman (DH) type assumptions (regardless of whether it is over a paring-free or paring group) require the proof size to have a multiplicative-overhead, where |C| is the size of the circuit that computes therelation.In this work, we make progress of constructing (DV, DP, PP)-NIZKs with varying flavors from DH-type assumptions. Our results are summarized as follows:DV-NIZKs forfrom the CDH assumption over pairing-free groups. This is the first construction of such NIZKs on pairing-free groups and resolves the open problem posed by Kim and Wu (CRYPTO’18).DP-NIZKs forwith short proof size from a DH-type assumption over pairing groups. Here, the proof size has an additive-overheadrather then an multiplicative-overhead. This is the first construction of such NIZKs (including CRS-NIZKs) that does not rely on the LWE assumption, fully-homomorphic encryption, indistinguishability obfuscation, or non-falsifiable assumptions.PP-NIZK forwith short proof size from the DDH assumption over pairing-free groups. This is the first PP-NIZK that achieves a short proof size from a weak and static DH-type assumption such as DDH. Similarly to the above DP-NIZK, the proof size is. This too serves as a solution to the open problem posed by Kim and Wu (CRYPTO’18).Along the way, we construct two new homomorphic authentication (HomAuth) schemes which may be of independent interest.