Abstract | ||
---|---|---|
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 vertical bar C vertical bar.poly(kappa), where vertical bar C vertical bar is the size of the circuit that computes the NP relation. 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 for NP from 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 for NP with short proof size from a DH-type assumption over pairing groups. Here, the proof size has an additive-overhead vertical bar C vertical bar+poly(kappa) rather then an multiplicative-overhead vertical bar C vertical bar.poly(kappa). 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 for NP with 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 vertical bar C vertical bar+poly(kappa). 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. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1007/978-3-030-17656-3_22 | ADVANCES IN CRYPTOLOGY - EUROCRYPT 2019, PT II |
Field | DocType | Volume |
Discrete mathematics,Open problem,Lattice (order),Computer science,Preprocessor,Gas meter prover,Diffie–Hellman key exchange | Journal | 11477 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Shuichi Katsumata | 1 | 8 | 7.88 |
Ryo Nishimaki | 2 | 131 | 14.91 |
Shota Yamada | 3 | 94 | 18.10 |
Takashi Yamakawa | 4 | 12 | 9.35 |