Examples
Multiple hospitals come together to run genetic study using combined patient records but without revealing records to each other.
Web browser and ad server execute protocol by which browser downloads ads relevant to user but does not leak user’s browsing history to server.
Google’s FLoC was designed to achieve something similar, but I don’t think it has strong privacy guarantees.
Private Set Intersection
A typical scenario:
- Firm has a list, \([a_1, a_2, …, a_n]\), of IP addresses of attack attempts
- FBI has a list, \([b_1, b_2, …, b_n]\), of IP addresses of investigation suspects
- Both parties want to learn the intersection
- Neither wants the other to learn IPs it doesn’t already know
Hashing doesn’t work because IP addresses, especially IPv4, can be enumerated by brute force and/or other guessing strategies in reasonable time.
IPv4 is a 32-bit address space, so \(2^{32} = 4,294,967,296 \) unique addresses. How fast can one compute a SHA-256 hash? I can’t find a definite answer in terms of hashes/sec.
appears top search results, and their results for SHA-256 are \(111 MiB/s\) and 15.8 cycles per byte.
IPv4 has 4 bytes, so \(15.8 \cdot 4 = 63.2 \) cycles per IPv4. \(1 MiB = 2^{20}B \therefore 1MiB = 2^{18} IPv4 \), and therefore we have \(111 \cdot 2^{18}\) IPv4s per second? That seems pretty fast. We’d get through the entire IPv4 space in \(\frac{2^32}{111 \cdot 2^18} = 147.60s\). Is this math right? Seems too fast; I expected “reasonable time” in the order of 30min, not 2min…
Here’s a scheme that works:
Fix a prime \(p\). Let Alice pick their own \(x\), and Bob pick their own \(y\)
Alice sends \([a_1^x \pmod p, a_2^x \pmod p, … ]\), while Bob sends \([b_1^y \pmod p, b_2^y \pmod p, … ]\)
Alice computes and sends \([ b_1^{yx} \pmod p, b_2^{yx} \pmod p, … ]\). Bob computes and sends \([ a_1^{xy} \pmod p, a_2^{xy} \pmod p, … ]\)
One trick for solving privacy puzzles is to exploit associative properties.
- To compute the intersection:
$$ a_i == b_j \iff a_i^{xy} \pmod p == b_j^{yx} \pmod p $$
References
- Secure Multi-Party Computation. en.wikipedia.org . Accessed Oct 27, 2021.
- Speed Comparison of Popular Crypto Algorithms. cryptopp.com . Accessed Oct 27, 2021.
Timeline of Secure Multi-Party Communication
In 1982, secure two-party computation (2PC) was introduced for problems that are boolean predicates, e.g. Yao’s Millionaires' Problem that asks whether \(a \ge b\) is true without revealing the actual values of \(a\) and \(b\).
Andrew Yao generalized 2PC for any feasible computation in 1986. Goldreich, Micali and Wigderson later generalized it to secure multiparty communication.
Yao-based protocols requires that the function to be securely evaluated be represented as a circuit, but an efficient transformation is not trivial. The Fairplay system transforms a program in a high-level language into a boolean circuit representation, garbles that circuit and then executes a protocol to evaluate the garbled circuit. AES’s circuit has \(\approx 50K\) gates, while the 4095-bit edit distance function has \(\approx 6B\) gates.
Additionally, Pinker et al. showed that the bottleneck of the protocols lie in the consistency checks. Recent research has been on highly parallel implementations to speed things up.