Robust Privacy-Preserving Gossip Averaging | SpringerLink
Skip to main content
Springer Nature Link
Log in

Robust Privacy-Preserving Gossip Averaging

  • Conference paper
  • First Online:
Stabilization, Safety, and Security of Distributed Systems (SSS 2019)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11914))

Abstract

Decentralized solutions are emerging as promising candidates to overcome the privacy risks associated with centralized data services. Such solutions suffer however from their own range of privacy vulnerabilities, arising from untrusted and malicious peers. In this paper, we consider the emblematic problem of privacy-preserving decentralized averaging, and propose a novel gossip protocol that exchanges noise for several rounds before starting to exchange actual data. This makes it hard for an honest but curious attacker to know whether a user is transmitting noise or actual data. Our protocol and analysis do not assume a lock-step execution, and demonstrate improved resilience to colluding attackers. We prove the correctness of this protocol as well as several privacy results. Finally, we provide simulation results about the efficiency of our averaging protocol.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The code used for these experiments is available at https://github.com/ALRBP/Private_Gossip_Average.

References

  1. Allard, T., Frey, D., Giakkoupis, G., Lepiller, J.: Lightweight privacy-preserving averaging for the Internet of Things (2016)

    Google Scholar 

  2. Allard, T., Hébrail, G., Masseglia, F., Pacitti, E.: Chiaroscuro: transparency and privacy for massive personal time-series clustering. In: ACM SIGMOD 2015, pp. 779–794 (2015)

    Google Scholar 

  3. Allavena, A., Demers, A., Hopcroft, J.E.: Correctness of a gossip based membership protocol. In: Proceedings of the Twenty-fourth Annual ACM Symposium on Principles of Distributed Computing, pp. 292–301. ACM (2005)

    Google Scholar 

  4. Bortnikov, E., Gurevich, M., Keidar, I., Kliot, G., Shraer, A.: Brahms: Byzantine resilient random membership sampling. Comput. Netw. 53(13), 2340–2359 (2009)

    Article  MATH  Google Scholar 

  5. Clifton, C., Kantarcioglu, M., Vaidya, J., Lin, X., Zhu, M.Y.: Tools for privacy preserving distributed data mining. ACM SIGKDD Explor. Newsl. 4, 28–34 (2002)

    Article  Google Scholar 

  6. Coretti, S., Garay, J., Hirt, M., Zikas, V.: Constant-round asynchronous multi-party computation based on one-way functions. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 998–1021. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_33

    Chapter  Google Scholar 

  7. Danner, G., Jelasity, M.: Fully distributed privacy preserving mini-batch gradient descent learning. In: Bessani, A., Bouchenak, S. (eds.) DAIS 2015. LNCS, vol. 9038, pp. 30–44. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19129-4_3

    Chapter  Google Scholar 

  8. Dellenbach, P., Bellet, A., Ramon, J.: Hiding in the crowd: a massively distributed algorithm for private averaging with malicious adversaries. CoRR (2018)

    Google Scholar 

  9. Dwork, C.: Differential privacy: a survey of results. In: Agrawal, M., Du, D., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol. 4978, pp. 1–19. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-79228-4_1

    Chapter  MATH  Google Scholar 

  10. Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 265–284. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_14

    Chapter  Google Scholar 

  11. Frikken, K.B.: Secure multiparty computation. In: Atallah, M.J., Blanton, M. (eds.) Algorithms and Theory of Computation Handbook, pp. 14.1–14.16. Chapman & Hall/CRC (2010)

    Google Scholar 

  12. Gao, H., Zhang, C., Ahmad, M., Wang, Y.: Privacy-preserving average consensus on directed graphs using push-sum. In: 2018 IEEE Conference on Communications and Network Security (CNS), pp. 1–9. IEEE (2018)

    Google Scholar 

  13. Gupta, N., Chopra, N.: Confidentiality in distributed average information consensus. In: 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 6709–6714. IEEE (2016)

    Google Scholar 

  14. Hadjicostis, C.N.: Privacy preserving distributed average consensus via homomorphic encryption. In: 2018 IEEE Conference on Decision and Control (CDC), pp. 1258–1263. IEEE (2018)

    Google Scholar 

  15. He, J., Cai, L.: Differential private noise adding mechanism: basic conditions and its application. In: 2017 American Control Conference (ACC), pp. 1673–1678. IEEE (2017)

    Google Scholar 

  16. He, J., Cai, L., Cheng, P., Pan, J., Shi, L.: Consensus-based privacy-preserving data aggregation. IEEE Trans. Autom. Control (2016)

    Google Scholar 

  17. He, J., Cai, L., Cheng, P., Pan, J., Shi, L.: Distributed privacy-preserving data aggregation against dishonest nodes in network systems. IEEE Internet Things J. 6(2), 1462–1470 (2019)

    Article  Google Scholar 

  18. He, J., Cai, L., Zhao, C., Cheng, P., Guan, X.: Privacy-preserving average consensus: privacy analysis and optimal algorithm design. IEEE Trans. Signal Inf. Process. Netw. 5(1), 127–138 (2019)

    Article  Google Scholar 

  19. Huang, Z., Mitra, S., Dullerud, G.: Differentially private iterative synchronous consensus. In: Proceedings of the 2012 ACM Workshop on Privacy in the Electronic Society, WPES 2012, pp. 81–90. ACM (2012)

    Google Scholar 

  20. Jelasity, M., Montresor, A., Babaoglu, O.: Gossip-based aggregation in large dynamic networks. ACM Trans. Comput. Syst. 23(3), 219–252 (2005)

    Article  Google Scholar 

  21. Jelasity, M., Voulgaris, S., Guerraoui, R., Kermarrec, A.-M., van Steen, M.: Gossip-based peer sampling. ACM ToCS 25(3), 8 (2007)

    Article  Google Scholar 

  22. Kempe, D., Dobra, A., Gehrke, J.E.: Gossip-based computation of aggregate information. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, pp. 482–491 (2003)

    Google Scholar 

  23. Lepiller, J.: Private decentralized aggregation (2016)

    Google Scholar 

  24. Liu, Q., Ren, X., Mo, Y.: Secure and privacy preserving average consensus. In: 2017 11th Asian Control Conference (ASCC), pp. 274–279. IEEE (2017)

    Google Scholar 

  25. Liu-Zhang, C.-D., Loss, J., Maurer, U., Moran, T., Tschudi, D.: Robust MPC: asynchronous responsiveness yet synchronous security. In: Theory and Practice of Multi-Party Computation Workshops (2019)

    Google Scholar 

  26. Manitara, N.E., Hadjicostis, C.N.: Privacy-preserving asymptotic average consensus. In: 2013 European Control Conference (ECC), pp. 760–765. IEEE (2013)

    Google Scholar 

  27. Mo, Y., Murray, R.M.: Privacy preserving average consensus. In: 53rd IEEE Conference on Decision and Control, pp. 2154–2159. IEEE (2014)

    Google Scholar 

  28. Nédelec, B., Tanke, J., Molli, P., Mostéfaoui, A., Frey, D.: An adaptive peer-sampling protocol for building networks of browsers. World Wide Web 21, 629–661 (2017)

    Article  Google Scholar 

  29. Nozari, E., Tallapragada, P., Cortés, J.: Differentially private average consensus: obstructions, trade-offs, and optimal algorithm design. Automatica 81, 221–231 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  30. Ruan, M., Gao, H., Wang, Y.: Secure and privacy-preserving consensus. IEEE Trans. Autom. Control (2019)

    Google Scholar 

  31. Sheikh, R., Kumar, B., Mishra, D.K.: A distributed k-secure sum protocol for secure multi-party computations. J. Comput. 2, 68–72 (2010)

    Google Scholar 

  32. Thobaben, R., Dán, G., Sandberg, H.: Wiretap codes for secure multi-party computation. In: 2014 IEEE Globecom Workshops (GC Wkshps), pp. 1349–1354. IEEE (2014)

    Google Scholar 

  33. Wang, A., Liao, X., He, H.: Event-triggered differentially private average consensus for multi-agent network. IEEE/CAA J. Automatica Sinica 6(1), 75–83 (2019)

    Article  MathSciNet  Google Scholar 

  34. Wang, X., He, J., Cheng, P., Chen, J.: Privacy preserving collaborative computing: heterogeneous privacy guarantee and efficient incentive mechanism. IEEE Trans. Signal Process. 67(1), 221–233 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  35. Wang, Y.: Privacy-preserving average consensus via state decomposition. IEEE Trans. Autom. Control (2019)

    Google Scholar 

  36. Wyner, A.D.: The wire-tap channel. Bell Syst. Tech. J. 54(8), 1355–1387 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  37. Yin, T., Lv, Y., Yu, W.: Accurate privacy preserving average consensus. IEEE Trans. Circuits Syst. II: Express Briefs (2019)

    Google Scholar 

  38. Zhou, H., Yang, W., Yang, C.: Privacy preserving consensus under interception attacks. In: 2017 36th Chinese Control Conference (CCC), pp. 8485–8490. IEEE (2017)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Univ Rennes, Inria, CNRS, IRISA, Rennes, France

    Amaury Bouchra Pilet, Davide Frey & Francois Taiani

  2. École Normale Supérieure «Ulm», Paris, France

    Amaury Bouchra Pilet

Authors
  1. Amaury Bouchra Pilet
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Davide Frey
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Francois Taiani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Amaury Bouchra Pilet .

Editor information

Editors and Affiliations

  1. ETH Zurich, Zurich, Switzerland

    Mohsen Ghaffari

  2. Kent State University, Kent, OH, USA

    Mikhail Nesterenko

  3. Sorbonne University, Paris, France

    Sébastien Tixeuil

  4. CEA LIST, Gif-sur-Yvette, France

    Sara Tucci

  5. Kyushu University, Fukuoka, Japan

    Yukiko Yamauchi

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bouchra Pilet, A., Frey, D., Taiani, F. (2019). Robust Privacy-Preserving Gossip Averaging. In: Ghaffari, M., Nesterenko, M., Tixeuil, S., Tucci, S., Yamauchi, Y. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2019. Lecture Notes in Computer Science(), vol 11914. Springer, Cham. https://doi.org/10.1007/978-3-030-34992-9_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-34992-9_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-34991-2

  • Online ISBN: 978-3-030-34992-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation