Time- and space-efficient arguments from groups of unknown order (Q2139631): Difference between revisions

This paper constructs public-coin time- and space-efficient zero-knowledge arguments for NP. Every time \(T\) and space $S$ non-deterministic RAM computation, the prover runs in time $T\cdot \text{ polylog}(T)$ and space $S\cdot\text{ polylog}(T)$, and the verifier runs in time $n\cdot\text{ polylog}(T)$ where \(n\) is the input length. This 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. For the entire collection see [Zbl 1486.94003].