## CryptoDB

### Paper: Interactive Proofs for Social Graphs

Authors: Eylon Yogev , Tel Aviv University Liran Katzir , Google Research Clara Shikhelman , California Institute of Technology DOI: http://dx.doi.org/10.1007/978-3-030-56877-1_20 (login may be required) Search ePrint Search Google Slides CRYPTO 2020 We consider interactive proofs for social graphs, where the verifier has only oracle access to the graph and can query for the $i^{th}$ neighbor of a vertex $v$, given $i$ and $v$. In this model, we construct a doubly-efficient public-coin two-message interactive protocol for estimating the size of the graph to within a multiplicative factor $\epsilon>0$. The verifier performs $\widetilde{O}(1/\epsilon^2 \cdot \tau \cdot \Delta)$ queries to the graph, where $\tau$ is the mixing time of the graph and $\Delta$ is the average degree of the graph. The prover runs in quasi-linear time in the number of nodes in the graph. Furthermore, we develop a framework for computing the average of essentially any (reasonable) function $f$ of vertices of the graph. Using this framework, we can estimate many health measures of social graphs such as the clustering coefficients and the average degree, where the verifier performs only a small number of queries to the graph. Using the Fiat-Shamir paradigm, we are able to transform the above protocols to a non-interactive argument in the random oracle model. The result is that any social media company (Facebook, Twitter, etc.) can publish, once and for all, a short proof for the size or health of their social network. This proof can be publicly verified by any single user using a small number of queries to the graph.
##### BibTeX
@inproceedings{crypto-2020-30422,
title={Interactive Proofs for Social Graphs},
publisher={Springer-Verlag},
doi={http://dx.doi.org/10.1007/978-3-030-56877-1_20},
author={Eylon Yogev and Liran Katzir and Clara Shikhelman},
year=2020
}