The complexity of quantitative information flow problems

Cerny P, Chatterjee K, Henzinger TA. 2011. The complexity of quantitative information flow problems. CSF: Computer Security Foundations, 205–217.

Download
OA IST-2012-81-v1+1_The_complexity_of_quantitative_information_flow_problems.pdf 299.07 KB [Submitted Version]

Conference Paper | Published | English

Scopus indexed
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.
Publishing Year
Date Published
2011-06-27
Publisher
IEEE
Page
205 - 217
Conference
CSF: Computer Security Foundations
Conference Location
Cernay-la-Ville, France
Conference Date
2011-06-27 – 2011-06-29
IST-REx-ID

Cite this

Cerny P, Chatterjee K, Henzinger TA. The complexity of quantitative information flow problems. In: IEEE; 2011:205-217. doi:10.1109/CSF.2011.21
Cerny, P., Chatterjee, K., & Henzinger, T. A. (2011). The complexity of quantitative information flow problems (pp. 205–217). Presented at the CSF: Computer Security Foundations, Cernay-la-Ville, France: IEEE. https://doi.org/10.1109/CSF.2011.21
Cerny, Pavol, Krishnendu Chatterjee, and Thomas A Henzinger. “The Complexity of Quantitative Information Flow Problems,” 205–17. IEEE, 2011. https://doi.org/10.1109/CSF.2011.21.
P. Cerny, K. Chatterjee, and T. A. Henzinger, “The complexity of quantitative information flow problems,” presented at the CSF: Computer Security Foundations, Cernay-la-Ville, France, 2011, pp. 205–217.
Cerny P, Chatterjee K, Henzinger TA. 2011. The complexity of quantitative information flow problems. CSF: Computer Security Foundations, 205–217.
Cerny, Pavol, et al. The Complexity of Quantitative Information Flow Problems. IEEE, 2011, pp. 205–17, doi:10.1109/CSF.2011.21.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
1a25be0c62459fc7640db88af08ff63a


Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar