{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:03Z","timestamp":1750694763398,"version":"3.40.3"},"publisher-location":"Cham","reference-count":53,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030568764"},{"type":"electronic","value":"9783030568771"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-56877-1_20","type":"book-chapter","created":{"date-parts":[[2020,8,11]],"date-time":"2020-08-11T17:17:58Z","timestamp":1597166278000},"page":"574-601","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Interactive Proofs for Social Graphs"],"prefix":"10.1007","author":[{"given":"Liran","family":"Katzir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clara","family":"Shikhelman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eylon","family":"Yogev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,10]]},"reference":[{"key":"20_CR1","unstructured":"Addario-Berry, L., T, Lei.: \u201cThe mixing time of the Newman-Watts small world\u201d. In"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Alvisi, L., Clement, A., Epasto, A., Lattanzi, S., Panconesi, A.: Sok: the evolution of sybil defense via social networks. IEEE (2013)","DOI":"10.1109\/SP.2013.33"},{"key":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-662-53644-5_2","volume-title":"Theory of Cryptography","author":"E Ben-Sasson","year":"2016","unstructured":"Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive Oracle proofs. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 31\u201360. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53644-5_2"},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"1531","DOI":"10.1177\/0956797615594620","volume":"26","author":"P Barber\u00e1","year":"2015","unstructured":"Barber\u00e1, 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\u20131542 (2015)","journal-title":"Psychol. Sci."},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1411509.1411514","volume":"55","author":"Z Bar-Yossef","year":"2008","unstructured":"Bar-Yossef, Z., Gurevich, M.: Random sampling from a search engine\u2019s index. J. ACM 55, 1\u201374 (2008)","journal-title":"J. ACM"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Gurevich, M.: Estimating the ImpressionRank of web pages (2009)","DOI":"10.1145\/1526709.1526716"},{"key":"20_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2019643.2019645","volume":"5","author":"Z Bar-Yossef","year":"2011","unstructured":"Bar-Yossef, Z., Gurevich, M.: Efficient search engine measurements. TWEB 5, 1\u201348 (2011)","journal-title":"TWEB"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1754399.1754401","volume":"57","author":"M Braverman","year":"2010","unstructured":"Braverman, M.: Polylogarithmic independence fools $$AC^{0}$$ circuits. J. ACM 57, 1\u201310 (2010)","journal-title":"J. ACM"},{"key":"20_CR9","unstructured":"Brede, M.: Networks-an introduction. In: Newman, M.E.J. (ed.) 2010 Artificial Life. Oxford University Press (2012)"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Broder, A., et al.: Estimating corpus size via queries. In: Association for Computing Machinery (2006)","DOI":"10.1145\/1183614.1183699"},{"key":"20_CR11","unstructured":"Canetti, R., Chen, Y., Holmgren, J., Lombardi, A., Rothblum, G.N., Rothblum, R.D.: Fiat-Shamir from simpler assumptions. IACR Cryptology ePrint Archive (2018)"},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-319-78381-9_4","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"R Canetti","year":"2018","unstructured":"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\u2013122. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78381-9_4"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Chiericetti, F., Dasgupta, A., Kumar, R., Lattanzi, S., Sarl\u00f3s, T.: On sampling nodes in a network (2016)","DOI":"10.1145\/2872427.2883045"},{"key":"20_CR14","first-page":"1804","volume":"8","author":"A Ching","year":"2015","unstructured":"Ching, A., Edunov, S., Kabiljo, M., Logothetis, D., Muthukrishnan, S.: One trillion edges: graph processing at Facebook-scale. PVLDB 8, 1804\u20131815 (2015)","journal-title":"PVLDB"},{"key":"20_CR15","unstructured":"Chierichetti, F., Haddadan, S.: On the complexity of sampling vertices uniformly from a graph (2018)"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"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\u2013242 (2006)","DOI":"10.1080\/00018730601170527"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Canetti, R., et al.: Fiat-Shamir: from practice to theory (2019)","DOI":"10.1145\/3313276.3316380"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Dasgupta, A., Kumar, R., Sarl\u00f3s, T.: On estimating the average degree. ACM (2014)","DOI":"10.1145\/2566486.2568019"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Ersahin, B., Aktas, \u00d6., Kilin\u00e7, D., Akyol, C.: Twitter fake account detection. IEEE (2017)","DOI":"10.1109\/UBMK.2017.8093420"},{"key":"20_CR20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761942","volume-title":"Networks, Crowds, and Markets - Reasoning About a Highly Connected World","author":"DA Easley","year":"2010","unstructured":"Easley, D.A., Kleinberg, J.M.: Networks, Crowds, and Markets - Reasoning About a Highly Connected World. Cambridge University Press, Cambridge (2010)"},{"key":"20_CR21","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.ic.2003.09.005","volume":"189","author":"F Erg\u00fcn","year":"2004","unstructured":"Erg\u00fcn, F., Kumar, R., Rubinfeld, R.: Fast approximate probabilistically checkable proofs. Inf. Comput. 189, 135\u2013159 (2004)","journal-title":"Inf. Comput."},{"key":"20_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 86","author":"A Fiat","year":"1987","unstructured":"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\u2013194. Springer, Heidelberg (1987). https:\/\/doi.org\/10.1007\/3-540-47721-7_12"},{"key":"20_CR23","doi-asserted-by":"crossref","unstructured":"Fortnow, L.: The complexity of perfect zero-knowledge. In: STOC 1987 (1987)","DOI":"10.1145\/28395.28418"},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Garimella, K., De Francisci Morales, G., Gionis, A., Mathioudakis, M.: Political discourse on social media: echo chambers, gatekeepers, and the price of bipartisanship (2018)","DOI":"10.1145\/3178876.3186139"},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1109\/INFCOM.2010.5462078"},{"key":"20_CR26","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S Goldwasser","year":"1989","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 186\u2013208 (1989)","journal-title":"SIAM J. Comput."},{"key":"20_CR27","unstructured":"Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: Advances in Computing Research (1989)"},{"key":"20_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-11799-2_1","volume-title":"Theory of Cryptography","author":"J H\u00e5stad","year":"2010","unstructured":"H\u00e5stad, J., Pass, R., Wikstr\u00f6m, D., Pietrzak, K.: An efficient parallel repetition theorem. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 1\u201318. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11799-2_1"},{"key":"20_CR29","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1140\/epjb\/e2009-00292-2","volume":"71","author":"SJ Hardiman","year":"2009","unstructured":"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)","journal-title":"Eur. Phys. J. B"},{"key":"20_CR30","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.20786","volume":"54","author":"P Harsha","year":"2019","unstructured":"Harsha, P., Srinivasan, S.: On polynomial approximations to AC. Random Struct. Algorithms 54, 289\u2013303 (2019)","journal-title":"Random Struct. Algorithms"},{"key":"20_CR31","unstructured":"Kurant, M., Butts, C.T., Markopoulou, A.: Graph size estimation. CoRR (2012)"},{"key":"20_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2790304","volume":"9","author":"L Katzir","year":"2015","unstructured":"Katzir, L., Hardiman, S.J.: Estimating clustering coefficients and size of social networks via random walk. ACM Trans. Web 9, 1\u201320 (2015)","journal-title":"ACM Trans. Web"},{"key":"20_CR33","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1080\/15427951.2013.862883","volume":"10","author":"L Katzir","year":"2014","unstructured":"Katzir, L., Liberty, E., Somekh, O., Cosma, I.A.: Estimating sizes of social networks via biased sampling. Internet Math. 10, 335\u2013359 (2014)","journal-title":"Internet Math."},{"key":"20_CR34","unstructured":"Kanade, V., Mallmann-Trenn, F., Verdugo, V. How large is your graph? (2017)"},{"key":"20_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-319-63715-0_8","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"YT Kalai","year":"2017","unstructured":"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\u2013251. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63715-0_8"},{"key":"20_CR36","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M.: The small-world phenomenon: an algorithmic perspective (2000)","DOI":"10.1145\/335305.335325"},{"key":"20_CR37","unstructured":"Lov\u00e1sz, L., Lov, L., Erdos, O.: Random walks on graphs: a survey (1996)"},{"key":"20_CR38","doi-asserted-by":"crossref","unstructured":"Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society (2008)","DOI":"10.1090\/mbk\/058"},{"key":"20_CR39","doi-asserted-by":"crossref","unstructured":"Mislove, A., Marcon, M., Gummadi, K.P., Druschel, P., Bhattacharjee, B.: Measurement and analysis of online social networks (2007)","DOI":"10.1145\/1298306.1298311"},{"key":"20_CR40","doi-asserted-by":"crossref","unstructured":"Mohaisen, A., Yun, A., Kim, Y.: Measuring the mixing time of social graphs (2010)","DOI":"10.1145\/1879141.1879191"},{"key":"20_CR41","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/S0097539795284959","volume":"30","author":"S Micali","year":"2000","unstructured":"Micali, S.: Computationally sound proofs. SIAM J. Comput. 30, 1253\u20131298 (2000)","journal-title":"SIAM J. Comput."},{"key":"20_CR42","unstructured":"Naor, M., Parter, M., Yogev, E.: The power of distributed verifiers in interactive proofs. In: Electronic Colloquium on Computational Complexity (ECCC) (2018)"},{"key":"20_CR43","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/S0375-9601(99)00757-4","volume":"263","author":"M Newman","year":"1999","unstructured":"Newman, M., Watts, D.: Renormalization group analysis of the small-world network model. Phys. Lett. A 263, 341\u2013346 (1999)","journal-title":"Phys. Lett. A"},{"key":"20_CR44","doi-asserted-by":"publisher","first-page":"7332","DOI":"10.1103\/PhysRevE.60.7332","volume":"60","author":"M Newman","year":"1999","unstructured":"Newman, M., Watts, D.: Scaling and percolation in the small-world network model. Phys. Rev. E 60, 7332 (1999)","journal-title":"Phys. Rev. E"},{"key":"20_CR45","doi-asserted-by":"crossref","unstructured":"Quattrociocchi, W., Scala, A., Sunstein, C.R.: Echo chambers on Facebook. Available at SSRN 2795110 (2016)","DOI":"10.2139\/ssrn.2795110"},{"key":"20_CR46","doi-asserted-by":"crossref","unstructured":"Ribeiro, B.F., Towsley, D.F.: Estimating and sampling graphs with multidimensional random walks (2010)","DOI":"10.1145\/1879141.1879192"},{"key":"20_CR47","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1145\/2488608.2488709"},{"key":"20_CR48","unstructured":"Tal, A.: Tight bounds on the fourier spectrum of AC0 (2017)"},{"key":"20_CR49","unstructured":"Ugander, J., Karrer, B., Backstrom, L., Marlow, C.: The anatomy of the Facebook social graph. CoRR (2011)"},{"key":"20_CR50","unstructured":"List of mergers and acquisitions by Facebook. https:\/\/en.wikipedia.org\/wiki\/List_of_mergers_and_acquisitions_by_Facebook"},{"key":"20_CR51","doi-asserted-by":"crossref","unstructured":"Xiao, C., Freeman, D.M., Hwa, T.: Detecting clusters of fake accounts in online social networks (2015)","DOI":"10.1145\/2808769.2808779"},{"key":"20_CR52","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1504\/IJSCCPS.2011.044172","volume":"1","author":"S Ye","year":"2011","unstructured":"Ye, S., Wu, S.F.: Estimating the size of online social networks. IJSCCPS 1, 160\u2013179 (2011)","journal-title":"IJSCCPS"},{"key":"20_CR53","doi-asserted-by":"crossref","unstructured":"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","DOI":"10.1145\/2068816.2068851"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2020"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-56877-1_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T00:10:15Z","timestamp":1691712615000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-56877-1_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030568764","9783030568771"],"references-count":53,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-56877-1_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"10 August 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 August 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"40","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2020\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"HotCRP","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"371","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"85","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"23% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.82","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"19.43","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}