International Association for Cryptologic Research

International Association
for Cryptologic Research


Fine-grained Verifier NIZK and Its Applications

Xiangyu Liu , Shanghai Jiao Tong University
Shengli Liu , Shanghai Jiao Tong University
Shuai Han , Shanghai Jiao Tong University
Dawu Gu , Shanghai Jiao Tong University
DOI: 10.1007/978-3-031-31371-4_17
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
Abstract: In this paper, we propose a new type of non-interactive zero-knowledge (NIZK), called Fine-grained Verifier NIZK (FV-NIZK), which provides more flexible and more fine-grained verifiability of proofs than standard NIZK that supports public verifiability and designated-verifier NIZK (DV-NIZK) that supports private verifiability. FV-NIZK has two statistically equivalent verification approaches: -- a master verification using the master secret key msk; -- a fine-grained verification using a derived secret key sk_d, which is derived from msk w.r.t. d (which may stand for user identity, email address, vector, etc.). We require unbounded simulation soundness (USS) of FV-NIZK to hold, even if an adversary obtains derived secret keys sk_d with d of its choices, and define proof pseudorandomness which stipulates the pseudorandomness of proofs for adversaries that are not given any secret key. We present two instantiations of FV-NIZK for linear subspace languages, based on the matrix decisional Diffie-Hellman (MDDH) assumption. One of the FV-NIZK instantiations is pairing-free and achieves almost tight USS and proof pseudorandomness. We illustrate the usefulness of FV-NIZK by showing two applications and obtain the following pairing-free schemes: -- the first almost tightly multi-challenge CCA (mCCA)-secure inner-product functional encryption (IPFE) scheme without pairings; -- the first public-key encryption (PKE) scheme that reconciles the inherent contradictions between public verifiability and anonymity. We formalize such PKE as Fine-grained Verifiable PKE (FV-PKE), which derives a special key from the decryption secret key, such that for those who obtain the derived key, they can check the validity of ciphertexts but the anonymity is lost from their views (CCA-security still holds for them), while for others who do not get the derived key, they cannot do the validity check but the anonymity holds for them. Our FV-PKE scheme achieves almost tight mCCA-security for adversaries who obtain the derived keys, and achieves almost tight ciphertext pseudorandomness (thus anonymity) for others who do not get any derived key.
  title={Fine-grained Verifier NIZK and Its Applications},
  author={Xiangyu Liu and Shengli Liu and Shuai Han and Dawu Gu},