We provide a novel definition of quantitative information flow, called transmissible information, that is suitable for reasoning about informational-theoretically secure (or non-cryptographic) systems, as well as about cryptographic systems with their polynomially bounded adversaries, error probabilities, etc. Transmissible information captures deliberate communication between two processes, and it safely over-approximates the quantity of information that a process unintentionally leaks to another process. We show that transmissible information is preserved under universal composability, which constitutes the prevalent cryptographic notion of a secure implementation. This result enables us to lift quantitative bounds of transmissible information from simple ideal functionalities of cryptographic tasks to actual cryptographic systems. We furthermore prove a connection between transmissible information in the unconditional setting and channel capacity, based on the weak converse of Shannon's coding theorem. This connection enables us to compute an upper bound on the transmissible information for a restricted class of protocols, using existing techniques from quantitative information flow.
We provide a novel definition of quantitative information flow, called transmissible information, that is suitable for reasoning about informational-theoretically secure (or non-cryptographic) systems, as well as about cryptographic systems with their polynomially bounded adversaries, error probabilities, etc. Transmissible information captures deliberate communication between two processes, and it safely over-approximates the quantity of information that a process unintentionally leaks to another process. We show that transmissible information is preserved under universal composability, which constitutes the prevalent cryptographic notion of a secure implementation. This result enables us to lift quantitative bounds of transmissible information from simple ideal functionalities of cryptographic tasks to actual cryptographic systems. We furthermore prove a connection between transmissible information in the unconditional setting and channel capacity, based on the weak converse of Shannon's coding theorem. This connection enables us to compute an upper bound on the transmissible information for a restricted class of protocols, using existing techniques from quantitative information flow.
This thesis presents a formal model for quantum protocols, that is, cryptographic protocols based on quantum mechanics. It also develops a definition of security (which includes notions such as privacy and correctness) for quantum protocols.
First, existing classical (non-quantum) definitions of security are studied. There are essentially two approaches: one based on Turing Machines and simulation, the other using information theory. Both approaches are explored in detail and compared, then a particular variation of the first approach is chosen. Security is defined by introducing an interface (also called a simulator) which is capable of translating an attack on protocol 1 into an attack on protocol 2. The profile of a protocol is a stochastic variable, defined as the output of the participants and the view of the adversary who performs the attack. If an interface exists such that the profile of protocol 1 is indistinguishable from the profile of protocol 2 with the help of this interface, then protocol 1 is at least as secure as protocol 2. An absolute notion of security is obtained by comparing the protocol implementation with its 'ideal' equivalent.
In this approach, and in classical cryptography in general, indistinguishability of probability distributions is a crucial tool. The meaning of this notion is explored in the context of density matrices, the mathematical formalism which is used to describe the state of a quantum system. Various measures of distinguishability of quantum states relevant from a cryptographic point of view are investigated: probability of error, trace norm (related to the Kolmogorov distance), overlap (related to the Bhattacharyya coefficient) and Shannon distinguishability (defined through the mutual information). It is shown that if we require that the distinguishability between two families of quantum states vanish exponentially fast, these four distinguishability measures are equivalent.
Along the way upper and lower bounds for the Shannon distinguishability are obtained. This is a very useful result, because explicit computation of the Shannon distinguishability between two quantum states is often difficult (it requires solving a transcendental equation), whereas the other distinguishability measures, in particular the trace norm, are usually much easier to compute.
In the last chapter the two previous topics are combined. A formal model for quantum protocols is formulated. It uses Quantum Turing Machines to represent the participants, who communicate through a quantum channel. The different nature of quantum information as opposed to classical information is explored in detail, including the implications this has for the definition. As in the classical case, we introduce an interface to compare the security of two protocols for the same task. Subsequently some consequences of the proposed definition are investigated. In particular, strong evidence is given that one classical technique often used in proofs of security for classical protocols, called rewinding, is impossible in the quantum setting.
We propose a novel paradigm for defining security of cryptographic protocols, called universally composable security. The salient property of universally composable definitions of security is that they guarantee security even when a secure protocol is composed of an arbitrary set of protocols, or more generally when the protocol is used as a component of an arbitrary system. This is an essential property for maintaining security of cryptographic protocols in complex and unpredictable environments such as the Internet. In particular, universally composable definitions guarantee security even when an unbounded number of protocol instances are executed concurrently in an adversarially controlled manner, they guarantee non-malleability with respect to arbitrary protocols, and more. We show how to formulate universally composable definitions of security for practically any cryptographic task. Furthermore, we demonstrate that practically any such definition can be realized using known techniques, as long as only a minority of the participants are corrupted. We then proceed to formulate universally composable definitions of a wide array of cryptographic tasks, including authenticated and secure communication, key-exchange, public-key encryption, signature, commitment, oblivious transfer, zero knowledge and more. We also make initial steps towards studying the realizability of the proposed definitions in various settings.
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.
In this paper, we propose a framework of source encryption, where cryptographic processing is applied to a prescribed fixed length source code. The proposed source encryption framework is based on the secure communication framework of the Shannon cipher system. In the proposed framework, we use the mutual information as a measure of information leakage to an adversary. For the proposed framework, we explicitly establish the necessary and sufficient condition for reliable and secure communication under the condition that error probability and information leakage, respectively, are upper bounded by prescribed constants ε∈(0,1) and δ∈(0,∞). We also show that the obtained necessary and sufficient condition does not depend on the constants ε∈(0,1) and δ∈(0,∞), demonstrating that we have the strong converse theorem for the proposed framework of source encryption. We further prove the existence of encryption/decryption schemes, which are universal in the sense that they work effectively for any distributions of the plain text and those of the key used for the encryption.
If we combine two secure cryptographic systems, is the resulting system still secure?Answering this question is highly nontrivial and has recently sparked a considerable research effort, in particular, in the area of classical cryptography.A central insight was that the answer to the question is yes, but only within a well-specified composability framework and for carefully chosen security definitions.In this article, we review several aspects of composability in the context of quantum cryptography.The first part is devoted to key distribution.We discuss the security criteria that a quantum key distribution (QKD) protocol must fulfill to allow its safe use within a larger security application (e.g. for secure message transmission); and we demonstrate-by an explicit example-what can go wrong if conventional (non-composable) security definitions are used.Finally, to illustrate the practical use of composability, we show how to generate a continuous key stream by sequentially composing rounds of a QKD protocol.In the second part, we take a more general point of view, which is necessary for the study of cryptographic situations involving, for example, mutually distrustful parties.We explain the universal composability (UC) framework and state the composition theorem that guarantees that secure protocols can securely be composed to larger applications.We focus on the secure composition of quantum protocols into unconditionally secure classical protocols.However, the resulting security definition is so strict that some tasks become impossible without additional security assumptions.Quantum bit commitment is impossible in the UC framework even with mere computational security.Similar problems arise in the quantum bounded storage model and we observe a trade-off between the UC and the use of the weakest possible security assumptions.
The field of quantitative information flow (QIF) is concerned with measuring and controlling information leakage in computational systems, aiming to assess and improve their security. Much effort has been put into developing a mathematical framework for QIF, the standard approach being to model systems as monolithic infomation theoretic channels. However, many real-life systems can be best described by a collection of interacting channels instead. This motivates us to investigate the behaviour of channel compositions under the QIF framework. The channel compositions we study capture typical ways in which parts interact in real-world systems. Among other results, we derive relations between the information leakage of compositions and that of their components, establish whether we may substitute a component with a safer one without compromising the security of the whole, and model two anonymity protocols from the literature: the Dining Cryptographers and the Crowds.