Security Seminar: Public-Coin Time- and Space-Efficient Arguments, Justin Holmgren

Security Seminar

Title: Public-Coin Time- and Space-Efficient Arguments
Speaker: Justin Holmgren
Date: October 19
Time: 1:30pm
Event link:

 We construct public-coin time- and space-efficient zero-knowledge
 arguments for NP where, for any time-T, space-S non-deterministic RAM
 computation, the prover runs in time T * polylog(T) and space S *
 polylog(T), and the verifier runs in time n * polylog(T), where n is the
 input length of the computation.  Our protocol relies on groups whose
 order is not efficiently computable, which: 
     can be instantiated with a trusted setup from the hardness of
     factoring products of safe primes, can be instantiated without a
     trusted setup, using class groups. 
 Our 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 recently
 proposed 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.
 Non-trivially modify the DARK scheme to overcome the aforementioned gap.
 The modified version relies on 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 (PoE) protocol to work with general
 groups of unknown order (without relying on any cryptographic
 In proving these results, we develop general-purpose techniques for
 working with (hidden order) groups, which may be of independent
 Based on joint work with Alexander Block, Alon Rosen, Ron Rothblum, and Pratik Soni.

Tuesday, October 19, 2021 - 1:30pm to 2:30pm