The complexity of quantitative information flow problems Conference Paper


Author(s): Cerný, Pavol; Chatterjee, Krishnendu; Henzinger, Thomas A
Title: The complexity of quantitative information flow problems
Affiliation IST Austria
Abstract: In this paper, we investigate the computational complexity of quantitative information flow (QIF) problems. Information-theoretic quantitative relaxations of noninterference (based on Shannon entropy)have been introduced to enable more fine-grained reasoning about programs in situations where limited information flow is acceptable. The QIF bounding problem asks whether the information flow in a given program is bounded by a constant $d$. Our first result is that the QIF bounding problem is PSPACE-complete. The QIF memoryless synthesis problem asks whether it is possible to resolve nondeterministic choices in a given partial program in such a way that in the resulting deterministic program, the quantitative information flow is bounded by a given constant $d$. Our second result is that the QIF memoryless synthesis problem is also EXPTIME-complete. The QIF memoryless synthesis problem generalizes to QIF general synthesis problem which does not impose the memoryless requirement (that is, by allowing the synthesized program to have more variables then the original partial program). Our third result is that the QIF general synthesis problem is EXPTIME-hard.
Conference Title: CSF: Computer Security Foundations
Conference Location: Abbaye des Vaux de Cernay, France
ISBN: 1063-6900
Publisher: IEEE  
Date Published: 2011-06-27
Start Page: 205
End Page: 217
Sponsor: This work was partially supported by the ERC Advanced Grant QUAREM, the FWF NFN Grant S11402-N23 and S11407-N23 (RiSE), and a Microsoft faculty fellowship.
URL:
DOI: 10.1109/CSF.2011.21
Open access: yes (repository)