2023/04/19 by Jiří Balun, Balun, Jiří, Tomáš Masopust +3
Computer Science · #Cryptography and Data Security #Distributed systems and fault tolerance #FOS: Computer and information sciences #FOS: Electrical engineering #Formal Languages and Automata Theory (cs.FL) #Systems and Control (eess.SY) #electronic engineering #information engineering #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2304.09920
openalex publication_date 2023/04/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.