Guard: secure routing in skip graph

Abstract

Skip Graph is a distributed hash table (DHT) which acts as the underlying infrastructure in various P2P applications such as cloud storage and online social networks. The basic operation in Skip Graph is the search which is done in a fully decentralized manner. Any misbehavior of peers during the routing of a search query heavily degrades the system functionality. Security of search queries is the missing feature of Skip Graph, and applying existing DHT-based solutions on a Skip Graph reduces the search operation's efficiency and degrades the performance of query processing and response time. In this work, we propose Guard, the first fully decentralized secure search mechanism for Skip Graph, that provides authenticated and reliable search operation in a fully decentralized manner. Guard secures Skip Graph against the Sybil attack and routing attacks in the presence of the malicious colluding nodes. In contrast to the existing solutions, security of our design is formally proven.