Computing in Social Networks

Details

Ressource 1Download: BIB_1D09FA0D4AFD.P001.pdf (310.45 [Ko])
State: Public
Version: author
Serval ID
serval:BIB_1D09FA0D4AFD
Type
Inproceedings: an article in a conference proceedings.
Collection
Publications
Title
Computing in Social Networks
Title of the conference
Proceedings of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
Author(s)
Giurgiu A., Guerraoui R., Huguenin K., Kermarrec A.-M.
Publisher
Springer
Address
New York, NY, USA
ISBN
978-3-642-16022-6
978-3-642-16023-3
ISSN
0302-9743
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.
Create date
01/12/2016 11:01
Last modification date
20/08/2019 12:53
Usage data