Paper 2020/1433

Interactive Proofs for Social Graphs

Liran Katzir, Clara Shikhelman, and Eylon Yogev


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 $\tilde{O}(1/\epsilon^2 \cdot \tau_{mix} \cdot \Delta)$ queries to the graph, where $\tau_{mix}$ 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 quantiles of essentially any (reasonable) function $f$ of vertices/edges 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 social media companies (e.g., 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.

Available format(s)
Publication info
Preprint. MINOR revision.
interactive proofssocial graphssuccinct arguments
Contact author(s)
eylony @ gmail com
2020-11-15: received
Short URL
Creative Commons Attribution


      author = {Liran Katzir and Clara Shikhelman and Eylon Yogev},
      title = {Interactive Proofs for Social Graphs},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1433},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.