k-Anonymously Private Search over Encrypted Data
This work addresses privacy-preserving search for users handling sensitive data, but it is incremental as it benchmarks existing methods.
The paper compared homomorphic encryption methods for private search with k-anonymity, finding that Goldwasser-Micali encryption offers practical performance while fully homomorphic encryptions are significantly slower.
In this paper we compare the performance of various homomorphic encryption methods on a private search scheme that can achieve $k$-anonymity privacy. To make our benchmarking fair, we use open sourced cryptographic libraries which are written by experts and well scrutinized. We find that Goldwasser-Micali encryption achieves good enough performance for practical use, whereas fully homomorphic encryptions are much slower than partial ones like Goldwasser-Micali and Paillier.