Back to Search
Start Over
Quantitative Information Flow in Boolean Programs.
- Source :
- Principles of Security & Trust: Third International Conference, POST 2014, Held as Part of the European Joint Conferences on Theory & Practice of Software, ETAPS 2014, Grenoble, France, April 5-13, 2014, Proceedings; 2014, p103-119, 17p
- Publication Year :
- 2014
-
Abstract
- The <italic>quantitative information flow bounding problem</italic> asks, given a program <italic>P</italic> and threshold <italic>q</italic>, whether the information leaked by <italic>P</italic> is bounded by <italic>q</italic>. When the amount of information is measured using mutual information, the problem is known to be PSPACE-hard and decidable in EXPTIME. We show that the problem is in fact decidable in PSPACE, thus establishing the exact complexity of the quantitative information flow bounding problem. Thus, the complexity of bounding quantitative information flow in programs has the same complexity as safety verification of programs. We also show that the same bounds apply when comparing information leaked by two programs. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783642547911
- Database :
- Complementary Index
- Journal :
- Principles of Security & Trust: Third International Conference, POST 2014, Held as Part of the European Joint Conferences on Theory & Practice of Software, ETAPS 2014, Grenoble, France, April 5-13, 2014, Proceedings
- Publication Type :
- Book
- Accession number :
- 95553987
- Full Text :
- https://doi.org/10.1007/978-3-642-54792-8_6