- Sebastian Berndt, Maciej Liskiewicz:
Algorithm Substitution Attacks from a Steganographic Perspective.
In ACM Conference on Computer and Communications Security (CCS 2017), ,
2017 (to appear).
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.
Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), pp. 1749-1755.
,
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, 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.
- Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
Proper Learning of k-term DNF Formulas from Satisfying Assignments.
Electronic Colloquium on Computational Complexity (ECCC), 24(114)2017.
Go to website | Show abstract
In certain applications there may only be positive samples available to to learn concepts of a class of interest, and this has to be done properly, i.e. the hypothesis space has to coincide with the concept class, and without false positives, i.e. the hypothesis always has be a subset of the real concept (one-sided error). For the well studied class of k-term DNF formulas it has been known that learning is difficult. Unless RP = NP, it is not feasible to learn k-term DNF formulas properly in a distribution-free sense even if both positive and negative samples are available and even if false positives are allowed.
This paper constructs an efficient algorithm that for arbitrary fixed k, if samples are drawn from distributions like uniform or q-bounded ones, properly learns the class of k-term DNFs without false positives from positive samples alone with arbitrarily small relative error.
- Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
Security levels in steganography - Insecurity does not imply detectability.
Theoret. Comput. Sci., 2017.
Go to website - Martin R. Schuster, Maciej Liskiewicz:
New Abilities and Limitations of Spectral Graph Bisection.
Technical report 1701.01337,
arXiv,
2017.
Go to website | Show abstract
Spectral based heuristics belong to well-known commonly used methods which determines provably minimal graph bisection or outputs "fail" when the optimality cannot be certified. In this paper we focus on Boppana's algorithm which belongs to one of the most prominent methods of this type. It is well known that the algorithm works well in the random \emph{planted bisection model} -- the standard class of graphs for analysis minimum bisection and relevant problems. In 2001 Feige and Kilian posed the question if Boppana's algorithm works well in the semirandom model by Blum and Spencer. In our paper we answer this question affirmatively. We show also that the algorithm achieves similar performance on graph classes which extend the semirandom model.
Since the behavior of Boppana's algorithm on the semirandom graphs remained unknown, Feige and Kilian proposed a new semidefinite programming (SDP) based approach and proved that it works on this model. The relationship between the performance of the SDP based algorithm and Boppana's approach was left as an open problem. In this paper we solve the problem in a complete way by proving that the bisection algorithm of Feige and Kilian provides exactly the same results as Boppana's algorithm. As a consequence we get that Boppana's algorithm achieves the optimal threshold for exact cluster recovery in the \emph{stochastic block model}. On the other hand we prove some limitations of Boppana's approach: we show that if the density difference on the parameters of the planted bisection model is too small then the algorithm fails with high probability in the model.
- 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.
- Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Space Efficient Algorithms for Series-Parallel Graphs.
Technical report SIIM-TR-A-00-17,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
2000.
Show postscript | Show abstract
The subclass of directed series-parallel graphs plays an important role in
computer science. To determine whether a graph is series-parallel is a
well studied problem in algorithmic graph theory. Fast sequential and
parallel algorithms for this problem have been developed in a sequence
of papers. For series-parallel graphs methods are also known to solve
the reachability and the decomposition problem time efficiently.
However, no dedicated results have been obtained for the space complexity
of these problems -- the topic of this paper.
For this special class of graphs, we develop deterministic algorithms
for the recognition, reachability, decomposition and the path counting
problem that use only logarithmic space. Since for arbitrary directed
graphs reachability and path counting are believed not to be solvable
in log-space the main contribution of this work are novel deterministic
path finding routines that work correctly in series-parallel graphs,
and a new characterization of series-parallel graphs by forbidden subgraphs.
We then sketch how these results can be generalised to extension of
the series-parallel graph family: to graphs with multiple sources or multiple
sinks and to the class of minimal vertex series-parallel graphs.
It it also shown that the space bounds are best possible,
i.e. the decision problems are L-complete with respect to AC-reductions.
Finally, we discuss implications of theses small space bounds for
the parallel time complexity of series-parallel graphs.
- Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
The Expressive Power and Complexity of Dynamic Process Graphs.
In 26. Int. Workshop on Graph-Theoretical Concepts in Computer Science WG'2000, Volume 1928 of Lecture Notes in Computer Science, pp. 230-242.
Springer,
2000.
Go to website - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
The Expressive Power and Complexity of Dynamic Process Graphs.
Technical report SIIM-TR-A-00-07,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
2000.
Show postscript | Show abstract
A model for parallel and distributed programs, the dynamic process graph,
is investigated under graph-theoretic and complexity aspects. Such graphs
are capable of representing all possible executions of a parallel or
distributed program in a very compact way. The size of this representation
is small -- in many cases only logarithmic with respect to the size of any
execution of the program. An important feature of this model is that
the encoded executions are directed acyclic graphs with a regular structure,
which is typical of parallel programs, and that it embeds constructors for
parallel programs, synchronization mechanisms as well as conditional branches.
In a previous paper we have analysed the expressive power of the general
model and various restrictions. Furthermore, from an algorithmic point
of view it is important to decide whether a given dynamic process graph can
be executed correctly and to estimate the minimal deadline given enough
parallelism. Our model takes into account communication delays between
processors when exchanging data.
In this paper we study a variant with output restriction. It is appropriate
in many situations, but its expressive power has not been known exactly.
First, we investigate structural properties of the executions of such dynamic
process graphs G. A natural graph-theoretic conjecture that executions must
always split into components isomorphic to subgraphs of G turns out to be
wrong. We are able to establish a weaker property. This implies a quadratic
bound on the maximal deadline in contrast to the general case, where
the execution time may be exponential. However, we show that the problem
to determine the minimal deadline is still intractable, namely this problem
is NEXPTIME-complete as is the general case. The lower bound is obtained by
showing that this kind of dynamic process graphs can represent certain
Boolean formulas in a highly succinct way.
This is an extended abstract to be presented at 26th International Workshop
on Graph-Theoretic Concepts in Computer Science, Konstanz, Germany, 2000.