Date Added: Nov 2012
Authenticating users in Online Social Networks (OSNs) is different from traditional authentication, because the participants in the authentication may not share any prior secret information. In this paper, the authors propose a decentralized authentication framework to help users authenticate unknown users in an OSN. In their framework, a user requests certificates from other trusted users to prove his identity in authentication. However, collecting certificates is constrained by the fact that trust is usually attritted with the length of a trust chain. Considering this constraint, their framework utilizes a decentralized online learning approach to help users collect more certificates. They further prove that the number of the collected certificates by each user using their protocols is close to optimum.