- Max Bannach, Sebastian Berndt, Thorsten Ehlers:
Jdrasil: A Modular Library for Computing Tree Decompositions.
In International Symposium on Experimental Algorithms (SEA 2017), Band 75 von LIPIcs, S. 28:1--28:21.
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
2017.
Website anzeigen | Zusammenfassung anzeigen
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 ACM Conference on Computer and Communications Security (CCS 2017), ,
2017 (noch nicht erschienen).
Website anzeigen | Zusammenfassung anzeigen
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.
Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), S. 1749-1755.
,
2017.
Website anzeigen | Zusammenfassung anzeigen
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.
- Martin R. Schuster, Maciej Liskiewicz:
New Abilities and Limitations of Spectral Graph Bisection.
In 25th Annual European Symposium on Algorithms, (ESA) 2017, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
2017.