License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.16
URN: urn:nbn:de:0030-drops-185504
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18550/
Go to the corresponding LIPIcs Volume Portal

Balun, Jiří ; Masopust, Tomáš ; Osička, Petr

Speed Me up If You Can: Conditional Lower Bounds on Opacity Verification

pdf-format:
LIPIcs-MFCS-2023-16.pdf (1.0 MB)

Abstract

Opacity is a property of privacy and security applications asking whether, given a system model, a passive intruder that makes online observations of system’s behaviour can ascertain some "secret" information of the system. Deciding opacity is a PSpace-complete problem, and hence there are no polynomial-time algorithms to verify opacity under the assumption that PSpace differs from PTime. This assumption, however, gives rise to a question whether the existing exponential-time algorithms are the best possible or whether there are faster, sub-exponential-time algorithms. We show that under the (Strong) Exponential Time Hypothesis, there are no algorithms that would be significantly faster than the existing algorithms. As a by-product, we obtained a new conditional lower bound on the time complexity of deciding universality (and therefore also inclusion and equivalence) for nondeterministic finite automata.

BibTeX - Entry

@InProceedings{balun_et_al:LIPIcs.MFCS.2023.16,
  author =	{Balun, Ji\v{r}{\'\i} and Masopust, Tom\'{a}\v{s} and Osi\v{c}ka, Petr},
  title =	{{Speed Me up If You Can: Conditional Lower Bounds on Opacity Verification}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18550},
  URN =		{urn:nbn:de:0030-drops-185504},
  doi =		{10.4230/LIPIcs.MFCS.2023.16},
  annote =	{Keywords: Finite automata, opacity, fine-grained complexity}
}

Keywords: Finite automata, opacity, fine-grained complexity
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI