- Max Bannach, Sebastian Berndt:
Practical Access to Dynamic Programming on Tree Decompositions.
In Proceedings of the 26th Annual European Symposium on Algorithms, LIPIcs,
2018.
Go to website | Show PDF | Show abstract
Parameterized complexity theory has lead to a wide range of algorithmic
breakthroughs within the last decades, but the practicability of these
methods for real-world problems is still not well understood. We investigate the practicability of one
of the fundamental approaches of this field: dynamic programming on tree
decompositions. Indisputably, this is a key technique in parameterized
algorithms and modern algorithm design. Despite the enormous impact of this
approach in theory, it still has very little influence on practical
implementations. The reasons for this phenomenon are manifold. One of them is
the simple fact that such an implementation requires a long chain of
non-trivial tasks (as computing the decomposition, preparing
it,\dots). We provide an easy way to implement such dynamic programs that only
requires the definition of the update rules.
With this interface, dynamic programs for
various problems, such as \Lang{3-coloring}, can be implemented easily in
about 100 lines of structured Java code.
The theoretical foundation of the success of dynamic programming on tree
decompositions is well understood due to Courcelle's celebrated theorem, which
states that every \textsc{MSO}-definable problem can be efficiently solved if
a tree decomposition of small width is given. We seek to provide practical
access to this theorem as well, by presenting a lightweight model-checker for
a small fragment of \textsc{MSO}. This fragment is powerful enough to
describe many natural problems, and our model-checker turns out to be very
competitive against similar state-of-the-art tools.
- Max Bannach, Sebastian Berndt, Thorsten Ehlers, Dirk Nowotka:
SAT-Encodings of Tree Decompositions.
In Proceedings of SAT Competition 2018: Solver and Benchmark Descriptions, ,
2018.
Go to website | Show abstract
We suggest some benchmarks based on a propositional encoding of tree decompositions of graphs.
- Sebastian Berndt, Maciej Liskiewicz:
On the Gold Standard for Security of Universal Steganography.
In Proc. Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Volume vol. 10820 of LNCS, pp. 29-60.
Springer,
2018.
Go to website | Show abstract
While symmetric-key steganography is quite well understood both in the
information-theoretic and in the computational setting, many fundamental
questions about its public-key counterpart resist persistent attempts to solve
them. The computational model for public-key steganography was proposed by von
Ahn and Hopper in EUROCRYPT 2004. At TCC 2005, Backes and Cachin gave the
first universal public-key stegosystem - i.e. one that works on all
channels - achieving security against replayable chosen-covertext attacks
(SS-RCCA) and asked whether security against non-replayable
chosen-covertext attacks (SS-CCA) is achievable. Later, Hopper
(ICALP 2005) provided such a stegosystem for every efficiently sampleable
channel, but did not achieve universality. He posed the question whether
universality and SS-CCA-security can be achieved simultaneously.
No progress on this question has been achieved since more than a decade. In
our work we solve Hopper's problem in a somehow complete manner: As our main
positive result we design an SS-CCA-secure stegosystem that works for
every memoryless channel. On the other hand, we prove that this result
is the best possible in the context of universal steganography. We provide a
family of 0-memoryless channels - where the already sent documents
have only marginal influence on the current distribution - and prove that no
SS-CCA-secure steganography for this family exists in the standard
non-look-ahead model.
- Sebastian Berndt, Maciej Liskiewicz:
On the Gold Standard for Security of Universal Steganography.
Technical report 106,
IACR Cryptology ePrint Archive,
2018.
Go to website
- Max Bannach, Sebastian Berndt, Thorsten Ehlers:
Jdrasil: A Modular Library for Computing Tree Decompositions.
In International Symposium on Experimental Algorithms (SEA 2017), Volume 75 of LIPIcs, pp. 28:1--28:21.
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
2017.
Go to website | Show PDF | Show abstract
While the theoretical aspects concerning the computation of tree
width - one of the most important graph parameters - are well
understood, it is not clear how it can be computed
practically.We present the open source Java library
Jdrasil that implements several different state of the art
algorithms for this task. By experimentally comparing these
algorithms, we show that the default choices made in Jdrasil
lead to an competitive implementation (it took the third place in the
first PACE challenge) while also being easy to use and easy to extend.
- Sebastian Berndt, Maciej Liskiewicz:
Algorithm Substitution Attacks from a Steganographic Perspective.
In Proc. 24th ACM Conference on Computer and Communications Security (CCS 2017), pp. 1649-1660.
ACM Press,
2017.
Go to website | Show abstract
The goal of an algorithm-substitution attack (ASA), also called a
subversion attack (SA), is to replace an honest implementation of a
cryptographic tool by a subverted one which allows to leak private
information while generating output indistinguishable from the honest
output. Bellare, Paterson, and Rogaway provided at CRYPTO '14 a
formal security model to capture this kind of attacks and constructed
practically implementable ASAs against a large class of symmetric
encryption schemes. At CCS'15 Ateniese, Magri, and Venturi extended
the model to allow the attackers to work in a fully-adaptive and
continuous fashion and proposed subversion attacks against
digital signature schemes. Both papers also showed
impossibility of ASAs in cases when the cryptographic tools are
deterministic. Also at CCS'15, Bellare, Jaeger and Kane strengthened
the original model and proposed a universal ASA against sufficiently
random encryption schemes. In this paper we analyze ASAs from the
point of view of steganography - the well known concept of hiding the
presence of secret messages in legal communications. While a close
connection between ASAs and steganography is known, this lacks a
rigorous treatment. We consider the common computational model for
secret-key steganography and prove that successful ASAs correspond to
secure stegosystems on certain channels and vice versa. This formal
proof allows us to conclude that ASAs are stegosystems and to
»rediscover« several results concerning ASAs known in the steganographic
literature.
- Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
Learning Residual Alternating Automata.
Electronic Colloquium on Computational Complexity (ECCC), 24(46)2017.
Go to website | Show abstract
Residuality plays an essential role for learning finite automata.
While residual deterministic and nondeterministic
automata have been understood quite well, fundamental
questions concerning alternating automata (AFA) remain open.
Recently, Angluin, Eisenstat, and Fisman have initiated
a systematic study of residual AFAs and proposed an algorithm called AL*
-an extension of the popular L* algorithm - to learn AFAs.
Based on computer experiments they conjectured
that AL* produces residual AFAs, but have not been able to give a proof.
In this paper we disprove this conjecture by constructing a counterexample.
As our main positive result we design an efficient
learning algorithm, named AL**, and give a proof
that it outputs residual AFAs only.
In addition, we investigate the succinctness of these different FA types in more detail.
- Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
Learning Residual Alternating Automata.
Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 2017), pp. 1749-1755.
AAAI Press,
2017.
Go to website | Show abstract
Residuality plays an essential role for learning finite automata.
While residual deterministic and non-deterministic
automata have been understood quite well, fundamental questions
concerning alternating automata (AFA) remain open.
Recently, Angluin, Eisenstat, and Fisman (2015) have initiated
a systematic study of residual AFAs and proposed an
algorithm called AL* – an extension of the popular L* algorithm
– to learn AFAs. Based on computer experiments
they have conjectured that AL* produces residual AFAs, but
have not been able to give a proof. In this paper we disprove
this conjecture by constructing a counterexample. As
our main positive result we design an efficient learning algorithm,
named AL**, and give a proof that it outputs residual
AFAs only. In addition, we investigate the succinctness of
these different FA types in more detail.
- Sebastian Berndt, Maciej Liskiewicz:
Hard Communication Channels for Steganography.
In The 27th International Symposium on Algorithms and Computation (ISAAC 2016), ISBN 978-3-95977-026-2, LIPICS Vol. 64, Schloss Dagstuhl-Leibniz-Zentrum für Informatik,
2016.
Go to website | Show abstract
This paper considers steganography -- the concept of hiding
the presence of secret messages in legal communications --
in the computational setting and its relation to cryptography.
Very recently the first (non-polynomial time) steganographic protocol
has been shown which, for any communication channel, is provably secure,
reliable, and has nearly optimal bandwidth. The security is
unconditional, i.e. it does not rely on any unproven
complexity-theoretic assumption. This disproves the claim that the
existence of one-way functions and access to a communication channel
oracle are both necessary and sufficient conditions for the existence of
secure steganography in the sense that secure and reliable steganography
exists independently of the existence of one-way functions.
In this paper, we prove that this equivalence also
does not hold in the more realistic setting, where the
stegosystem is polynomial time bounded. We prove this by constructing
(a) a channel for which secure steganography exists if and only if one-way
functions exist and (b) another channel such that secure steganography
implies that no one-way functions exist. We therefore show that
security-preserving reductions between cryptography and
steganography need to be treated very carefully.
- Sebastian Berndt, Maciej Liskiewicz:
Provable Secure Universal Steganography of Optimal Rate.
In Proceedings of the 4rd ACM Workshop on Information Hiding and Multimedia Security, IH&MMSec 2016, Vigo, Spain, June 20 - 22, 2016, pp. 387-394.
ACM (Awarded Best Student Paper),
2016.
Go to website | Show abstract
We present the first complexity-theoretic secure steganographic protocol which, for any communication channel, is provably secure, reliable, and has nearly optimal bandwidth. Our system is unconditionally secure, i.e. our proof does not rely on any unproven complexity-theoretic assumption, like e.g. the existence of one-way functions. This disproves the claim that the existence of one-way functions and access to a communication channel oracle are both necessary and sufficient conditions for the existence of secure steganography, in the sense that secure and reliable steganography exists independently of the existence of one-way functions.
- Sebastian Berndt, Rüdiger Reischuk:
Steganography Based on Pattern Languages.
In Language and Automata Theory and Applications, 10th International Conference LATA 2016 Prague, Czech Republic, March 14-18, 2016, Volume Volume 9618 of Lecture Notes in Computer Science (LNCS), pp. 387-399.
Springer,
2016.
Go to website | Show abstract
In order to transmit secret information, such that this transmission cannot be
detected, steganography needs a channel, a set of strings with some distribution that occur in an ordinary communication.
The elements of such a language or concept are called coverdocuments.
The question how to design secure stegosystems for natural classes
of languages is investigated for pattern languages.
We present a randomized modification scheme for strings of a pattern
language that can reliably encode arbitrary messages and is almost
undetectable.