Cryptographic Protocols:: Theory and Implementation
Martin Geisler · 2010
The art of keeping messages secret is ancient. It must have been invented only shortly after the invention of the messages themselves. Merchants and generals have always had a need to exchange critical messages while keeping them secret from the prying eyes of competitors or the enemy. Classical cryptography was thus concerned with message confidentiality and integrity. Modern cryptography cover a much wider range of subjects including the area of secure multiparty computation, which will be the main topic of this dissertation. Our first contribution is a new protocol for secure comparison, presented in Chapter 2. Comparisons play a key role in many systems such as online auctions and benchmarks — it is not unreasonable to say that when parties come together for a multiparty computation, it is because they want to make decisions that depend on private information. Decisions depend on comparisons. We have implemented the comparison protocol in Java and benchmarks show that is it highly competitive and practical. The biggest contribution of this dissertation is a general framework for secure multiparty computation. Instead of making new ad hoc implementations for each protocol, we want a single and extensible framework. We call this framework VIFF, short for Virtual Ideal Functionality Framework. VIFF implements a UC functionality for general multiparty computation on asynchronous networks. We give a formal definition of the functionality in Chapter 3. There we also describe how we implemented the functionality with a variant of the classic BGW protocol. The protocol is secure against a semi-honest adversary. In Chapter 4 we describe a new protocol for VIFF that is secure against malicious adversaries. The protocol guarantees termination if the adversary allows a preprocessing phase to terminate, in which no information is released. The communication complexity of this protocol is the same as that of a passively secure solution up to a constant factor. It is secure against an adaptive and active adversary corrupting less than n=3 players. Following the presentation of VIFF, we turn to a more theoretical subject. Chapter 5 investigates the notion of a covert adversary — an adversary type that intuitively lies in between semi-honest and malicious adversaries. The main idea is that we accept that a cheating adversary may succeed with a given probability, which need not be negligible. The reasoning is that in many real-world cases, a large probability of being caught is sufficient to prevent the adversary from trying to cheat. We show how to compile a passively secure protocol for honest majority into a protocol that is secure against covert attacks, again for honest majority. The transformed protocol catches cheating with probability 1/4 . Though we present no implementation of this compiler, we believe it will be very efficient and practical to implement using, say, VIFF. The cost of the modified protocol is essentially twice that of the original plus an overhead that only depends on the number of inputs. We round off this dissertation with Chapter 6. There we return to the practical side of things and consider how users of online collaboration tools and network storage services place considerable trust in their providers. We presents a novel approach for protecting data integrity in revision control systems hosted by an untrusted provider. It guarantees atomic read and write operations on the shared data when the service is correct and preserves fork-linearizability when the service is faulty. A prototype has been implemented on top of the Subversion revision control system; benchmarks show that the approach is practical.