Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2020 | Book

Introduction Read chapter Read first chapter

The Science of Quantitative Information Flow

Authors: Dr. Mário S. Alvim, Dr. Konstantinos Chatzikokolakis, Prof. Annabelle McIver, Prof. Carroll Morgan, Prof. Catuscia Palamidessi, Prof. Geoffrey Smith

Publisher: Springer International Publishing

Book Series : Information Security and Cryptography

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This book presents a comprehensive mathematical theory that explains precisely what information flow is, how it can be assessed quantitatively – so bringing precise meaning to the intuition that certain information leaks are small enough to be tolerated – and how systems can be constructed that achieve rigorous, quantitative information-flow guarantees in those terms. It addresses the fundamental challenge that functional and practical requirements frequently conflict with the goal of preserving confidentiality, making perfect security unattainable.

Topics include: a systematic presentation of how unwanted information flow, i.e., "leaks", can be quantified in operationally significant ways and then bounded, both with respect to estimated benefit for an attacking adversary and by comparisons between alternative implementations; a detailed study of capacity, refinement, and Dalenius leakage, supporting robust leakage assessments; a unification of information-theoretic channels and information-leaking sequential programs within the same framework; and a collection of case studies, showing how the theory can be applied to interesting realistic scenarios.

The text is unified, self-contained and comprehensive, accessible to students and researchers with some knowledge of discrete probability and undergraduate mathematics, and contains exercises to facilitate its use as a course textbook.

Table of Contents

Frontmatter

Motivation

Frontmatter
Chapter 1. Introduction
Abstract
Protecting sensitive information from improper disclosure or corruption is a longstanding, fundamental goal of computer security: but it is one that is not currently being achieved well at all, as is evident from continual news reports of large-scale data compromises.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith

Secrets and How to Measure Them

Frontmatter
Chapter 2. Modeling secrets
Abstract
We begin our detailed study of quantitative information flow by asking ourselves what a secret really is. There are many non-controversial examples, such as a user’s password, social security number, or current location — but what does it mean for us to treat them as secrets?
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 3. On -vulnerability
Abstract
As we have just seen in Chap. 2, Bayes vulnerability measures one basic threat to a secret X, namely the risk that the adversary could correctly guess it in one try. But of course there are many other operational scenarios that we could be worried about.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith

Channels and Information Leakage

Frontmatter
Chapter 4. Channels
Abstract
We now turn our attention to systems that process secret information. In this part of the book, we model such systems as information-theoretic channels, which are (possibly probabilistic) functions from inputs to outputs.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 5. Posterior vulnerability and leakage
Abstract
We recall from Chap. 3 that, given a secret X with prior distribution π, the “threat” to X can be measured as its g-vulnerability Vg(π) for a suitably chosen gain function g — where the choice of g reflects the circumstances, and the importance to us of the secret’s remaining undisclosed, and might vary depending on who “we” are and what adversary we are facing.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 6. Robustness
Abstract
Given a channel with input X, we have now seen that g-leakage provides us with a rich variety of ways to measure the information leakage of X that the channel causes. The prior models the adversary’s prior knowledge about X; the gain function g models the operational scenario, which encompasses both the set of actions that the adversary can take and also the worth to the adversary of each such action, for each possible value of X; and the choice of multiplicative- or additive leakage allows us to measure either the relative or the absolute increase in g-vulnerability.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 7. Capacity
Abstract
In this chapter we develop the theory of channel capacity.
In Def. 5.11 we considered for a fixed prior π and gain function g the idea of comparing prior and posterior vulnerabilities. As we noted in §6.2 however, in general one cannot be sure of the π’s and g’s our channels might face in practice; and so it is worth asking “What is the worst leakage that we, as defenders, might have to deal with if we use this channel?”
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 8. Composition of channels
Abstract
As we saw in Chap. 6, our framework for quantitative information flow can provide a robust theory for deriving security properties from a system’s representation as a channel, as long as we can determine what that channel is — but determining an appropriate channel to model a system is itself often a non-trivial task.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 9. Refinement
Abstract
As a technical term in Computer Science, “refinement” is understood as a relation between systems (programs, channels. . . ) that, in its most austere form, is simply preservation of properties.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 10. The Dalenius perspective
Abstract
We now consider the possibility that the adversary knows interesting correlations among different secrets, and we study the implications of that for information leakage.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 11. Axiomatics
Abstract
In previous chapters we discussed how secrecy can be quantified: we described information measures that map a prior to a real number reflecting the amount of threat to which the secret is subjected; and we introduced g-vulnerabilities as a rich family of such information measures that can capture a variety of significant operational scenarios.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 12. The geometry of hypers, gains and losses
Abstract
Many of the constructions we have seen so far have a compelling geometric interpretation. Information is not only numbers and formulae — it is also curves and tangents, shapes and planes.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith

Information Leakage in Sequential Programs

Frontmatter
Chapter 13. Quantitative information flow in sequential computer programs
Abstract
Until this point, we have modeled systems as channels: either concretely as matrices of type \(\mathcal{X}\rightarrow\mathcal{Y}\) for some input X and observation Y, or abstractly as functions \(\mathbb{D}\mathcal{X}\rightarrow\mathbb{D}^{2}\mathcal{X}\) on \(\mathcal{X}\) alone.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 14. Hidden-Markov modeling of QIF in sequential programs
Abstract
In the last chapter we made the case for embedding our treatment of QIF, developed in Parts I–III as “channels that leak”, in a programming-language setting.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 15. Program algebra for QIF
Abstract
One of our principal aims in this work is to extend the reliable derivation of implementations from specifications –so long pursued in other areas like functionality, concurrency and probability– to include security as well, and in particular quantitative security.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 16. Iteration and nontermination
Abstract
Iteration in programming-language semantics requires a more sophisticated approach than the other constructs we have seen so far: once loops are introduced, we are forced to describe the meaning of a loop’s failing to terminate, in the most extreme case for example WHILE TRUE DO SKIP.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 17. A demonic lattice of information
Abstract
The “double \(\mathbb{D}\)”, the distribution-of-distributions construction that makes our hyperdistributions, has its origins in an earlier “double \(\mathbb{P}\)” construction where \(\mathbb{P}\) is for powerset — that is, where we doubled over powersets rather than over distributions.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith

Applications

Frontmatter
Chapter 18. The Crowds protocol
Abstract
In this chapter we apply our theory of quantitative information flow to the analysis of the Crowds anonymous-communication protocol.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 19. Timing attacks on blinded and bucketed cryptography
Abstract
In this chapter, we apply the theory of quantitative information flow to the important practical problem of timing attacks on cryptography. In such attacks an adversary observes the amount of time taken by a large number of cryptographic operations, in an effort to discover the secret key being used.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 20. Defense against side channels
Abstract
This chapter, like Chap. 19, considers timing attacks against RSA decryption — but from a different perspective. Recall that in Chap. 19 decryption is treated as a black box protected only by the “external” defenses of blinding and bucketing, and under a weak observational model that allows the adversary to see only the total amount of time required by a decryption, as might be appropriate if the decryption were done remotely.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 21. Multi-party computation: The Three Judges protocol
Abstract
Multi-party computation is the solution to the situation in which two (or more) agents say A,B, · · · have private variables a,b,· · · and wish to calculate a public result x = f(a, b, · · · ) without revealing to any one of them more than is strictly necessary — in this case for example A must learn no more than what it can deduce from its variable a (which it knows anyway) and x (which is in the end known by everyone).
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 22. Voting systems
Abstract
Peaceful transfer of power is a core principle of modern democracies, and electoral commissions in particular must navigate the election process in a scenario where participants don’t trust each other completely (or at all).
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Chapter 23. Differential privacy
Abstract
Statistical databases store the data of a large number of individuals, and data analysts are allowed to pose statistical queries about those data. Typical queries include average values, total counting, or the percentage of the entries that satisfy a given property.
Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, Geoffrey Smith
Backmatter
Metadata
Title
The Science of Quantitative Information Flow
Authors
Dr. Mário S. Alvim
Dr. Konstantinos Chatzikokolakis
Prof. Annabelle McIver
Prof. Carroll Morgan
Prof. Catuscia Palamidessi
Prof. Geoffrey Smith
Copyright Year
2020
Electronic ISBN
978-3-319-96131-6
Print ISBN
978-3-319-96129-3
DOI
https://doi.org/10.1007/978-3-319-96131-6

Premium Partner

    Image Credits