2024

• Pascal Bemmann, Sebastian Berndt, Rongmao Chen:
  Subversion-Resilient Signatures without Random Oracles.
  In Conference on Applied Cryptography and Network Security (ACNS 2024), , 2024.
• Florian Sieck, Zhiyuan Zhang, Sebastian Berndt, Chitchanok Chuengsatiansup, Thomas Eisenbarth, Yuval Yarom:
  TeeJam: Sub Cache Line Leakages Strike Back.
  In IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES '24), , 2024.

2023

• Pascal Bemmann, Sebastian Berndt, Denis Diemert, Tibor Jager:
  Subversion-Resilient Authenticated Encryption without Random Oracles.
  In Applied Cryptography and Network Security, ACNS 2023, Communications in Computer and Information Science, , 2023.
• Sebastian Berndt, Thomas Eisenbarth, Sebastian Faust, Marc Gourjon, Maximilian Orlt, Okan Seker:
  Combined Fault and Leakage Resilience: Composability, Constructions and Compiler.
  In Advances in Cryptology - CRYPTO 2023, Springer, 2023.
• Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich, Tobias Stamm:
  New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines.
  In The 34th International Symposium on Algorithms and Computation (ISAAC 2023), , 2023.
• Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack, Lars Rohwedder:
  Online Bin Covering with Limited Migration.
  J. Comput. Syst. Sci., 2023.
• Thore Tiemann, Sebastian Berndt, Thomas Eisenbarth, Maciej Liskiewicz:
  "Act natural!": Having a Private Chat on a Public Blockchain.
  In 8th IEEE European Symposium on Security and Privacy (EuroS&P '23), IEEE, 2023.

2022

• Max Bannach, Sebastian Berndt:
  Recent Advances in Positive-Instance Driven Graph Searching.
  Algorithms, 15(2):42, 2022.
  Go to website | Show abstract
  
  Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic programming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Algorithms producing only such subinstances are called positive-instance driven (PID). The parameter treedepth has a similar story. It was popularized through the graph sparsity project and is theoretically well understood—but the first practical algorithm was discovered only recently by Trimble (IPEC 2020) and is based on the same paradigm. We give an alternative and unifying view on such algorithms from the perspective of the corresponding configuration graphs in certain two-player games. This results in a single algorithm that can compute a wide range of important graph parameters such as treewidth, pathwidth, and treedepth. We complement this algorithm with a novel randomized data structure that accelerates the enumeration of subproblems in positive-instance driven algorithms.
• Sebastian Berndt, Jan Wichelmann, Claudius Pott, Tim-Henrik Tracking, Thomas Eisenbarth:
  ASAP: Algorithm Substitution Attacks on Cryptographic Protocols.
  In Proceedings ASIACCS, ACM, 2022.
• Sebastian Berndt, Maciej Liskiewic, Matthias Lutter, Rüdiger Reischuk:
  Learning residual alternating automata.
  Inf. Comput., 289(Part):861-878, 2022.
• Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
  Learning residual alternating automata.
  Information and Computation, (289):104981, 2022.
  Go to website
• Sebastian Berndt, Max A. Deppert, Klaus Jansen, Lars Rohwedder:
  Load Balancing: The Long Road from Theory to Practice..
  In Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2022, pp. 104-116. SIAM, 2022.
  Go to website
• Sebastian Berndt, Franziska Eberle, Nicole Megow:
  Online load balancing with general reassignment cost.
  Operations Research Letters, 50(3):322-328, 2022.

2020

• Max Bannach, Sebastian Berndt, Martin Schuster, Marcel Wienöbst:
  PACE Solver Description: PID*.
  In Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), LIPIcs, 2020.
  Go to website | Show abstract
  
  This document provides a short overview of our treedepth solver PID^{?} in the version that we submitted to the exact track of the PACE challenge 2020. The solver relies on the positive-instance driven dynamic programming (PID) paradigm that was discovered in the light of earlier iterations of the PACE in the context of treewidth. It was recently shown that PID can be used to solve a general class of vertex pursuit-evasion games - which include the game theoretic characterization of treedepth. Our solver PID^{?} is build on top of this characterization.
• Max Bannach, Sebastian Berndt, Martin Schuster, Marcel Wienöbst:
  PACE Solver Description: Fluid.
  In Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), LIPIcs, 2020.
  Go to website | Show abstract
  
  This document describes the heuristic for computing treedepth decompositions of undirected graphs used by our solve fluid. The heuristic runs four different strategies to find a solution and finally outputs the best solution obtained by any of them. Two strategies are score-based and iteratively remove the vertex with the best score. The other two strategies iteratively search for vertex separators and remove them. We also present implementation strategies and data structures that significantly improve the run time complexity and might be interesting on their own.
• Max Bannach, Sebastian Berndt, Marten Maack, Matthias Mnich, Alexandra Lassota, Malin Rau, Malte Skambath:
  Solving Packing Problems with Few Small Items Using Rainbow Matchings.
  In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), LIPIcs, 2020.
  Go to website | Go to website | Show abstract
  
  An important area of combinatorial optimization are packing problems. While fundamental problems like bin packing, multiple knapsack, and bin covering have been studied intensively from the viewpoint of approximation algorithms, the use of parameterized techniques for this problems is rather limited. For instances containing no "small'' items, known matching algorithms give exact polynomial-time algorithm. Following the distance from triviality approach, our parameter k is the distance from such easy instances, i. e., the number of small items. Our main results are randomized fixed-parameter tractable algorithms for vector-versions of bin packing, multiple knapsack, and bin covering parameterized by k, which run in time 4^k * k! * n^O(1) with one-sided error. To achieve this, we introduce a colored matching problem to which we reduce all these packing problems. The colored matching problem is natural in itself and we expect it to be useful for other applications as well. We also present a deterministic parameterized algorithm for bin packing with run time O( (k!)^2 * k * 2^k + n log(n) ).
• Sebastian Berndt, Maciej Liskiewicz:
  On the universal steganography of optimal rate.
  Information and Computation, 104632(Available online 14 October 2020)2020.
  Go to website

2019

• Max Bannach, Sebastian Berndt:
  Positive-Instance Driven Dynamic Programming for Graph Searching.
  In Proceedings of the 16th Algorithms and Data Structures Symposium (WADS 2019), Springer, 2019.
  Show PDF | Show abstract
  
  Research on the similarity of a graph to being a tree – called the treewidth of the graph – has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic program- ming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Al- gorithms producing only such subinstances are called positive-instance driven (PID). We give an alternative and intuitive view on this algo- rithm from the perspective of the corresponding configuration graphs in certain two-player games. This allows us to develop PID-algorithms for a wide range of important graph parameters such as treewidth, pathwidth, q-branched treewidth, treedepth and dependency-treewidth. We analyze the worst case behavior of the approach on some well-known graph classes and perform an experimental evaluation on real world and random graphs.
• Max Bannach, Sebastian Berndt:
  Practical Access to Dynamic Programming on Tree Decompositions.
  MDPI Algorithms, 2019. Special Issue: New Frontiers in Parameterized Complexity and Algorithms
  Go to website | Show abstract
  
  Parameterized complexity theory has led to a wide range of algorithmic breakthroughs within the last few 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, …). 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 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 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 MSO1 (that is, we do not consider “edge-set-based” problems). 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.

2018

• 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

2017

• 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.

2016

• 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.

2015

• Sebastian Berndt, Klaus Jansen, Kim-Manuel Klein:
  Fully Dynamic Bin Packing Revisited.
  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), Volume 40 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 135-151. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015.
  Go to website | Show abstract
  
  We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is the migration factor, defined as the total size of repacked items divided by the size of an arriving or departing item. Concerning the trade-off between number of bins and migration factor, if we wish to achieve an asymptotic competitive ratio of 1 + epsilon for the number of bins, a relatively simple argument proves a lower bound of Omega(1/epsilon) of the migration factor. We establish a fairly close upper bound of O(1/epsilon^4 log(1/epsilon)) using a new dynamic rounding technique and new ideas to handle small items in a dynamic setting such that no amortization is needed. The running time of our algorithm is polynomial in the number of items n and in 1/epsilon. The previous best trade-off was for an asymptotic competitive ratio of 5/4 for the bins (rather than 1+epsilon) and needed an amortized number of O(log n) repackings (while in our scheme the number of repackings is independent of n and non-amortized).

2014

• Sebastian Berndt, Klaus Jansen, Kim-Manuel Klein:
  Fully Dynamic Bin Packing Revisited.
  Technical report arXiv:1411.0960, arXiv, 2014.
  Go to website | Show abstract
  
  We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is the migration factor, defined as the total size of repacked items divided by the size of an arriving or departing item. Concerning the trade-off between number of bins and migration factor, if we wish to achieve an asymptotic competitive ratio of 1 + epsilon for the number of bins, a relatively simple argument proves a lower bound of Omega(1/epsilon) of the migration factor. We establish a fairly close upper bound of O(1/epsilon^4 log(1/epsilon)) using a new dynamic rounding technique and new ideas to handle small items in a dynamic setting such that no amortization is needed. The running time of our algorithm is polynomial in the number of items n and in 1/epsilon. The previous best trade-off was for an asymptotic competitive ratio of 5/4 for the bins (rather than 1+epsilon) and needed an amortized number of O(log n) repackings (while in our scheme the number of repackings is independent of n and non-amortized).