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/breakoutsessioninteractivezeroknowledge/
https://community.zkproof.org/c/breakoutsessions
LaTeX: https://drive.google.com/drive/u/2/folders/1HWZYMH6Mx8wcX8geium506L0KRxcgPe
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 zeroknowledge protocols, and, upon weighing them, identify settings or applications where interactive protocols may be particularly suitable or relevant.
Some relevant background: Zeroknowledge protocols are often constructed in a twostep process. First, an informationtheoretically 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 informationtheoretically secure protocol is â€ścompiledâ€ť via cryptographic techniques into a zeroknowledge argument, which may or may not be interactive. See Yuval Ishaiâ€™s talk at this workshop for more information on this twostep approach to constructing zeroknowledge protocols.
Below is a list of advantages (or nondisadvantages) discussed:
 Efficiency, Simplicity, and Setup Assumptions: Interactive protocols can often be simpler than noninteractive 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 PCPbased arguments do.).
Yet, if an interactive protocol is public coin, it can be rendered noninteractive in most settings via the FiatShamir 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 noninteractive via FiatShamir.
A concrete example of how interactive protocols can be simpler and accordingly more efficient than noninteractive 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 linearPCP (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 FiatShamir heuristic is not known to be able to render a publiccoin protocol totally noninteractive (see, e.g., https://eprint.iacr.org/2019/188)

Interactive protocols can be based on weaker cryptographic assumptions than noninteractive ones (e.g., interactive proofs are informationtheoretically 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., realworld 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 nontransferrable/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).

Zeroknowledge 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 zeroknowledge protocol is noninteractive.
Below is a list of disadvantages discussed:

Currently, the zeroknowledge protocols with the shortest known proofs are based on linear PCPs, which are noninteractive. These proofs are just a few group elements. While (publiccoin) zeroknowledge protocols based on interactive proofs or interactive oracle proofs can be rendered noninteractive with the FiatShamir 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 FiatShamir 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 zeroknowledge (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 noninteractivity.

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 zeroknowledge, not soundness, for publiccoin 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 zeroknowledge 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 noninteractive. Luis will look into this.

There was brief discussion about techniques other than FiatShamir 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 








