The prosperity of Internet is making our life more connective, colorful and convenient. At the same time, more data breaching incidents have been emerging explosively. And more and more people are concerned about their personal privacy and security. Along with this concerns, cryptographic protocols and technologies attract both academic field and industry field. Many fantastic cryptographic primitives and paradigms such as homomorphic encryption, order-revealing encryption, oblivious storage, etc. have been proposed. These new cryptographic primitives and techniques are widely used to enhance security and privacy. However, these applications are not fully exploited in three aspects, namely, security, privacy, and efficiency. When people try to use cryptographic techniques to enhance security and privacy, these techniques may introduce additional overhead such as computation cost and communication overhead which may make some flaws in these applications.

This thesis presents algorithms and implementations of privacy-preserving applications which leverage the latest progresses of homomorphic encryption.

First, we proposed a practical targeted mobile advertising service framework while preserving user privacy and enabling accurate targeting. In particular, this framework enables accurate and private user targeting through a privacy-preserving matrix factorization protocol via homomorphic operations. To achieve private ads dissemination, it further adopts the latest advancement of private information retrieval (PIR) to allow the users to retrieve the most relevant ads without revealing their profiles and which ads are accessed. Security and cost analysis are conducted to show that our design achieves strong security guarantees with practical performance. Second, we designed practical navigation schemes that preserve users' privacy while achieving practical shortest path recommendation. The proposed schemes are based on graph encryption schemes that enable privacy assured approximate shortest path queries on large-scale encrypted graphs. We first leverage a data structure called a distance oracle to create sketch information. Further we add path information to the data structure and design three structured encryption schemes. The first scheme is straightforward and computationally efficient. It is based on oblivious storage. The second scheme takes advantage of the latest cryptographic techniques to find the minimal distance and achieves optimal communication complexity. The third scheme adopts homomorphic encryption scheme and achieves efficient communication overhead and computation overhead on the client side. The first two schemes support privacy-preserving shortest path query and provide robust privacy guarantees without introducing any third party. While the third scheme introduces minimum computation overhead and communication overhead.

Third, we also evaluate our schemes systematically. And we further conduct a fine-grained investigation about how to select the parameters to achieve practical performance. The evaluation reveals the relationship between the parameters and the performance of batching homomorphic operations.

And our results show that the computation overhead and communication overhead are reasonable and practical.