Secure-Computation-Friendly Private Set Intersection from Oblivious Compact Graph Evaluation

Secure-Computation-Friendly Private Set Intersection from Oblivious Compact Graph Evaluation

연구 분야: Cryptography

학회: ASIA CCS '22: Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security

Private set intersection (PSI) is a secure two-party computation ($2$PC) protocol that reveals only the intersection of two private sets. Driven by different applications, various works devise specific protocols for private computation on the intersection (PCI), e.g., summation of the values labeled with each element in the intersection. Upgrading a PSI protocol to PCI for generic computations while maintaining efficiency and preventing leakage is known to be not straightforward (e.g., the intersection set size could be leaked). Ciampi and Orlandi (SCN'18) proposed a generic, one-of-a-kind, and concretely efficient PSI design that is compatible with common 2PC paradigms for realizing PCI, namely, garbled circuits, secret sharing, and homomorphic encryption. Its core is a 2PC protocol for private set membership, ƒ(x, (Y, ({γ0, γ1})) = (γ(x ∈ Y), ⊥), which uses only symmetric-key operations and oblivious transfer. This paper continues their endeavor, which "compresses" the graph representation of set Y to reduce the computation and communication costs (e.g., 40%/58% for the latter, when |Y| = 220 /224 with the security parameter λ = 128). Our protocol is inspired by a recent (outsourceable) 2PC protocol for decision tree evaluation by Ma et al. (NDSS'21). We overcome the challenges of supporting the branching program needed by Ciampi and Orlandi by extending a protocol for a tree, e.g., allowing a node to have multiple "real" and "fake" parents while hiding the "spine" of the branching program without padding the maximum possible number of fake ciphertexts. As a bonus, we extend our PCI protocol to the secure outsourcing setting. Such PCI protocols are scarcer. We also briefly discuss a PCI application in contact tracing for fine-grained privacy control.