Acyclicity Programming for Sigma-Protocols

Masayuki Abe; Miguel Ambrona; Andrej Bogdanov; Miyako Ohkubo; Alon Rosen

Paper 2021/135

Acyclicity Programming for Sigma-Protocols

Masayuki Abe, Miguel Ambrona, Andrej Bogdanov, Miyako Ohkubo, and Alon Rosen

Abstract

Cramer, Damgård, and Schoenmakers (CDS) built a proof system to demonstrate the possession of subsets of witnesses for a given collection of statements that belong to a prescribed access structure P by composing so-called sigma-protocols for each atomic statement. Their verifier complexity is linear in the size of the monotone span program representation of P. We propose an alternative method for combining sigma-protocols into a single non-interactive system for a compound statement in the random oracle model. In contrast to CDS, our verifier complexity is linear in the size of the acyclicity program representation of P, a complete model of monotone computation introduced in this work. We show that the acyclicity program size of a predicate is never larger than its de Morgan formula size and it is polynomially incomparable to its monotone span program size. We additionally present an extension of our proof system, with verifier complexity linear in the monotone circuit size of P, in the common reference string model. Finally, considering the types of statement that naturally reduce to acyclicity programming, we discuss several applications of our new methods to protecting privacy in cryptocurrency and social networks.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in TCC 2021
Keywords: sigma-protocols zero-knowledge proofs random oracles
Contact author(s): abe masayuki cp @ hco ntt co jp
miguel ambrona fu @ hco ntt co jp
andrejb @ cse cuhk edu hk
m ohkubo @ nict go jp
alon rosen @ idc ac il
History: 2021-10-06: last of 2 revisions; 2021-02-10: received; See all versions
Short URL: https://ia.cr/2021/135
License: CC BY

BibTeX

@misc{cryptoeprint:2021/135,
      author = {Masayuki Abe and Miguel Ambrona and Andrej Bogdanov and Miyako Ohkubo and Alon Rosen},
      title = {Acyclicity Programming for Sigma-Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2021/135},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/135}},
      url = {https://eprint.iacr.org/2021/135}
}