Privacy amplification with social networks

Shishir Nagaraja

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

1 Citation (Scopus)


There are a number of scenarios where users wishing to communicate, share a weak secret. Often, they are also part of a common social network. Connections (edges) from the social network are represented as shared link keys between participants (vertices). We propose mechanisms that utilise the graph topology of such a network, to increase the entropy of weak pre-shared secrets. Our proposal is based on using random walks to identify a chain of common acquaintances between Alice and Bob, each of which contribute entropy to the final key. Our mechanisms exploit one-wayness and convergence properties of Markovian random walks to, firstly, maximize the set of potential entropy contributors, and second, to resist any contribution from dubious sources such as Sybill sub-networks.

Original languageEnglish
Title of host publicationSecurity Protocols - 15th International Workshop, Revised Selected Papers
EditorsBruce Christianson, Bruno Crispo, James A. Malcolm, Michael Roe
Number of pages16
ISBN (Print)3642177727, 9783642177729
Publication statusPublished - 1 Jan 2010
Event15th International Workshop on Security Protocols - Brno, Czech Republic
Duration: 18 Apr 200720 Apr 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5964 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference15th International Workshop on Security Protocols
Country/TerritoryCzech Republic


  • social network
  • random walk
  • random graph
  • small world networks
  • graph topology


Dive into the research topics of 'Privacy amplification with social networks'. Together they form a unique fingerprint.

Cite this