Cryptology ePrint Archive: Report 2020/1617

Arguments of Knowledge via hidden order groups

Steve Thakur

Abstract: We study non-interactive arguments of knowledge (AoKs) for commitments in groups of hidden order. We provide protocols whereby a Prover can demonstrate certain properties of and relations between committed sets/multisets, with succinct proofs that are publicly verifiable against the constant-sized commitments. In particular, we provide AoKs for the disjointness of committed sets/multisets in cryptographic accumulators, with a view toward applications to verifiably outsourcing data storage and sharded stateless blockchains.

Recent work ([DGS20]) suggests that the hidden order groups need to be substantially larger in size that previously thought, in order to ensure the desired security level. Thus, in order to keep the communication complexity between the Prover and the the Verifier to a minimum, we have designed the protocols so that the proofs entail a constant number of group elements, independent of the number of the committed sets/multisets rather than just independent of the sizes of these sets/multisets.

If the underlying group of hidden order is an appropriate imaginary quadratic class group or a genus three Jacobian, the argument systems are transparent. Furthermore, since all challenges are public coin, the protocols can be made non-interactive using the Fiat-Shamir heuristic. We build on the techniques from [BBF19] and [Wes18].

Category / Keywords: cryptographic protocols / Arguments of knowledge, accumulators, hidden order groups, succinct, batching, non-interactive, commitments

Date: received 30 Dec 2020, last revised 5 Mar 2021

Contact author: stevethakur01 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210305:072521 (All versions of this report)

Short URL: ia.cr/2020/1617