Authenticating strangers in Online Social Networks

摘要

In current Online Social Networks (OSNs), it is necessary for a user to determine whether a claimed public key belongs to a target user. In this paper, we design a system to complete this task. We first find a common friend between two users and let her help to prove the ownership of the public key. The common friend is proved to exist with high probability in fast mixing OSNs. We also propose a protocol to securely compute the intersection of friend sets. The effectiveness of the system is demonstrated by simulation.