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

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989592%3A15310%2F23%3A73620789" target="_blank" >RIV/61989592:15310/23:73620789 - isvavai.cz</a>
Result on the web
<a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.16" target="_blank" >https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.16</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPICS.MFCS.2023.16" target="_blank" >10.4230/LIPICS.MFCS.2023.16</a>

Result language
angličtina
Original language name
Speed Me up If You Can: Conditional Lower Bounds on Opacity Verification
Original language description
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.
Czech name
—
Czech description
—

Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
ISBN
978-3-95977-292-1
ISSN
—
e-ISSN
—
Number of pages
15
Pages from-to
"16-1"-"16-15"
Publisher name
Schloss-Dagstuhl - Leibniz Zentrum für Informatik
Place of publication
Schloss-Dagstuhl, Leibniz Zentrum für Informatik
Event location
Bordeaux
Event date
Aug 28, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)