## Computing in social networks

### Details

Download: BIB_6DB26138126D.P001.pdf (760.43 [Ko])

State: Serval

Version: author

State: Serval

Version: author

Serval ID

serval:BIB_6DB26138126D

Type

**Article**: article from journal or magazin.

Collection

Publications

Fund

Title

Computing in social networks

Journal

Information and Computation

ISSN

0890-5401

Publication state

Published

Issued date

02/2014

Peer-reviewed

Oui

Volume

234

Pages

3-16

Language

english

Abstract

This paper defines the problem of Scalable Secure computing in a Social network: we call it the S3 problem. In short, nodes, directly reflecting on associated users, need to compute a symmetric function f:Vn→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 Ω(n), any protocol that S3-computes component-wise addition of vectors of integers S3-computes f.

We then present AG-S3, a protocol that S3-computes a class of aggregation functions, that is that can be expressed as a commutative monoid operation on U : f(x1,...,xn)=x1⊕⋯⊕xn, assuming the number of faulty participants is at most View the MathML source. We further prove that AG-S3 S3-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.

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 Ω(n), any protocol that S3-computes component-wise addition of vectors of integers S3-computes f.

We then present AG-S3, a protocol that S3-computes a class of aggregation functions, that is that can be expressed as a commutative monoid operation on U : f(x1,...,xn)=x1⊕⋯⊕xn, assuming the number of faulty participants is at most View the MathML source. We further prove that AG-S3 S3-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.

Keywords

Distributed computing, Security, Privacy, Social networks

Web of science

Publisher's website

Create date

03/11/2016 14:00

Last modification date

14/12/2016 14:41