Privacy-Preserving Distributed Computation
Jonathan Katz · 2024
In many settings, it would be useful to have access to a “trusted entity” who performs computations on behalf of different parties (servers, administrators, users, etc.). For example: Consider a user who wants to privately query a database D held by a server. (For example, the user may want to search a medical database for information about diseases consistent with a set of symptoms the user is experiencing, while being unwilling to reveal its symptoms to the company hosting the database.) That is, the user wants to learn the result of their query q while not revealing q to the server. If a trusted entity were available, this problem could be solved by having the two parties send q and D , respectively, to that entity, who then evaluates the query and returns the result to the user. Imagine there are multiple companies which wish to generate statistics about all their employees; however, none of the companies is willing to reveal sensitive information about its employees to any other company. (For example, companies in Boston might want to measure the overall wage gap between men and women employed at those companies, but be unwilling to share payroll data. 1 ) Here, again, a trusted entity could be used to solve this problem: each company would simply send its sensitive data to the trusted entity, who could then compute the desired statistics and send the results back to everyone. A collection of distributed servers may wish to maintain a tamper-proof log of ordered transactions (i.e., a blockchain ) on which they all agree. In this setting, a trusted entity could accept transactions from the servers and locally maintain an ordered log; it can share the current log (or any portion thereof) with any server upon request. A trusted entity can even be useful in cases involving a single user. Consider a user who is concerned about potential exposure of her secret cryptographic key sk in case her machine is hacked. She could mitigate this threat by splitting the master key sk across multiple machines, giving each machine a share of the key that, by itself, reveals nothing about sk . (Formally, this could be done using a cryptographic mechanism called secret sharing , but the details are unimportant for this high-level discussion.) Cryptographic operations could then be carried out by having each machine send its share to a trusted entity, who combines the shares to recover sk and then applies the desired operation (e.g., decrypting some file). This is known as threshold cryptography .