nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Interactive Proofs for Social Graphs

verfasst von : Liran Katzir, Clara Shikhelman, Eylon Yogev

Erschienen in: Advances in Cryptology – CRYPTO 2020

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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 \(\varepsilon >0\). The verifier performs \(\widetilde{O}(1/\varepsilon ^2 \cdot \tau _{mix}\cdot \varDelta )\) queries to the graph, where \(\tau _{mix}\) is the mixing time of the graph and \(\varDelta \) 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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Tight Parallel Repetition Theorem for Partially Simulatable Interactive Arguments via Smooth KL-Divergence

Nächstes Kapitel The Measure-and-Reprogram Technique 2.0: Multi-round Fiat-Shamir and More

We are not suggesting that WhatsApp behave untruthfully, but merely that they had the incentive to do so.

Since any \(\varepsilon \) deviation is further divided by the \(v_i\)’s degree.

Addario-Berry, L., T, Lei.: “The mixing time of the Newman-Watts small world”. In

Alvisi, L., Clement, A., Epasto, A., Lattanzi, S., Panconesi, A.: Sok: the evolution of sybil defense via social networks. IEEE (2013)

Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive Oracle proofs. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 31–60. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53644-5_2CrossRef

Barberá, P., Jost, J.T., Nagler, J., Tucker, J.A., Bonneau, R.: Tweeting from left to right: is online political communication more than an echo chamber? Psychol. Sci. 26, 1531–1542 (2015)CrossRef

Bar-Yossef, Z., Gurevich, M.: Random sampling from a search engine’s index. J. ACM 55, 1–74 (2008)MathSciNetCrossRef

Bar-Yossef, Z., Gurevich, M.: Estimating the ImpressionRank of web pages (2009)

Bar-Yossef, Z., Gurevich, M.: Efficient search engine measurements. TWEB 5, 1–48 (2011)CrossRef

Braverman, M.: Polylogarithmic independence fools \(AC^{0}\) circuits. J. ACM 57, 1–10 (2010)MathSciNetCrossRef

Brede, M.: Networks-an introduction. In: Newman, M.E.J. (ed.) 2010 Artificial Life. Oxford University Press (2012)

Broder, A., et al.: Estimating corpus size via queries. In: Association for Computing Machinery (2006)

Canetti, R., Chen, Y., Holmgren, J., Lombardi, A., Rothblum, G.N., Rothblum, R.D.: Fiat-Shamir from simpler assumptions. IACR Cryptology ePrint Archive (2018)

Canetti, R., Chen, Y., Reyzin, L., Rothblum, R.D.: Fiat-Shamir and correlation intractability from strong KDM-secure encryption. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 91–122. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_4CrossRef

Chiericetti, F., Dasgupta, A., Kumar, R., Lattanzi, S., Sarlós, T.: On sampling nodes in a network (2016)

Ching, A., Edunov, S., Kabiljo, M., Logothetis, D., Muthukrishnan, S.: One trillion edges: graph processing at Facebook-scale. PVLDB 8, 1804–1815 (2015)

Chierichetti, F., Haddadan, S.: On the complexity of sampling vertices uniformly from a graph (2018)

da F Costa, L., Rodrigues, F.A., Travieso, G., Boas, P.R.V.: Characterization of complex networks: a survey of measurements. Adv. Phys. 56, 167–242 (2006)

Canetti, R., et al.: Fiat-Shamir: from practice to theory (2019)

Dasgupta, A., Kumar, R., Sarlós, T.: On estimating the average degree. ACM (2014)

Ersahin, B., Aktas, Ö., Kilinç, D., Akyol, C.: Twitter fake account detection. IEEE (2017)

Easley, D.A., Kleinberg, J.M.: Networks, Crowds, and Markets - Reasoning About a Highly Connected World. Cambridge University Press, Cambridge (2010)CrossRef

Ergün, F., Kumar, R., Rubinfeld, R.: Fast approximate probabilistically checkable proofs. Inf. Comput. 189, 135–159 (2004)MathSciNetCrossRef

Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12CrossRef

Fortnow, L.: The complexity of perfect zero-knowledge. In: STOC 1987 (1987)

Garimella, K., De Francisci Morales, G., Gionis, A., Mathioudakis, M.: Political discourse on social media: echo chambers, gatekeepers, and the price of bipartisanship (2018)

Gjoka, M., Kurant, M., Butts, C.T., Markopoulou, A.: Walking in Facebook: a case study of unbiased sampling of OSNs. In: Proceedings of IEEE INFOCOM 2010 (2010)

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 186–208 (1989)MathSciNetCrossRef

Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: Advances in Computing Research (1989)

Håstad, J., Pass, R., Wikström, D., Pietrzak, K.: An efficient parallel repetition theorem. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 1–18. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11799-2_1CrossRef

Hardiman, S.J., Richmond, P., Hutzler, S.: Calculating statistics of complex networks through random walks with an application to the on-line social network Bebo. Eur. Phys. J. B 71, 611 (2009)CrossRef

Harsha, P., Srinivasan, S.: On polynomial approximations to AC. Random Struct. Algorithms 54, 289–303 (2019)MathSciNetCrossRef

Kurant, M., Butts, C.T., Markopoulou, A.: Graph size estimation. CoRR (2012)

Katzir, L., Hardiman, S.J.: Estimating clustering coefficients and size of social networks via random walk. ACM Trans. Web 9, 1–20 (2015)CrossRef

Katzir, L., Liberty, E., Somekh, O., Cosma, I.A.: Estimating sizes of social networks via biased sampling. Internet Math. 10, 335–359 (2014)MathSciNetCrossRef

Kanade, V., Mallmann-Trenn, F., Verdugo, V. How large is your graph? (2017)

Kalai, Y.T., Rothblum, G.N., Rothblum, R.D.: From obfuscation to the security of Fiat-Shamir for proofs. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 224–251. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_8CrossRef

Kleinberg, J.M.: The small-world phenomenon: an algorithmic perspective (2000)

Lovász, L., Lov, L., Erdos, O.: Random walks on graphs: a survey (1996)

Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society (2008)

Mislove, A., Marcon, M., Gummadi, K.P., Druschel, P., Bhattacharjee, B.: Measurement and analysis of online social networks (2007)

Mohaisen, A., Yun, A., Kim, Y.: Measuring the mixing time of social graphs (2010)

Micali, S.: Computationally sound proofs. SIAM J. Comput. 30, 1253–1298 (2000)MathSciNetCrossRef

Naor, M., Parter, M., Yogev, E.: The power of distributed verifiers in interactive proofs. In: Electronic Colloquium on Computational Complexity (ECCC) (2018)

Newman, M., Watts, D.: Renormalization group analysis of the small-world network model. Phys. Lett. A 263, 341–346 (1999)MathSciNetCrossRef

Newman, M., Watts, D.: Scaling and percolation in the small-world network model. Phys. Rev. E 60, 7332 (1999)CrossRef

Quattrociocchi, W., Scala, A., Sunstein, C.R.: Echo chambers on Facebook. Available at SSRN 2795110 (2016)

Ribeiro, B.F., Towsley, D.F.: Estimating and sampling graphs with multidimensional random walks (2010)

Rothblum, G.N., Vadhan, S.P., Wigderson, A.: Interactive proofs of proximity: delegating computation in sublinear time. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) ACM (2013)

Tal, A.: Tight bounds on the fourier spectrum of AC0 (2017)

Ugander, J., Karrer, B., Backstrom, L., Marlow, C.: The anatomy of the Facebook social graph. CoRR (2011)

List of mergers and acquisitions by Facebook. https://en.wikipedia.org/wiki/List_of_mergers_and_acquisitions_by_Facebook

Xiao, C., Freeman, D.M., Hwa, T.: Detecting clusters of fake accounts in online social networks (2015)

Ye, S., Wu, S.F.: Estimating the size of online social networks. IJSCCPS 1, 160–179 (2011)CrossRef

Zhou, J., Li, Y., Adhikari, V.K., Zhang, Z.-L.: Counting YouTube videos via random prefix sampling. In: Association for Computing Machinery, New York (2011). ISBN 9781450310130

Titel: Interactive Proofs for Social Graphs
verfasst von: Liran Katzir
Clara Shikhelman
Eylon Yogev
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2020
Print ISBN: 978-3-030-56876-4

Electronic ISBN: 978-3-030-56877-1

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-56877-1_20

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner