Appendix: Exploiting Data Sparsity in Secure Cross-Platform Social Recommendation

Our protocol requires a bandwidth-efficient single-server PIR scheme. Specifically, in our work, we use the famous Seal PIR [1], which additionally leverages levelled homomorphic encryption scheme Fan-Vercauteren (FV) [2]. Slightly different from the standard PIR scheme, Seal-PIR further allows the client to send a compressed query to the server, which is then decompressed on the server by PIR.Expand algorithm. In general, Seal-PIR consists of four algorithms (see Figure 1): (PIR.Query, PIR.Expand, PIR.Response, PIR.Extract). In particular, we consider single-server PIR with a computationally bounded adversary.