||Design and implementation of an algorithmic procedure for synthesis of secure communication protocols for generalized Russian cards problems
||Goranko, Valentin (Algorithms and Logic, Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
||Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
||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.
||Technical University of Denmark (DTU) : Kgs. Lyngby, Denmark
Creation date: 2011-04-04
Update date: 2011-05-18