Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Computing in social networks
 
Loading...
Thumbnail Image
research article

Computing in social networks

Giurgiu, Andrei  
•
Guerraoui, Rachid  
•
Huguenin, Kevin
Show more
2014
Information And Computation

This paper defines the problem of Scalable Secure computing in a Social network: we call it the S-3 problem. In short, nodes, directly reflecting on associated users, need to compute a symmetric function f : V-n -> U of their inputs in a set of constant size, in a scalable and secure way. Scalability means that the spatial, computational and message complexity of the distributed computation does not grow too fast with the number of nodes n. Security encompasses (1) accuracy and (2) privacy: accuracy holds when the distance from the output to the ideal result is negligible with respect to the maximum distance between any two possible results; privacy is characterized by how the information disclosed by the computation helps faulty nodes infer inputs of non-faulty nodes, which we capture in our context by the very notion of probabilistic anonymity. We first prove that under mild regularity conditions the problem of computing an arbitrary function can be reduced to that of component-wise addition of vectors of integers. More specifically, if the function f is Lipschitz-continuous and the maximum distance between two possible results is Omega(n), any protocol that S-3-computes component-wise addition of vectors of integers S-3-computes f. We then present AG-S3, a protocol that S-3-computes a class of aggregation functions, that is that can be expressed as a commutative monoid operation on U: f (x(1),...,x(n)) = x(1) circle plus ... circle plus x(n), assuming the number of faulty participants is at most root n/log(2)n. We further prove that AG-S3 S-3-computes component-wise addition of vectors of integers thus extending its application spectrum to regular functions. Key to our protocol is a dedicated overlay structure that enables secret sharing and distributed verifications which leverage the social aspect of the network: nodes care about their reputation and do not want to be tagged as misbehaving. (C) 2013 Elsevier Inc. All rights reserved.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

computing_in_social_1-s2.0-S0890540113001259-main.pdf

Type

Publisher's Version

Access type

openaccess

Size

465.34 KB

Format

Adobe PDF

Checksum (MD5)

72103ebab5500c43714e3ff740027829

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés