The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Cryptographic Protocol Design

Sven Laur

Dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Faculty of Information and Natural Sciences for public examination and debate in Auditorium T2 at Helsinki University of Technology (Espoo, Finland) on the 25th of April, 2008, at 12 noon.

Overview in PDF format (ISBN 978-951-22-9293-6)   [1541 KB]
Dissertation is also available in print (ISBN 978-951-22-9292-9)

Abstract

In this work, we investigate the security of interactive computations. The main emphasis is on the mathematical methodology that is needed to formalise and analyse various security properties. Differently from many classical treatments of secure multi-party computations, we always quantify security in exact terms. Although working with concrete time bounds and success probabilities is technically more demanding, it also has several advantages. As all security guarantees are quantitative, we can always compare different protocol designs. Moreover, these security guarantees also have a clear economical interpretation and it is possible to compare cryptographic and non-cryptographic solutions. The latter is extremely important in practice, since cryptographic techniques are just one possibility to achieve practical security. Also, working with exact bounds makes reasoning errors more apparent, as security proofs are less abstract and it is easier to locate false claims.

The choice of topics covered in this thesis was guided by two principles. Firstly, we wanted to give a coherent overview of the secure multi-party computation that is based on exact quantification of security guarantees. Secondly, we focused on topics that emerged from the author's own research. In that sense, the thesis generalises many methodological discoveries made by the author.

As surprising as it may seem, security definitions and proofs mostly utilise principles of hypothesis testing and analysis of stochastic algorithms. Thus, we start our treatment with hypothesis testing and its generalisations. In particular, we show how to quantify various security properties, using security games as tools. Next, we review basic proof techniques and explain how to structure complex proofs so they become easily verifiable. In a nutshell, we describe how to represent a proof as a game tree, where each edge corresponds to an elementary proof step. As a result, one can first verify the overall structure of a proof by looking at the syntactic changes in the game tree and only then verify all individual proof steps corresponding to the edges.

The remaining part of the thesis is dedicated to various aspects of protocol design. Firstly, we discuss how to formalise various security goals, such as input-privacy, output-consistency and complete security, and how to choose a security goal that is appropriate for a specific setting. Secondly, we also explore alternatives to exact security. More precisely, we analyse connections between exact and asymptotic security models and rigorously formalise a notion of subjective security. Thirdly, we study in which conditions protocols preserve their security guarantees and how to safely combine several protocols. Although composability results are common knowledge, we look at them from a slightly different angle. Namely, it is irrational to design universally composable protocols at any cost; instead, we should design computationally efficient protocols with minimal usage restrictions. Thus, we propose a three-stage design procedure that leads to modular security proofs and minimises usage restrictions.

This thesis consists of an overview and of the following 4 publications:

  1. Bart Goethals, Sven Laur, Helger Lipmaa, and Taneli Mielikäinen. 2004. On private scalar product computation for privacy-preserving data mining. In: Choonsik Park and Seongtaek Chee, editors. Revised Selected Papers of the 7th International Conference on Information Security and Cryptology (ICISC 2004). Seoul, Korea, 2-3 December 2004. Lecture Notes in Computer Science, volume 3506, pages 104-120. © 2004 by authors and © 2004 Springer Science+Business Media. By permission.
  2. Sven Laur and Helger Lipmaa. 2007. A new protocol for conditional disclosure of secrets and its applications. In: Jonathan Katz and Moti Yung, editors. Proceedings of the 5th International Conference on Applied Cryptography and Network Security (ACNS 2007). Zhuhai, China, 5-8 June 2007. Lecture Notes in Computer Science, volume 4521, pages 207-225. © 2007 by authors and © 2007 Springer Science+Business Media. By permission.
  3. Ahto Buldas and Sven Laur. 2007. Knowledge-binding commitments with applications in time-stamping. In: Tatsuaki Okamoto and Xiaoyun Wang, editors. Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography (PKC 2007). Beijing, China, 16-20 April 2007. Lecture Notes in Computer Science, volume 4450, pages 150-165. © 2007 by authors and © 2007 Springer Science+Business Media. By permission.
  4. Sven Laur and Kaisa Nyberg. 2006. Efficient mutual data authentication using manually authenticated strings. In: David Pointceval, Yi Mu, and Kefei Chen, editors. Proceedings of the 5th International Conference on Cryptology and Network Security (CANS 2006). Suzhou, China, 8-10 December 2006. Lecture Notes in Computer Science, volume 4301, pages 90-107. © 2006 by authors and © 2006 Springer Science+Business Media. By permission.

Keywords: asymptotic security, data authentication, exact security, homomorphic encryption, secure multi-party computation, sequential composability, subjective security, time-stamping, universal composability

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2008 Helsinki University of Technology

Last update 2011-05-26