Privacy-Preserving Protocols with Oblivious Transfer and Mix Networks

Abstract

We propose and analyze security protocols to safeguard user privacy. We use oblivioustransfer (OT) as the main cryptographic primitive---and mix network architecture---to design two protocols: 1) BVOT, a boardroom voting protocol with ballot secrecy using OT, and 2) AOT, an anonymous communication protocol using OT. We also analyze and improve cMix, an anonymous communication system with precomputation. Our first protocol, BVOT, uses OT to facilitate boardroom voting, an election with a smallnumber of voters. BVOT provides perfect ballot secrecy: unless all the voters conspire against one voter, none of the voters nor any external party can learn how voters cast their votes. Voters hide their votes before casting them, without the need to provide any proof for correctness of their vote. This property is a significant improvement as existing voting protocols with vote hiding property require the voters to provide zero-knowledge proofs for correctness of their vote and check zero-knowledge proofs provided by other voters to verify correctness of their votes. Our protocol is self tallying: after votes are cast, any of the voters can tally the votes. Our protocol is fair: none of the voters can compute the tally before casting their vote. Our protocol supports elections with any number of candidates. Our second protocol, AOT, provides anonymous two-way communications using OT. As the maincryptographic primitive in AOT, OT delivers messages to recipients anonymously. To our knowledge, AOT is the first protocol that uses OT to facilitate anonymous communication. Users of AOT do not have to register with the system; any entity who knows the public key of any middle-layer node in the system can send messages with AOT. AOT does not need the address of the recipient of a message to deliver the message. AOT does not learn any information about the recipient of a message, nor does it learn if a message has been delivered. AOT provides receiver anonymity---an adversary cannot distinguish who received the message from among all users receiving some message---even if the covert adversary controls all nodes in AOT. Next we briefly overview and analyze the performance of cMix, an anonymous communicationprotocol that does not perform any public-key operation during run-time. The author of this dissertations is a member of the team that engineered, implemented, and analyzed cMix. The author's main contributions to the cMix project are the formal description of the protocol, performance analysis, and implementation of cMix. cMix, a mix network with a fixed cascade architecture, uses multi-party group homomorphicencryption to create a shared secret in the precomputation phase and uses this shared secret to eliminate the need for computationally expensive public-key operations during run-time. cMix is distinct from previous precomputation based mixnets in that it completely eliminates public-key operations, both on the client and server sides. The original cMix protocol does not resist active blending attacks. We propose two techniques to make cMix resistant to blending attacks, one of which requires only one honest mixnode.