Paper 2020/1433
Interactive Proofs for Social Graphs
Liran Katzir, Clara Shikhelman, and Eylon Yogev
Abstract
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 doublyefficient publiccoin twomessage 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 quasilinear 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 FiatShamir paradigm, we are able to transform the above protocols to a noninteractive 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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 interactive proofssocial graphssuccinct arguments
 Contact author(s)
 eylony @ gmail com
 History
 20201115: received
 Short URL
 https://ia.cr/2020/1433
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1433, 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{https://eprint.iacr.org/2020/1433}}, url = {https://eprint.iacr.org/2020/1433} }