International Association
for Cryptologic Research

The existing works on privacy-preserving recommender systems based on homomorphic encryption do not filter top-k most relevant items on the server side. As a result, sending the encrypted rating vector for all items to the user retrieving the top-k items is necessary. This incurs significant computation and communication costs on the user side.

In this work, we employ private sorting at the server to reduce the user-side overheads. In private sorting, the values and corresponding positions of elements must remain private. We use an existing private sorting protocol by Foteini and Olga and tailor it to the privacy-preserving top-k recommendation applications. We enhance it to use secure bit decomposition in the private comparison routine of the protocol. This leads to a notable reduction in cost overheads of users as well as the servers, especially at the keyserver where the computation cost is reduced to half. The dataserver does not have to perform costly encryption and decryption operations. It performs computationally less expensive modular exponentiation operations. Since the private comparison operation contributes significantly to the overall cost overhead, making it efficient enhances the sorting protocol’s performance. Our security analysis concludes that the proposed scheme is as secure as the original protocol.