Dissertation

Algebraic techniques for low communication secure protocols

Promotor: R. Cramer

Author: Robbert de Haan
Date: 11 March 2009
Links: Thesis in Leiden Repository

This thesis discusses new results in two areas within cryptography; securely transmitting a message between two parties and securely computing a function on the inputs of multiple parties. For both of these areas we mainly consider perfectly secure protocols, which are protocols that have a zero error probability and that do not rely on any number-theoretical assumptions for their security or correctness. For the first area, we in this thesis give an overview of all results on perfectly secure message transmission in the commonly used model and furthermore determine the exact achievable communication complexity under the weakest possible assumption in this model. For the second area, which is commonly referred to as secure multi-party computation, we introduce new techniques that allow to drastically reduce the required communication for perfectly secure multi-party computations and establish new connections with coding theory and algebraic geometry.