Paper 2020/286

Shorter Non-Interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages

Geoffroy Couteau and Dominik Hartmann

Abstract

We put forth a new framework for building pairing-based non-interactive zero- knowledge (NIZK) arguments for a wide class of algebraic languages, which are an extension of linear languages, containing disjunctions of linear languages and more. Our approach differs from the Groth-Sahai methodology, in that we rely on pairings to compile a $\Sigma$-protocol into a NIZK. Our framework enjoys a number of interesting features: – conceptual simplicity, parameters derive from the $\Sigma$-protocol; – proofs as short as resulting from the Fiat-Shamir heuristic applied to the underlying $\Sigma$-protocol; – fully adaptive soundness and perfect zero-knowledge in the common random string model with a single random group element as CRS; – yields simple and efficient two-round, public coin, publicly-verifiable perfect witness-indistinguishable (WI) arguments (ZAPs) in the plain model. To our knowledge, this is the first construction of two-rounds statistical witness-indistinguishable arguments from pairing assumptions. Our proof system relies on a new (static, falsifiable) assumption over pairing groups which generalizes the standard kernel Diffie-Hellman assumption in a natural way and holds in the generic group model (GGM) and in the algebraic group model (AGM). Replacing Groth-Sahai NIZKs with our new proof system allows to improve several important cryptographic primitives. In particular, we obtain the shortest tightly-secure structure-preserving signature scheme (which are a core component in anonymous credentials), the shortest tightly-secure quasi-adaptive NIZK with unbounded simulation soundness (which in turns implies the shortest tightly-mCCA-secure cryptosystem), and shorter ring signatures.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
zero-knowledge argumentsnon-interactive zero-knowledge argumentssatistical witness-indistinguishabilitypairing-based cryptographytight securitystructure-preserving signatures.
Contact author(s)
couteau @ irif fr
Dominik Hartmann @ rub de
History
2020-03-06: revised
2020-03-06: received
See all versions
Short URL
https://ia.cr/2020/286
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/286,
      author = {Geoffroy Couteau and Dominik Hartmann},
      title = {Shorter Non-Interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages},
      howpublished = {Cryptology ePrint Archive, Paper 2020/286},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/286}},
      url = {https://eprint.iacr.org/2020/286}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.