This thesis is about approximate guarantees of security via probabilistic checking. Whereas security in cryptography is usually defined as a probability of failure exponentially small in the security parameter, we identify applications where higher rates of failure can be tolerated and where the use of probabilistic checking leads to significant gains in protocol efficiency.; The first part of this thesis is devoted to mix networks. A mix network is a cryptographic protocol used to ensure privacy in applications such as anonymous communication or anonymous voting. We present a new mix network protocol based on probabilistic checking that is extremely efficient and offers a guarantee of “almost entirely correct” mixing. This guarantee, while weaker than perfect correctness, is nevertheless adequate for all but the closest of elections. We introduce next a new type of key-less mix network architecture, called universal mix network, that dispenses with the cumbersome key management necessary in traditional mix networks. We propose finally a practical protocol for reusable anonymous return channels, which enables a player to reply multiple times to an anonymous message without learning the identity of the sender of that message.; In the second part of this thesis, we apply probabilistic checking techniques to secure large-scale computations distributed over the Internet from cheating by untrusted participants. We show that probabilistic checking, combined with arguments from game-theory, offers excellent guarantees of approximate security with minimal overhead.
展开▼
