Private Computing with Untrustworthy Proxies
Bartek Gedrojc · Research Repository (Delft University of Technology) · 2011
The objective of this thesis is to preserve privacy for the user while untrustworthy proxies are involved in the communication and computation i.e. private computing. A basic example of private computing is an access control system (proxy) which grants access (or not) to users based on fingerprints. For privacy reasons the user does not want to reveal his fingerprint to the system, since he does not trust the system in storing his fingerprint securely. The system uses a mechanism to compare a new fingerprint with previously collected fingerprints, in order to verify the identity of the user. The challenge is that fingerprints, even if they are from the same user, are never exactly equal like passwords are. This makes fingerprints hard to compare, especially when the system should not learn anything from these fingerprints other than if they are equal or not. This thesis addresses two problems within private computing. First, the problem of letting an untrustworthy proxy collect private information from various sources is investigated. The challenge is to let the untrustworthy proxy perform the collection of the selected information, while guaranteeing confidentiality of the inputs and outputs. Second, the problem of letting an untrustworthy proxy compare the collected private information is addressed. The challenge is to let the untrustworthy proxy compute a comparison function without being able to learn the actual inputs, but being allowed to learn the outcome of the function. The problem is similar to the Millionaires' problem known from Multi-Party Computation, however in the private computing case the untrustworthy proxy learns the outcome of the computation without having to inform the users. For the selection and collection problem two approaches are addressed. First, the parallel selection and collection approach is considered whereby an untrustworthy proxy collects information simultaneously from various sources without loosing the users privacy. The problem is presented within a location-based services (LBS) scenario with the goal to protect private location data. The solution is based on two distinct oblivious transfers and the usage of homomorphic encryption. Second, the sequential selection and collection approach is considered where information is collected from various sources based on a fixed itinerary before returning with the results to the proxy. The solution is provided using threshold signature schemes and hash chaining. Furthermore, a mechanism is constructed which ensures that the itinerary is completed even if one of the sources is unavailable. Two approaches are addressed for the comparison problem. First, a single comparison is undertaken, where the untrustworthy proxy computes one inequality function. The solution is to use a bit-wise comparison protocol and reconstruct it in such a way that the proxy leaks one bit of information (the result of the comparison) but nothing else. The reconstruction of the protocol is based on multiple homomorphic encryptions and decryptions using ElGamal. Finally, the multiple comparison problem is addressed which can be applied to the fingerprint matching problem as described above. The challenge is to let an untrustworthy proxy compare multiple inequality functions, learning only if all off the functions satisfied the comparison conditions or that some failed while letting the proxy remain oblivious to which conditions failed. The output of the function also only leaks one bit of information. The solution is based on the same bit-wise comparison protocol as the single comparison but it is reconstructed using a different homomorphic encryption scheme and extending the hiding function used for comparison. This thesis demonstrats that private computing protocols can be designed to protect the privacy of the users while providing functionality in the cryptographic domain. Moreover, the presented protocols can also be applied within other applications where untrustworthy proxies are unavoidable.