Paper 2021/358

Time- and Space-Efficient Arguments from Groups of Unknown Order

Alexander R. Block, Justin Holmgren, Alon Rosen, Ron D. Rothblum, and Pratik Soni

Abstract

We construct public-coin time- and space-efficient zero-knowledge arguments for $\mathbf{NP}$. For every time $T$ and space $S$ non-deterministic RAM computation, the prover runs in time $T \cdot \mathrm{polylog}(T)$ and space $S \cdot \mathrm{polylog}(T)$, and the verifier runs in time $n \cdot \mathrm{polylog}(T)$, where $n$ is the input length. Our protocol relies on hidden order groups, which can be instantiated with a trusted setup from the hardness of factoring (products of safe primes), or without a trusted setup using class groups. The argument-system can heuristically be made non-interactive using the Fiat-Shamir transform. Our proof builds on DARK (Bünz et al., Eurocrypt 2020), a recent succinct and efficiently verifiable polynomial commitment scheme. We show how to implement a variant of DARK in a time- and space-efficient way. Along the way we: 1. Identify a significant gap in the proof of security of DARK. 2. Give a non-trivial modification of the DARK scheme that overcomes the aforementioned gap. The modified version also relies on significantly weaker cryptographic assumptions than those in the original DARK scheme. Our proof utilizes ideas from the theory of integer lattices in a novel way. 3. Generalize Pietrzak's (ITCS 2019) proof of exponentiation ($\mathsf{PoE}$) protocol to work with general groups of unknown order (without relying on any cryptographic assumption). In proving these results, we develop general-purpose techniques for working with (hidden order) groups, which may be of independent interest.

Note: Added DOI.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in Crypto 2021
DOI
10.1007/978-3-030-84259-8_5
Keywords
Proofs and ArgumentsSuccinct ArgumentsZero Knowledge
Contact author(s)
block9 @ purdue edu
justin holmgren @ ntt-research com
alon rosen @ idc ac il
rothblum @ cs technion ac il
psoni @ andrew cmu edu
History
2021-09-21: last of 2 revisions
2021-03-18: received
See all versions
Short URL
https://ia.cr/2021/358
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/358,
      author = {Alexander R.  Block and Justin Holmgren and Alon Rosen and Ron D.  Rothblum and Pratik Soni},
      title = {Time- and Space-Efficient Arguments from Groups of Unknown Order},
      howpublished = {Cryptology ePrint Archive, Paper 2021/358},
      year = {2021},
      doi = {10.1007/978-3-030-84259-8_5},
      note = {\url{https://eprint.iacr.org/2021/358}},
      url = {https://eprint.iacr.org/2021/358}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.