| As the world becomes increasingly dependent on electronic communication, and as such communication falls prey to various forms of surveillance, it is important to investigate whether cryptographic protocols which enable secure electronic communication can have privacy-protecting variants that are efficient enough for practical usage. In this thesis, we present two types of privacy-preserving protocols, namely private mutual authentication and privacy-preserving set intersection.A Private Mutual Authentication, or Secret Handshake, allows two parties to authenticate each other as certified by a certification authority specified in their authentication policy (i.e. affiliated with the group managed by this certification authority), in a mutually private way, in the sense that the protocol leaks no information about either participant to a party which does not satisfy that participant's authentication policy. In particular, the protocol hides what group this participant belongs to. And we say that the secret handshake is unlinkable if instances involving the same participant cannot be detected. We construct the two realizations of unlinkable secret handshake using O(logN) and O( l) exponentiations (and bilinear maps) respectively, where N is the maximum size of a group and l is the length of a group's revocation list. We also construct a linkable secret handshake protocol with O(n) exponentiations in the case when each player is affiliated with n authorities.A Privacy-Preserving Set Intersection protocol is a protocol executed between a sender and a receiver on respective sets of bitstrings X and Y of size N, which lets the receiver compute the intersection of X and Y without revealing anything else. We construct two privacy-preserving set intersection protocols with the computational cost of O(N). |
