ZKProof - The Zero-Knowledge Community Forum

Breakout Session: Interactive Zero Knowledge

#1

During the upcoming 2nd ZKProof standards workshop, there will be a breakout session devoted to Interactive Zero Knowledge.

This breakout session will identify advantages and disadvantages of interactive zero-knowledge proofs relative to non-interactive ones, and attempt to identify scenarios and applications where interactive protocols are particularly suitable or relevant.

This forum serves as a place for people to comment and keep the conversation alive. A partial list of advantages and relevant applications has been compiled, and will be discussed at the breakout session. Participants are encouraged to add to the list before, during, and after the session.

1 Like

#3

I just saw the breakout session schedule - will post here for others’ reference!

1 Like

#4

PDF export of notes

Please let me know if you’d like the raw OneNote file - Sean Coughlin


Moderators: Justin Thaler, Yael Kalai

Scribe: Sean Coughlin

Notes deliverable owner: Sean Coughlin

Participants:

Suggested contributions:

  • Most of the focus has been on non-interactive
  • Surely settings where interactive is valuable
  • Goals: identify advantages and disadvantages of interactive protocols relative to non-interactive
  • Advantages
    • Makes protocols easier to design (more efficient) if interactive
      • GKR’s PCP (non-interactive) requires all possible conditions
      • IOPs allow for interaction, Fiat-Shamir allows for non-interactive
        • Fiat-Shamir requires raised computability, since has security loss
      • Generally, more efficient and not easier to design
    • Space is smaller (Muthu)
      • Can prove layer-by-layer
      • DIZK necessary for huge size parameters
    • If public coin, make non-interactive via Fiat-Shamir
      • Fiat-Shamir is not memory efficient (Muthu): not really
      • Have to have fixed rounds (Ivan )
      • More degrees of freedom so harder
      • Public coins can just be made into non-interactive (Kalai)
      • Fiat-Shamir requires honest verifying (Muthu): perhaps (Kalai, Ivan )
      • Random Oracle (Riad)
    • Have security with rewinding (since can make into protocol)
    • Transferability, plausible deniability (Luis )
    • In literature: in public verifiable case, scheme where proofs are transferrable must be non-interactive: false (Luis )
    • Combining ZK with oblivious transfer
      • Receive of oblivious transfer … only if sender satisfies NP relation (Muthu)
      • Certified oblivious transfer can become interactive
    • Why is there so little interest in applications/cases of interactive? (Kalai)
      • Where need deniable
      • Why should we start with assumption that interactive is OK
        • Gives us freedom and can then go NI (Kalai)
      • Are transparent snarks dependent on interactive? (Ynpeng)
        • Huge advantage of size
      • Removing trusted setup (Ynpeng)
    • If you assume RO then you assume transparent setup…
      • It depends on you assumption
    • Tradeoffs are important
      • In particular setting you can gain efficiency with interactive (Luis )
      • With concurrent cases it would require more steps
      • Depends on if need rewind
      • So transparency, transferability…
    • In setting where communication time is a problem, can do things like CRS (Ivan )
      • CRS isn’t necessary (Muthu)
    • Deniability necessary (Kalai)
      • Want to be able to prove statement but prevent transferability from verifier to others (Luis )
      • VDF can prove either you know statement or next block, so hard to transfer (Muthu)
      • Can prove I know witness or I know you secret key
    • Want interactive design that’s not transferrable but where messages are signed, prover signs own messages, now is transferrable (Luis )
      • Non-cryptographers should know about this
  • Disadvantages
    • Concurrent security concerns
    • Network latency
    • Some applications require interactivity (Kalai)
  • Soundness
    • Statistical security: can convince verifier with certain probability
      • When noninteractive there must be higher probability
    • 40 bits in interactive protocol is good enough
      • There is only 1 try interactively
      • Asynchronous NI must be higher security
    • Soundness is not ZK (Riad)
    • Time to live is only limited by time of protocol
  • Trusted setup or assumptions is not removed but simplified (Ynpeng)
    • RO is lower security
  • Action item: inaccuracy in documents since no discussion of Fiat-Shamir loss of security (Ynpeng)
    • Will get relevant references (Ynpeng)
      • Is inaccurate about hash function/RO
  • Disadvantage
    • Interactive protocols take longer (Kalai)
    • Interactive have more exposure to side-channel and timing attacks (Riad)
      • Verifier can track time of responses (Luis )
      • Public coin can have prover do timing attack
      • Being careful with implementation is not good enough since side-channels keep innovating (Luis )
      • Verifier computation should be the same regardless of the size of the witness (Ivan )
      • Bad programming is a universal solvent; not guaranteed full compliance (Riad)
      • Could use weaker definition of timing attack: for any 2 witnesses the timing must be the same (Muthu)
        • Theoreticians don’t care about constant time (Kalai)
        • Define ideal functionality where timing is t_0 to t_d where clock must reset (Luis )
  • PCP have constant length; public coins need small proof size
    • Difference between public coins and private/enterprise (Daniel )
      • Regulators will demand auditing
      • Easiest private blockchain is database (Kalai)
        • Enterprise is diverse (Daniel )
        • Has different trust model (Muthu)
        • DB not immutable (Riad)
        • Amazon AWS has DB structured like blockchain (black jacket)
          • Removes consensus (Daniel )
    • If there are interactive proofs that have super-constant/linear with short interactive proofs
      • How does this compare with longer proofs since both are possible (Luis )
      • Interactive proofs are always longer (Kalai)
      • With interactive proofs we can’t get as small size as NI (Luis )
      • Why is that? Do interactive version with Fiat-Shamir and use SNARG which is short and no Fiat-Shamir (Kalai)
      • SNARG has RO in circuit (Ynpeng)
      • Not ZK just correctness (Kalai)
      • Why not use random string? (Riad)
      • This is a general principle to shorten proof (Muthu)
      • Need so many ROs for SHA256 (Ynpeng)
      • Use Pedersen since it’s faster (Muthu)
  • Is there another way to remove interactivity other than Fiat-Shamir (Daniel )
    • Yes, but less efficient (Kalai)
    • Can lose soundness but not terrible (Muthu)
    • Public verifiability with pairings (Kalai)
      • Costs efficiency of proving (Ynpeng)
  • Disadvantages
    • Shortest known NI are shorter than interactive
  • Calls for action points
    • Last time didn’t cover interactive at all
    • Need paragraph from each volunteer
    • List advantages/disadvantages
    • Not discuss inaccurate document
    • Daniel: applications
    • Luis: statistical security
    • Ynpeng: efficiency and trusted setup
    • Ivan: deniability
  • Public verifiability of interactive proofs
    • Can use external structures
1 Like