(K, P)-SHORTEST PATH ALGORITHM IN THE CLOUD MAINTAINING NEIGHBORHOOD PRIVACY

Privacy-preserving computation has recently attracted much attention in areas of transaction, social networking, location-based, and mobile services. The inexpensive storage and efficient computation of cloud computing technology is expected to further escalate these services to a higher and wider level, without compromising the breaches of sensitive information. In this work, we study the shortest path distance computing in the cloud while preserving two types of privacy in the same time: k-neighborhood privacy and sensitive path privacy. We propose a new privacy model called (k, p)-shortest path neighborhood privacy, which is an extension of [19] and more flexible than 1-neighborhood-d-radius model [6]. We also develop an efficient four-step shortest distance computation scheme to achieve (k, p)- shortest path neighborhood privacy on p outsourced servers in the cloud, which combines the construction of k-skip shortest path sub-graphs, sensitive vertex adjustment, vertex hierarchy labeling and bottom-up partitioning techniques. Numerical experiments show that the proposed approach is more efficient than prior model of constructing the 1-neighborhood privacy graph and also requires less querying time.