We present a system, Sandi, for creating trust through accountability. Concretely, we focus on online communication scenarios, where the communicating parties do not know each other, yet would benefit from a degree of initial trust. Sandi can be seen as a reputation system that measures bad behavior, with strong integrity protections and resistance to manipulation. Unlike most reputation systems, Sandi is entirely based on "downvotes" and therefore requires strong privacy guarantees to prevent retaliation. It utilizes a ticket-based reporting mechanism to limit who can report. We also prove that Sandi incentivizes good behavior in a well-defined sense.Sandi is by design unidirectional, so that message senders have Sandi scores and receivers can report them for inappropriate communication, but it is designed to benefit both senders and receivers. Senders benefit, as receivers are more likely to react to communication with the added trust signal. Receivers benefit from seeing senders’ scores, allowing them to make more informed decisions about which senders to trust.Receivers do not need registered accounts and neither senders nor receivers need long-term keys. Sandi guarantees score integrity, communication privacy, reporter privacy to protect reporting receivers, and sender unlinkability. Sandi can be implemented on top of any communication system that allows for small binary data transfer.

It is known that fully homomorphic encryption (FHE) can be used to build efficient (labeled) Private Set Intersection protocols in the unbalanced setting, where one of the sets is much larger than the other~(Chen et al. (CCS'17, CCS'18)). In this paper we demonstrate multiple algorithmic improvements upon these works. In particular, our protocol has an asymptotically better computation cost, requiring only O(√|X| ) homomorphic multiplications, and communication complexity sublinear in the larger set size|X|. We demonstrate that our protocol is significantly better than that of Chen et al. (CCS'18) for many practical parameters, especially in terms of online communication cost. For example, when intersecting $228 and 2048 item sets, our protocol reduces the online computation time by more than 71% and communication by more than 63%. When intersecting 224 and 4096 item sets, our protocol reduces the online computation time by 27% and communication by 63%. Our comparison to other state-of-the-art unbalanced PSI protocols shows that our protocol has the best total communication complexity when |X| ≥ 224. For labeled PSI our protocol also outperforms Chen et al. (CCS'18). When intersecting 220 and 256 item sets, with the larger set having associated 288-byte labels, our protocol reduces the online computation time by more than 67% and communication by 34%. Finally, we demonstrate a modification that results in nearly constant communication cost in the larger set size |X|, but impractically high computation complexity on today's CPUs. For example, to intersect a 210-item set with sets of size 222, 224, or 226, our proof-of-concept implementation requires only 0.76 MB of online communication, which is more than a 24-fold improvement over Chen et al. (CCS'18).