Welcome to the resource topic for 2020/1433
Title:
Interactive Proofs for Social Graphs
Authors: Liran Katzir, Clara Shikhelman, 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 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.
ePrint: https://eprint.iacr.org/2020/1433
Talk: https://www.youtube.com/watch?v=fkCOhuH1um4
Slides: https://iacr.org/submit/files/slides/2020/crypto/crypto2020/70/slides.pptx
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .