Publications de Ziyi Guan | EPFL Graph Search

Publications associées (5)

Security Bounds for Proof-Carrying Data from Straightline Extractors

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 com ...

Springer Science and Business Media Deutschland GmbH2025

On Parallel Repetition of PCPs

Alessandro Chiesa, Ziyi Guan, Burcu Yildiz

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 pr ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2024

Untangling the Security of Kilian’s Protocol: Upper and Lower Bounds

Alessandro Chiesa, Ziyi Guan

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 Schnor ...

Springer Science and Business Media Deutschland GmbH2025

Generalised Linial-Nisan Conjecture Is False for DNFs

Mika Tapani Göös, Gilbert Théodore Maystre, Artur Riazanov, Ziyi Guan, Weiqiang Yuan

Aaronson (STOC 2010) conjectured that almost k-wise independence fools constant-depth circuits; he called this the generalised Linial-Nisan conjecture. Aaronson himself later found a counterexample for depth-3 circuits. We give here an improved counterexam ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2025

Quantum and Classical Communication Complexity of Permutation-Invariant Functions

Ziyi Guan

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-invar ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2024