Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Quantifying information flow in interactive systems
Mestel, David
2019In 2019 IEEE 32nd Computer Security Foundations Symposium (CSF)
Peer reviewed


Full Text
Author postprint (303.52 kB)

All documents in ORBilu are protected by a user license.

Send to


Abstract :
[en] We consider the problem of quantifying information flow in interactive systems, modelled as finite-state transducers in the style of Goguen and Meseguer. Our main result is that if the system is deterministic then the information flow is either logarithmic or linear, and there is a polynomial-time algorithm to distinguish the two cases and compute the rate of logarithmic flow. To achieve this we first extend the theory of information leakage through channels to the case of interactive systems, and establish a number of results which greatly simplify computation. We then show that for deterministic systems the information flow corresponds to the growth rate of antichains inside a certain regular language, a property called the width of the language. In a companion work we have shown that there is a dichotomy between polynomial and exponential antichain growth, and a polynomial time algorithm to distinguish the two cases and to compute the order of polynomial growth. We observe that these two cases correspond to logarithmic and linear information flow respectively. Finally, we formulate several attractive open problems, covering the cases of probabilistic systems, systems with more than two users and nondeterministic systems where the nondeterminism is assumed to be innocent rather than demonic.
Disciplines :
Computer science
Author, co-author :
Mestel, David ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
External co-authors :
Language :
Title :
Quantifying information flow in interactive systems
Publication date :
Event name :
32nd IEEE Symposium on Computer Security Foundations (CSF 2019)
Event organizer :
Institute of Electrical and Electronics Engineers
Event place :
Hoboken, United States - New Jersey
Event date :
from 25-6-2019 to 28-6-2019
Main work title :
2019 IEEE 32nd Computer Security Foundations Symposium (CSF)
Peer reviewed :
Peer reviewed
FnR Project :
FNR11689058 - Quantum Communication With Deniability, 2017 (01/07/2018-30/06/2021) - Peter Y. A. Ryan
Funders :
FNR - Fonds National de la Recherche [LU]
Available on ORBilu :
since 15 May 2019


Number of views
131 (10 by Unilu)
Number of downloads
56 (2 by Unilu)

Scopus citations®
Scopus citations®
without self-citations


Similar publications

Contact ORBilu