Zero-knowledge proofs on secret-shared data via fully linear PCPs
We introduce and study the notion of fully linear probabilistically checkable proof systems. In
such a proof system, the verifier can make a small number of linear queries that apply jointly …
such a proof system, the verifier can make a small number of linear queries that apply jointly …
Local certification of graph decompositions and applications to minor-free classes
Local certification consists in assigning labels to the vertices of a network to certify that some
given property is satisfied, in such a way that the labels can be checked locally. In the last …
given property is satisfied, in such a way that the labels can be checked locally. In the last …
Distributed zero-knowledge proofs over networks
Zero knowledge proofs are one of the most influential concepts in theoretical computer
science. In the seminal definition due to Goldwasser, Micali and Rackoff dating back to the …
science. In the seminal definition due to Goldwasser, Micali and Rackoff dating back to the …
Compact distributed certification of planar graphs
Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a
distributed interactive proof for planarity (ie, for certifying that a network is planar), using a …
distributed interactive proof for planarity (ie, for certifying that a network is planar), using a …
Local certification of graphs on surfaces
L Esperet, B Lévêque - Theoretical Computer Science, 2022 - Elsevier
A proof labelling scheme for a graph class C is an assignment of certificates to the vertices of
any graph in the class C, such that upon reading its certificate and the certificates of its …
any graph in the class C, such that upon reading its certificate and the certificates of its …
Distributed certification for classes of dense graphs
A proof-labeling scheme (PLS) for a boolean predicate $\Pi $ on labeled graphs is a
mechanism used for certifying the legality with respect to $\Pi $ of global network states in a …
mechanism used for certifying the legality with respect to $\Pi $ of global network states in a …
Trade-offs in distributed interactive proofs
The study of interactive proofs in the context of distributed network computing is a novel
topic, recently introduced by Kol, Oshman, and Saxena [PODC 2018]. In the spirit of …
topic, recently introduced by Kol, Oshman, and Saxena [PODC 2018]. In the spirit of …
Local certification of graphs with bounded genus
Abstract Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for
automatically translating standard centralized interactive protocols to distributed interactive …
automatically translating standard centralized interactive protocols to distributed interactive …
Introduction to local certification
L Feuilloley - Discrete Mathematics & Theoretical Computer …, 2021 - dmtcs.episciences.org
A distributed graph algorithm is basically an algorithm where every node of a graph can look
at its neighborhood at some distance in the graph and chose its output. As distributed …
at its neighborhood at some distance in the graph and chose its output. As distributed …
Distributed-prover interactive proofs
Interactive proof systems enable a verifier with limited resources to decide an intractable
language (or compute a hard function) by communicating with a powerful but untrusted …
language (or compute a hard function) by communicating with a powerful but untrusted …