Skip to main content
Top
Published in:
Cover of the book

2018 | OriginalPaper | Chapter

On the Additive Capacity Problem for Quantitative Information Flow

Author : Konstantinos Chatzikokolakis

Published in: Quantitative Evaluation of Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Preventing information leakage is a fundamental goal in achieving confidentiality. In many practical scenarios, however, eliminating such leaks is impossible. It becomes then desirable to quantify the severity of such leaks and establish bounds on the threat they impose. Aiming at developing measures that are robust wrt a variety of operational conditions, a theory of channel capacity for the g-leakage model was developed in [1], providing solutions for several scenarios in both the multiplicative and the additive setting.
This paper continuous this line of work by providing substantial improvements over the results of [1] for additive leakage. The main idea of employing the Kantorovich distance remains, but it is now applied to quasimetrics, and in particular the novel “convex-separation” quasimetric. The benefits are threefold: first, it allows to maximize leakage over a larger class of gain functions, most notably including the one of Shannon. Second, a solution is obtained to the problem of maximizing leakage over both priors and gain functions, left open in [1]. Third, it allows to establish an additive variant of the “Miracle” theorem from [3].

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
The notation is due to the fact that distributions can be convexly combined (\({\mathbb D}\mathcal {A}\) is a vector space). \(\sum _y a_y [\delta ^y]\) is exactly the hyper assigning probability \(a_y\) to each \(\delta ^y\).
 
2
Which is why we generally refer to the maximization of leakage as “capacity”.
 
3
The same phenomenon happens for multiplicative leakage, this time demonstrated by shifting. To keep \(\mathcal {ML}^{\times }_{\mathcal {G}}(\pi ,C)\) bounded we can restrict to the class \({\mathbb G}^{+}{\mathcal{X}}\) of non-negative gain functions.
 
4
The choice \(\mathcal{W}= \mathcal{X}\mathbin {\rightarrow }\{-1,1\}\), \(g(w,x) = \frac{1}{2}\big ( w(x) - \mathcal{E}_{\pi }{w} \big )\) is also capacity-realizing [1].
 
Literature
1.
go back to reference Alvim, M.S., Chatzikokolakis, K., McIver, A., Morgan, C., Palamidessi, C., Smith, G.: Additive and multiplicative notions of leakage, and their capacities. In: Proceedings of CSF, pp. 308–322. IEEE (2014) Alvim, M.S., Chatzikokolakis, K., McIver, A., Morgan, C., Palamidessi, C., Smith, G.: Additive and multiplicative notions of leakage, and their capacities. In: Proceedings of CSF, pp. 308–322. IEEE (2014)
2.
go back to reference Alvim, M.S., Chatzikokolakis, K., McIver, A., Morgan, C., Palamidessi, C., Smith, G.: Axioms for information leakage. In: Proceedings of CSF, pp. 77–92 (2016) Alvim, M.S., Chatzikokolakis, K., McIver, A., Morgan, C., Palamidessi, C., Smith, G.: Axioms for information leakage. In: Proceedings of CSF, pp. 77–92 (2016)
3.
go back to reference Alvim, M.S., Chatzikokolakis, K., Palamidessi, C., Smith, G.: Measuring information leakage using generalized gain functions. In: Proceedings of CSF, pp. 265–279 (2012) Alvim, M.S., Chatzikokolakis, K., Palamidessi, C., Smith, G.: Measuring information leakage using generalized gain functions. In: Proceedings of CSF, pp. 265–279 (2012)
4.
go back to reference Antonopoulos, T., Gazzillo, P., Hicks, M., Koskinen, E., Terauchi, T., Wei, S.: Decomposition instead of self-composition for proving the absence of timing channels. In: PLDI, pp. 362–375. ACM (2017) Antonopoulos, T., Gazzillo, P., Hicks, M., Koskinen, E., Terauchi, T., Wei, S.: Decomposition instead of self-composition for proving the absence of timing channels. In: PLDI, pp. 362–375. ACM (2017)
5.
go back to reference Backes, M., Köpf, B., Rybalchenko, A.: Automatic discovery and quantification of information leaks. In: Proceedings of S&P, pp. 141–153 (2009) Backes, M., Köpf, B., Rybalchenko, A.: Automatic discovery and quantification of information leaks. In: Proceedings of S&P, pp. 141–153 (2009)
6.
go back to reference Barthe, G., Köpf, B.: Information-theoretic bounds for differentially private mechanisms. In: Proceedings of CSF, pp. 191–204 (2011) Barthe, G., Köpf, B.: Information-theoretic bounds for differentially private mechanisms. In: Proceedings of CSF, pp. 191–204 (2011)
9.
go back to reference Braun, C., Chatzikokolakis, K., Palamidessi, C.: Quantitative notions of leakage for one-try attacks. In: Proceedings of MFPS, ENTCS, vol. 249, pp. 75–91. Elsevier (2009) Braun, C., Chatzikokolakis, K., Palamidessi, C.: Quantitative notions of leakage for one-try attacks. In: Proceedings of MFPS, ENTCS, vol. 249, pp. 75–91. Elsevier (2009)
11.
go back to reference Chatzikokolakis, K., Palamidessi, C., Panangaden, P.: On the Bayes risk in information-hiding protocols. J. Comp. Secur. 16(5), 531–571 (2008)CrossRef Chatzikokolakis, K., Palamidessi, C., Panangaden, P.: On the Bayes risk in information-hiding protocols. J. Comp. Secur. 16(5), 531–571 (2008)CrossRef
12.
go back to reference Clarkson, M.R., Schneider, F.B.: Quantification of integrity. In: Proceedings of CSF, pp. 28–43 (2010) Clarkson, M.R., Schneider, F.B.: Quantification of integrity. In: Proceedings of CSF, pp. 28–43 (2010)
13.
go back to reference Cover, T.M., Thomas, J.A.: Elements of Information Theory, 2nd edn. Wiley, Hoboken (2006)MATH Cover, T.M., Thomas, J.A.: Elements of Information Theory, 2nd edn. Wiley, Hoboken (2006)MATH
14.
go back to reference Doychev, G., Köpf, B.: Rigorous analysis of software countermeasures against cache attacks. In: PLDI, pp. 406–421. ACM (2017) Doychev, G., Köpf, B.: Rigorous analysis of software countermeasures against cache attacks. In: PLDI, pp. 406–421. ACM (2017)
15.
go back to reference Heusser, J., Malacaria, P.: Quantifying information leaks in software. In: Proceedings ACSAC 2010, pp. 261–269 (2010) Heusser, J., Malacaria, P.: Quantifying information leaks in software. In: Proceedings ACSAC 2010, pp. 261–269 (2010)
16.
go back to reference Khouzani, M.H.R., Malacaria, P.: Relative perfect secrecy: universally optimal strategies and channel design. In: Proceedings of CSF, pp. 61–76 (2016) Khouzani, M.H.R., Malacaria, P.: Relative perfect secrecy: universally optimal strategies and channel design. In: Proceedings of CSF, pp. 61–76 (2016)
17.
go back to reference Köpf, B., Basin, D.: An information-theoretic model for adaptive side-channel attacks. In: Proceedings of CCS, pp. 286–296 (2007) Köpf, B., Basin, D.: An information-theoretic model for adaptive side-channel attacks. In: Proceedings of CCS, pp. 286–296 (2007)
19.
go back to reference Köpf, B., Rybalchenko, A.: Approximation and randomization for quantitative information-flow analysis. In: Proceedings of CSF, pp. 3–14 (2010) Köpf, B., Rybalchenko, A.: Approximation and randomization for quantitative information-flow analysis. In: Proceedings of CSF, pp. 3–14 (2010)
20.
go back to reference Köpf, B., Smith, G.: Vulnerability bounds and leakage resilience of blinded cryptography under timing attacks. In: Proceedings of CSF, pp. 44–56 (2010) Köpf, B., Smith, G.: Vulnerability bounds and leakage resilience of blinded cryptography under timing attacks. In: Proceedings of CSF, pp. 44–56 (2010)
21.
go back to reference Malacaria, P.: Assessing security threats of looping constructs. In: Proceedings of POPL, pp. 225–235 (2007) Malacaria, P.: Assessing security threats of looping constructs. In: Proceedings of POPL, pp. 225–235 (2007)
22.
23.
go back to reference Meng, Z., Smith, G.: Calculating bounds on information leakage using two-bit patterns. In: Proceedings of PLAS, pp. 1:1–1:12 (2011) Meng, Z., Smith, G.: Calculating bounds on information leakage using two-bit patterns. In: Proceedings of PLAS, pp. 1:1–1:12 (2011)
26.
go back to reference Villani, C.: Topics in Optimal Transportation. No. 58, American Mathematical Society (2003) Villani, C.: Topics in Optimal Transportation. No. 58, American Mathematical Society (2003)
27.
go back to reference Yasuoka, H., Terauchi, T.: Quantitative information flow – verification hardness and possibilities. In: Proceedings of CSF, pp. 15–27 (2010) Yasuoka, H., Terauchi, T.: Quantitative information flow – verification hardness and possibilities. In: Proceedings of CSF, pp. 15–27 (2010)
Metadata
Title
On the Additive Capacity Problem for Quantitative Information Flow
Author
Konstantinos Chatzikokolakis
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-99154-2_1

Premium Partner