# Computing in Social Networks

### Details

Download: BIB_1D09FA0D4AFD.P001.pdf (310.45 [Ko])

State: Serval

Version: author

State: Serval

Version: author

Serval ID

serval:BIB_1D09FA0D4AFD

Type

**Inproceedings**: An article in a conference proceedings.

Collection

Publications

Fund

Title

Computing in Social Networks

Title of the conference

Proceedings of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)

Publisher

Springer

Address

New York, NY, USA

ISBN

978-3-642-16022-6

978-3-642-16023-3

978-3-642-16023-3

ISSN

0302-9743

1611-3349

1611-3349

Publication state

Published

Issued date

2010

Peer-reviewed

Oui

Volume

6366

Series

Lecture Notes in Computer Science

Pages

332-346

Language

english

Abstract

This paper defines the problem of Scalable Secure Computing in a Social network: we call it the S³ problem. In short, nodes, directly reflecting on associated users, need to compute a function f : V → U of their inputs in a set of constant size, in a scalable and secure way. Scalability means that the message and computational complexity of the distributed computation is at most O(√n · polylog 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.

We present AG-S3, a protocol that S³-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 √n/log²n. 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 present AG-S3, a protocol that S³-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 √n/log²n. 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.

Create date

01/12/2016 12:01

Last modification date

03/03/2018 14:33