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. Informationtheoretic quantitative relaxations of noninterference (based on Shannon entropy)have been introduced to enable more finegrained 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 PSPACEcomplete. 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 EXPTIMEcomplete. 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 EXPTIMEhard.

Conference Title:

CSF: Computer Security Foundations

Conference Location:

Abbaye des Vaux de Cernay, France

ISBN:

10636900

Publisher:

IEEE

Date Published:

20110627

Start Page: 
205

End Page:

217

Sponsor: 
This work was partially supported by the ERC Advanced Grant QUAREM, the FWF NFN Grant S11402N23 and S11407N23 (RiSE), and a Microsoft faculty fellowship.

URL: 

DOI: 
10.1109/CSF.2011.21

Open access: 
yes (repository) 