Paper 2019/173

Shorter Quadratic QA-NIZK Proofs

Vanesa Daza, Alonso González, Zaira Pindado, Carla Ràfols, and Javier Silva

Abstract

Despite recent advances in the area of pairing-friendly Non-Interactive Zero-Knowledge proofs, there have not been many efficiency improvements in constructing arguments of satisfiability of quadratic (and larger degree) equations since the publication of the Groth-Sahai proof system (JoC'12). In this work, we address the problem of aggregating such proofs using techniques derived from the interactive setting and recent constructions of SNARKs. For certain types of quadratic equations, this problem was investigated before by González et al. (ASIACRYPT'15). Compared to their result, we reduce the proof size by approximately 50% and the common reference string from quadratic to linear, at the price of using less standard computational assumptions. A theoretical motivation for our work is to investigate how efficient NIZK proofs based on falsifiable assumptions can be. On the practical side, quadratic equations appear naturally in several cryptographic schemes like shuffle and range arguments.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
zero knowledgeelliptic curve cryptosystem
Contact author(s)
carla rafols @ upf edu
zaira pindado @ upf edu
History
2019-03-29: revised
2019-02-26: received
See all versions
Short URL
https://ia.cr/2019/173
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/173,
      author = {Vanesa Daza and Alonso González and Zaira Pindado and Carla Ràfols and Javier Silva},
      title = {Shorter Quadratic QA-NIZK Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2019/173},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/173}},
      url = {https://eprint.iacr.org/2019/173}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.