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
#5

The notes from the breakout session on Interactive Zero Knowledge have been edited. They can be found in docx and pdf format at the following links (.docx, .pdf). Below is also the text of the notes, though some formatting has been lost.

2nd ZKProof Workshop Notes

Interactive Zero Knowledge

https://community.zkproof.org/t/breakout-session-interactive-zero-knowledge/

https://community.zkproof.org/c/breakout-sessions

LaTeX: https://drive.google.com/drive/u/2/folders/1HWZYMH-6Mx8wcX8geium506L0KRxcgPe

Moderators: Yael Kalai and Justin Thaler

Scribes: Sean Coughlin

Notes Delivery Owner (post notes by April 19th):

Participants (as sign up sheet) - https://docs.google.com/spreadsheets/d/1bVx3sekpR23wMigGTBuUa0s73LaNk5JI4UZPk2ru61A/edit?usp=sharing

General Notes

The goal of the session was to identify advantages and disadvantages of interactive zero-knowledge protocols, and, upon weighing them, identify settings or applications where interactive protocols may be particularly suitable or relevant.

Some relevant background: Zero-knowledge protocols are often constructed in a two-step process. First, an information-theoretically secure protocol is constructed (e.g., an interactive proof, an interactive oracle proof, a PCP, a linear PCP, etc. As their names suggest, interactive proofs and interactive oracle proofs are interactive, while PCPs and linear PCPs are not). Second, the information-theoretically secure protocol is “compiled” via cryptographic techniques into a zero-knowledge argument, which may or may not be interactive. See Yuval Ishai’s talk at this workshop for more information on this two-step approach to constructing zero-knowledge protocols.

Below is a list of advantages (or non-disadvantages) discussed:

  • Efficiency, Simplicity, and Setup Assumptions: Interactive protocols can often be simpler than non-interactive ones, and may be more efficient as a result. They also may rely on simpler or weaker trusted setup assumptions (i.e., they typically do not require a structured reference string (SRS), the way many linear PCP-based arguments do.).
    Yet, if an interactive protocol is public coin, it can be rendered non-interactive in most settings via the Fiat-Shamir heuristic (secure in the Random Oracle Model), often with little loss in efficiency. This means that protocol designers have the freedom to leverage interactivity as a “resource” to simplify protocol design, improve efficiency, or weaken or remove trusted setup, and still have the option of rendering the protocol non-interactive via Fiat-Shamir.

A concrete example of how interactive protocols can be simpler and accordingly more efficient than non-interactive variants: researchers attempted to render PCPs practical (e.g., BCGT, STOC 2013), but the resulting PCPs were still complicated, and fell short of practicality. More recent work (SCI, STARKs, Aurora, etc.) turned to interactive oracle proofs rather than PCPs, leveraging interaction to achieve simpler and more efficient protocols.

Space efficiency of the prover was also discussed. PCP- and linear-PCP (and even interactive oracle proof based arguments) often have large space requirements and require the prover to perform FFTs on big vectors (see efforts in the DIZK work that Howard talked about to distribute the prover due to these issues). Interactive proof based protocols currently seem more space efficient (e.g., GKR protocol works one circuit layer at a time, no FFTs), easier to distribute.

Note: in some specialized settings, the Fiat-Shamir heuristic is not known to be able to render a public-coin protocol totally non-interactive (see, e.g., https://eprint.iacr.org/2019/188)

  • Interactive protocols can be based on weaker cryptographic assumptions than non-interactive ones (e.g., interactive proofs are information-theoretically secure, interactive oracle proofs can be compiled into interactive arguments based only on string commitments). In comparison, zkSNARKs are often based on knowledge assumptions.

  • Many applications are inherently interactive (e.g., real-world networking protocols involve multiple messages just to initiate a connection). If an application is inherently interactive, why not leverage interaction as a resource to make a protocol simpler, more efficient, remove trusted setup, or use weaker crypto assumptions?

  • Interactive protocols can potentially be run with fewer bits of security and hence be more efficient (adversaries may only have one try to break things in an interactive setting). Can also impose a time limit for the protocol to terminate, limiting the runtime of attackers, and thereby get away with fewer bits of security.

  • Interactive protocols may be non-transferrable/deniable: the verifier cannot turn around and convince someone else of the validity of the statement. This can be essential in many applications. However, subtleties may arise if messages are signed by the prover (having the prover sign messages of an interactive protocol can make it transferrable).

  • Zero-knowledge protocols are often combined with other cryptographic primitives in applications (e.g., oblivious transfer). If the other primitives are interactive, then the final cryptographic protocol will be interactive regardless of whether the zero-knowledge protocol is non-interactive.

Below is a list of disadvantages discussed:

  • Currently, the zero-knowledge protocols with the shortest known proofs are based on linear PCPs, which are non-interactive. These proofs are just a few group elements. While (public-coin) zero-knowledge protocols based on interactive proofs or interactive oracle proofs can be rendered non-interactive with the Fiat-Shamir heuristic, they currently produce longer proofs (log or polylog field elements). The longer proofs may render these protocols unsuitable for some applications (e.g., public blockchain), but they may still be suitable for other applications (even related ones, like enterprise blockchain applications).

  • Applying the Fiat-Shamir heuristic to an interactive protocol may increase soundness error.

  • Network latency can make interactive protocols slow.

  • Interactive protocols must occur online, i.e., the proof cannot simply be published or posted and checked later at the verifier’s convenience.

  • Also discussed was whether interactive protocols are more vulnerable to concurrency attacks on zero-knowledge (i.e., multiple malicious verifiers may interactive with a single prover and coordinate and interleave their messages to try to learn information from the prover).

  • Many applications require non-interactivity.

  • Because interactive protocols require the prover to send multiple messages, there may be more vulnerability to side channel or timing attacks (timing attacks will only affect zero-knowledge, not soundness, for public-coin protocols, since the verifier’s messages are just random coins and timing attacks shouldn’t leak information to the prover in this case. In private coin protocols, both zero-knowledge and soundness may be affected by these attacks).

Other topics that came up:

  • Luis raised a possible error in the documents produced from the last workshop, regarding whether in public verifiable case, schemes where proofs are transferrable must be non-interactive. Luis will look into this.

  • There was brief discussion about techniques other than Fiat-Shamir to remove interaction. Some exist but are not necessarily practical (e.g., Kalai, Paneth, Yang 2019).

  • Verifiable Delay Functions

Suggested Contributions

Name Email Specific Contribution / Action Point
Ivan Visconti Deniability
LuĂ­s T. A. N. BrandĂŁo Statistical Security
Yupeng Zhang Efficiency and trusted setup
Yael and Justin Intro
1 Like
#6

These are great notes! Thank you @Sean and @justin, it seems to me that the notes can (with minor editing and formatting) be included in the Reference Document as they are.

Two things I would like to add:

  • I volunteered as well to help with the contributions, specifically about applications of interactive ZK. As we mentioned, there are use-cases where non-transferability of proofs is needed (see this quote):