Beta 1


Title Design and implementation of an algorithmic procedure for synthesis of secure communication protocols for generalized Russian cards problems
Author Huo, Nan
Supervisor Goranko, Valentin (Algorithms and Logic, Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2011
Abstract Modern cryptography are based on the high complexity of computing certain mathematical functions and this kind of communication protocols is called conditional secure. Unconditional security can be obtained by information exchange among the communicating parties. The Russian cards problem is investigated with the intention of developing unconditional secure protocols. This master thesis investigated the generalized Russian cards problem in the sense that the numbers of cards the players hold separately are not restrained. Work that has been done on the Russian cards problem focuses on the approach of using theoretical combinatorial analysis. This work tries to address the problem not only from theoretical perspective but also by developing a working system to practically compute solutions. The problem is analyzed and modeled using epistemic logic with update semantics. Properties of a solution are summarized as information requirement and safety requirement and these requirements are specified as epistemic properties on the model during a run of a protocol. The requirements are further analyzed for protocols that finish in two rounds which means one player makes the first announcement and the other one will learn the deal and announce the adversary's cards. Some propositions about the requirements and the bounds of sizes for good protocols are proved. An algorithm using the technique of local search and heuristics is designed and implemented in Haskell. Three different heuristic functions are developed to guide the local search.
Imprint Technical University of Denmark (DTU) : Kgs. Lyngby, Denmark
Series IMM-M.Sc.-2011-20
Admin Creation date: 2011-04-04    Update date: 2011-05-18    Source: dtu    ID: 275890    Original MXD