Paper 2015/910

QA-NIZK Arguments in Asymmetric Groups: New Tools and New Constructions

Alonso González, Alejandro Hevia, and Carla Ràfols

Abstract

A sequence of recent works have constructed constant-size quasi-adaptive (QA) NIZK arguments of membership in linear subspaces of $\mathbb{G}^m$, where $\mathbb{G}$ is a group equipped with a bilinear map $e : G \times H \to T$. Although applicable to any bilinear group, these techniques are less useful in the asymmetric case. For example, Jutla and Roy (Crypto 2014) show how to do QA aggregation of Groth- Sahai proofs, but the types of equations which can be aggregated are more restricted in the asymmetric setting. Furthermore, there are natural statements which cannot be expressed as membership in linear subspaces, for example the satisfiability of quadratic equations. In this paper we develop specific techniques for asymmetric groups. We introduce a new computational assumption, under which we can recover all the aggregation results of Groth-Sahai proofs known in the symmetric setting. We adapt the arguments of membership in linear spaces of $\mathbb{G}^m$ to linear subspaces of $\mathbb{G}^m \times \mathbb{H}^n$. In particular, we give a constant-size argument that two sets of Groth-Sahai commitments, defined over different groups $\mathbb{G},\mathbb{H}$, open to the same scalars in $\mathbb{Z}_q$, a useful tool to prove satisfiability of quadratic equations in $\mathbb{Z}_q$. We then use one of the arguments for subspaces in $\mathbb{G}^m \times\mathbb{H}^n$ and develop new techniques to give constant-size QA-NIZK proofs that a commitment opens to a bit-string. To the best of our knowledge, these are the first constant-size proofs for quadratic equations in $\mathbb{Z}_q$ under standard and falsifiable assumptions. As a result, we obtain improved threshold Groth-Sahai proofs for pairing product equations, ring signatures, proofs of membership in a list, and various types of signature schemes.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in ASIACRYPT 2015
Keywords
Cryptographic ProtocolsQA-NIZK ArgumentsAsymmetric Groups.
Contact author(s)
alonso gon @ gmail com
History
2016-02-22: revised
2015-09-17: received
See all versions
Short URL
https://ia.cr/2015/910
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/910,
      author = {Alonso González and Alejandro Hevia and Carla Ràfols},
      title = {QA-NIZK Arguments in Asymmetric Groups: New Tools and New Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/910},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/910}},
      url = {https://eprint.iacr.org/2015/910}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.