The Complexity of Quantitative Information Flow in Recursive Programs

Rohit ChadhaRohit Chadha, Michael UmmelsMichael Ummels

DOI Link

Rohit Chadha, Michael Ummels
The Complexity of Quantitative Information Flow in Recursive Programs
Proc. of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 18 of Leibniz International Proceedings in Informatics, 534--545, 2012. Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Details
Bibtex

KurzfassungAbstract
Information-theoretic measures based upon mutual information can be employed to quantify the information that an execution of a program reveals about its secret inputs. The information leakage bounding problem asks whether the information leaked by a program does not exceed a given threshold. We consider this problem for two scenarios: a) the outputs of the program are revealed, and b)the timing (measured in the number of execution steps) of the program is revealed. For both scenarios, we establish complexity results in the context of deterministic boolean programs, both for programs with and without recursion. In particular, we prove that for recursive programs the information leakage bounding problem is no harder than checking reachability.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@inproceedings{CU2012,
  author    = {Rohit Chadha and Michael Ummels},
  title     = {The Complexity of Quantitative Information Flow in Recursive
               Programs},
  booktitle = {Proc. of the {IARCS} Annual Conference on Foundations of Software
               Technology and Theoretical Computer Science (FSTTCS)},
  series    = {Leibniz International Proceedings in Informatics},
  volume    = {18},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2012},
  pages     = {534--545},
  doi       = {10.4230/LIPIcs.FSTTCS.2012.534}
}