Your Name

Ziyi Guan

I am a fourth-year Ph.D. student at the EPFL theory group, where I am fortunate to be advised by Alessandro Chiesa and Mika Göös. I am interested in Theoretical Computer Science, particularly complexity theory and cryptography.

Email: ziyi.guan@epfl.ch

Google Scholar: Ziyi Guan

Papers

Quantum Rewinding for IOP-Based Succinct Arguments [abstract] [arXiv]

We analyze the post-quantum security of succinct interactive arguments constructed from interactive oracle proofs (IOPs) and vector commitment schemes. We prove that an interactive variant of the BCS transformation is secure in the standard model against quantum adversaries when the vector commitment scheme is collapsing.

Our proof builds on and extends prior work on the post-quantum security of Kilian's succinct interactive argument, which is instead based on probabilistically checkable proofs (PCPs). We introduce a new quantum rewinding strategy that works across any number of rounds.

As a consequence of our results, we obtain standard-model post-quantum secure succinct arguments with the best asymptotic complexity known.

Untangling the Security of Kilian’s Protocol: Upper and Lower Bounds [abstract] [ePrint]
TCC 2024 (22nd Theory of Cryptography Conference)

Sigma protocols are elegant cryptographic proofs that have become a cornerstone of modern cryptography. A notable example is Schnorr's protocol, a zero-knowledge proof-of-knowledge of a discrete logarithm. Despite extensive research, the security of Schnorr's protocol in the standard model is not fully understood.

In this paper we study Kilian's protocol, an influential public-coin interactive protocol that, while not a sigma protocol, shares striking similarities with sigma protocols. The first example of a succinct argument, Kilian's protocol is proved secure via rewinding, the same idea used to prove sigma protocols secure. In this paper we show how, similar to Schnorr's protocol, a precise understanding of the security of Kilian's protocol remains elusive. We contribute new insights via upper bounds and lower bounds.

  • Upper bounds.

    We establish the tightest known bounds on the security of Kilian's protocol in the standard model, via strict-time reductions and via expected-time reductions. Prior analyses are strict-time reductions that incur large overheads or assume restrictive properties of the PCP underlying Kilian's protocol.

  • Lower bounds.

    We prove that significantly improving on the bounds that we establish for Kilian's protocol would imply improving the security analysis of Schnorr's protocol beyond the current state-of-the-art (an open problem). This partly explains the difficulties in obtaining tight bounds for Kilian's protocol.

Breaking Verifiable Delay Functions in the Random Oracle Model [abstract] [ePrint]

This work resolves the open problem of whether verifiable delay functions (VDFs) can be constructed in the random oracle model. A VDF is a cryptographic primitive that requires a long time to compute (even with parallelization), but produces a unique output that is efficiently and publicly verifiable.

We prove that VDFs with imperfect completeness and computational uniqueness do not exist in the random oracle model. This also rules out black-box constructions of VDFs from other cryptographic primitives, such as one-way permutations and collision-resistant hash functions.

Prior to our work, Mahmoody, Smith and Wu (ICALP 2020) prove that VDFs satisfying both perfect completeness and perfect uniqueness do not exist in the random oracle model; on the other hand, Ephraim, Freitag, Komargodski, and Pass (Eurocrypt 2020) construct VDFs with perfect completeness and computational uniqueness in the random oracle model assuming the hardness of repeated squaring. Our result is optimal -- we bridge the current gap between previously known impossibility results and existing constructions.

Relativized Succinct Arguments in the ROM Do Not Exist [abstract] [ePrint]

A relativized succinct argument in the random oracle model (ROM) is a succinct argument in the ROM that can prove/verify the correctness of computations that involve queries to the random oracle. We prove that relativized succinct arguments in the ROM do not exist. The impossibility holds even if the succinct argument is interactive, and even if soundness is computational (rather than statistical).

This impossibility puts on a formal footing the commonly-held belief that succinct arguments require non-relativizing techniques. Moreover, our results stand in sharp contrast with other oracle models, for which a recent line of work has constructed relativized succinct non-interactive arguments (SNARGs). Indeed, relativized SNARGs are a powerful primitive that, e.g., can be used to obtain constructions of IVC (incrementally-verifiable computation) and PCD (proof-carrying data) based on falsifiable cryptographic assumptions. Our results rule out this approach for IVC and PCD in the ROM.

Quantum and Classical Communication Complexity of Permutation-Invariant Functions [abstract] [arXiv]
STACS 2024 (41st International Symposium on Theoretical Aspects of Computer Science)

This paper gives a nearly tight characterization of the quantum communication complexity of the permutation-invariant Boolean functions. With such a characterization, we show that the quantum and randomized communication complexity of the permutation-invariant Boolean functions are quadratically equivalent (up to a logarithmic factor). Our results extend a recent line of research regarding query complexity to communication complexity, showing symmetry prevents exponential quantum speedups.

Furthermore, we show the Log-rank Conjecture holds for any non-trivial total permutation-invariant Boolean function. Moreover, we establish a relationship between the quantum/classical communication complexity and the approximate rank of permutation-invariant Boolean functions. This implies the correctness of the Log-approximate-rank Conjecture for permutation-invariant Boolean functions in both randomized and quantum settings (up to a logarithmic factor).

On the Security of Succinct Interactive Arguments from Vector Commitments [abstract] [ePrint] [slides]

We study the security of a fundamental family of succinct interactive arguments in the standard model, stemming from the works of Kilian (1992) and Ben-Sasson, Chiesa, and Spooner (``BCS'', 2016). These constructions achieve succinctness by combining probabilistic proofs and vector commitments.

Our first result concerns the succinct interactive argument of Kilian, realized with any probabilistically-checkable proof (PCP) and any vector commitment. We establish the tightest known bounds on the security of this protocol. Prior analyses incur large overheads, or assume restrictive properties of the underlying PCP.

Our second result concerns an interactive variant of the BCS succinct non-interactive argument, which here we call IBCS, realized with any public-coin interactive oracle proof (IOP) and any vector commitment. We establish the first security bounds for the IBCS protocol. Prior works rely upon this protocol without proving its security; our result closes this gap.

Finally, we study the capabilities and limitations of succinct arguments based on vector commitments. We show that a generalization of the IBCS protocol, which we call the Finale protocol, is secure when realized with any public-query IOP (a notion that we introduce) that satisfies a natural ``random continuation sampling'' (RCS) property. We also show a partial converse: if the Finale protocol satisfies the RCS property (which in particular implies its security), then so does the underlying public-query IOP.

On Parallel Repetition of PCPs [abstract] [ePrint] [slides]
ITCS 2024 (15th Innovations in Theoretical Computer Science)

Parallel repetition refers to a set of valuable techniques used to reduce soundness error of probabilistic proofs while saving on certain efficiency measures. Parallel repetition has been studied for interactive proofs (IPs) and multi-prover interactive proofs (MIPs). In this paper, we initiate the study of parallel repetition for probabilistically checkable proofs (PCPs).

We show that, perhaps surprisingly, parallel repetition of a PCP can increase soundness error, in fact bringing the soundness error to one as the number of repetitions tends to infinity. This "failure" of parallel repetition is common: we find that it occurs for a wide class of natural PCPs for NP-complete languages. We explain this unexpected phenomenon by providing a characterization result: the parallel repetition of a PCP brings the soundness error to zero if and only if a certain "MIP projection" of the PCP has soundness error strictly less than one. We show that our characterization is tight via a suitable example. Moreover, for those cases where parallel repetition of a PCP does bring the soundness error to zero, the aforementioned connection to MIPs offers preliminary results on the rate of decay of the soundness error.

Finally, we propose a simple variant of parallel repetition, called consistent parallel repetition (CPR), which has the same randomness complexity and query complexity as the plain variant of parallel repetition. We show that CPR brings the soundness error to zero for every PCP (with non-trivial soundness error). In fact, we show that CPR decreases the soundness error at an exponential rate in the repetition parameter.

Security Bounds for Proof-Carrying Data from Straightline Extractors [abstract] [ePrint] [slides]
TCC 2024 (22nd Theory of Cryptography Conference)

Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Real-world deployments of PCD have sparked keen interest within the applied community and industry.

Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. Unfortunately, known security analyses incur expensive blowups, which practitioners have disregarded as the analyses would lead to setting parameters that are prohibitively expensive.

In this work we study the concrete security of recursive composition, with the goal of better understanding how to reasonably set parameters for certain PCD constructions of practical interest. Our main result is that PCD obtained from SNARKs with straightline knowledge soundness has essentially the same security as the underlying SNARK (i.e., recursive composition incurs essentially no security loss).

We describe how straightline knowledge soundness is achieved by SNARKs in several oracle models, which results in a highly efficient security analysis of PCD that makes black-box use of the SNARK's oracle (there is no need to instantiated the oracle to carry out the security reduction).

As a notable application, our work offers an idealized model that provides new, albeit heuristic, insights for the concrete security of recursive STARKs used in blockchain systems. Our work could be viewed as partial evidence justifying the parameter choices for recursive STARKs made by practitioners.

Depth-3 Circuits for Inner-Product [abstract] [ECCC] [slides]
MFCS 2023 (48th International Symposium on Mathematical Foundations of Computer Science)
Information and Computation (invited to special issue on MFCS 2023)

What is the Σ32-circuit complexity (depth 3, bottom-fanin 2) of the 2n-bit inner product function? The complexity is known to be exponential 2αnn for some αn=Ω(1). We show that the limiting constant α≔limsup αn satisfies:

0.847... ≤ α ≤ 0.965...

Determining α is one of the seemingly-simplest open problems about depth-3 circuits. The question was recently raised by Golovnev, Kulikov, and Williams (ITCS 2021) and Frankl, Gryaznov, and Talebanfard (ITCS 2022), who observed that α ∈ [0.5, 1]. To obtain our improved bounds, we analyze a covering LP that captures the Σ32-complexity up to polynomial factors. In particular, our lower bound is proved by constructing a feasible solution to the dual LP.

Linear-Time Probabilistic Proofs with Sublinear Verification for Algebraic Automata Over Every Field [abstract] [ePrint]

Interactive oracle proofs (IOPs) are a generalization of probabilistically checkable proofs that can be used to construct succinct arguments. Improvements in the efficiency of IOPs lead to improvements in the efficiency of succinct arguments. Key efficiency goals include achieving provers that run in linear time and verifiers that run in sublinear time, where the time complexity is with respect to the arithmetic complexity of proved computations over a finite field 𝔽.

We consider the problem of constructing IOPs for any given finite field 𝔽 with a linear-time prover and polylogarithmic query complexity. Several previous works have achieved these efficiency requirements with O(1) soundness error for NP-complete languages. However, constrained by the soundness error of the sumcheck protocol underlying these constructions, the IOPs achieve linear prover time only for instances in fields of size (log n). Prior work (Ron-Zewi and Rothblum, STOC 2022) overcomes this problem, but with linear verification time.

We construct IOPs for the algebraic automata problem over any finite field 𝔽 with a linear-time prover, polylogarithmic query complexity, and sublinear verification complexity. We additionally prove a similar result to Ron-Zewi and Rothblum for the NP-complete language R1CS using different techniques. The IOPs imply succinct arguments for (nondeterministic) arithmetic computations over any finite field with linear-time proving (given black-box access to a linear-time collision-resistant hash function).

Inspired by constructions of reverse-multiplication-friendly embeddings, our IOP constructions embed problem instances over small fields into larger fields and adapt previous IOP constructions to the new instances. The IOP provers are modeled as random access machines and use precomputation techniques to achieve linear prover time. In this way, we avoid having to replace the sumcheck protocol.

Talks

Security Bounds for Proof-Carrying Data from Straightline Extractors [slides]
On the Security of Succinct Interactive Arguments from Vector Commitments [slides]
On Parallel Repetition of PCPs [slides]
Depth-3 Circuits for Inner-Product [slides]

Supervising

Sebastian Simon (Princeton University, Master in Computer Science)
  • 2024.9-,
  • 2024.7-2024.9, Summer @ EPFL
Mathias Marty (EPFL, Master in Computer Science)
  • 2023.11-2024.6, EPFL Master's Thesis
Annalisa Barbara (Bocconi University, Master in Computer Science)
  • 2023.9-2024.6
  • 2023.6-2023.9, Summer @ EPFL
Keming Ouyang (University of Michigan, Ann Arbor, Bachelor in Computer Science)
  • 2023.6-2023.9, Summer @ EPFL
Burcu Yıldız (EPFL, Master in Computer Science)
  • 2024.9-, EPFL Master's Thesis
  • 2023.9-2024.6, EPFL Research Scholar
  • 2023.3-2023.9, Master Semester Project
Nikolaos Efthymiou (EPFL, Master in Computer Science)
  • 2023.1-2023.6, Master Semester Project
Zihan Yu (EPFL, Master in Computer Science)
  • 2024.9-, EPFL Master's Thesis
  • 2023.11-2024.9, Master Optional Semester Project
  • 2022.1-2022.6, Master Semester Project
Andrea Byku (ETH Zurich, Master in Cyber Security)
  • 2022.1-2022.6, Master Semester Project

Teaching

[Spring 2024] Head teaching assistant for Theory of Computation at EPFL
[Fall 2023] Teaching assistant for Foundation of Probabilistic Proofs at EPFL
[Summer 2023] Teaching assistant for Foundations and Frontiers of Probabilistic Proofs at Zurich, Switzerland
[Spring 2023] Teaching assistant for Theory of Computation at EPFL
[Fall 2022] Teaching assistant for Foundation of Probabilistic Proofs at EPFL
[Spring 2022] Teaching assistant for Foundation of Probabilistic Proofs at EPFL
[Fall 2020] Teaching assistant for Great Ideas in Theoretical Computer Science at Carnegie Mellon University
[Spring 2020] Teaching assistant for Continuous Time Finance at Carnegie Mellon University
[Spring 2020] Tutor for Great Ideas in Theoretical Computer Science at Carnegie Mellon University
[Fall 2019] Teaching assistant for Discrete Time Finance at Carnegie Mellon University
[Spring 2019] Teaching assistant for Integration and Approximation at Carnegie Mellon University

Education

École polytechnique fédérale de Lausanne 2021.9 -
  • Ph.D. candidate in Computer Science
Carnegie Mellon University 2017.9 - 2020.12
  • Bachelor of Science in Computer Science with University Honors
  • Bachelor of Science in Mathematical Sciences with University Honors

Employment

Google 2020.6 - 2020.8
  • Software engineering intern at Shanghai, China
Google 2019.5 - 2019.8
  • Engineering practicum at Mountain View, CA, USA