Bernd Borchert - Homepage

picture, taken in 2007

Bernd Borchert

Department of Computer Science, University of Tuebingen, Germany

Address: Sand 13, D-72076 Tuebingen, Room B107
Email: borchert at informatik dot uni-tuebingen dot de
Phone: +49-7071-29-70465
Mobile: +49-177-2135290

Scientific Interest: Automata, Logic, Complexity, Algorithms, Cryptography.

Vorlesung Kryptologie Sommersemster 2017

Themen Bachelor/Master Arbeiten

Display-TAN (Startup)


Bernd Borchert, Pierre McKenzie, Klaus Reinhardt
Few Gates but many Zeros

Abstract.  Motivated by the integer factoring problem, we define a d-gem as a {+,-,x}-circuit having at most l(d) product gates and computing a degree d polynomial having d distinct roots in Z, where l(d) is the minimum length of an addition chain for d. For n>3 we exhibit 2n-gems having the additional property of being skew, that is, one input to each {+,-}-gate is from Z. We prove that such skew circuits require n {+,-}-gates and we conclude that our 2n-gems for n>3 are both optimal as gems and as skew gems. We relate our constructions to the conjectures of Blum-Cucker-Shub-Smale and of Buergisser and we raise the unlikely possibility that d-gems might exist for every d. We exhibit optimal d-gems for several values of d up to 55. We observe however that the existence of skew 2n-gems for n>4 would provide new solutions to the Prouhet-Tarry-Escott problem in number theory. By contrast, d-gems over the real numbers are shown to exist for every d.

MFCS 2009

Bernd Borchert
Segment-based Visual Cryptography

Abstract.  A version of Visual Cryptography is presented which is not pixel-based but segment-based. It is used to encrypt messages consisting of symbols which can be represented by a segment display. For example, the decimal digits 0,...,9 can be represented by the well-known seven-segment display. The advantage of the segment-based encryption is that it may be easier to adjust the secret images and that the symbols are potentially easier to recognize for the human eye, especially in a transparency-on-screen szenario.

to be submitted.

Bernd Borchert, Klaus Reinhardt.
Deterministically and Sudoku-Deterministically Recognizable Picture Languages

Abstract.  The recognizable 2-dimensional languages are a robust class with many characterizations, comparable to the regular languages in the 1-dimensional case. One characterization is by tiling systems. The corresponding word problem is NP-complete. Therefore, notions of determinism for tiling systems were suggested. For the notion which was called "deterministically recognizable" it was open since 1998 whether it implies recognizability. By showing that acyclicity of grid graphs is recognizable we answer this question positively. In contrast to that, we show that non-recognizable languages can be accepted by a generalization of this tiling system determinism which we call Sudoku-determinism. Its word problem, however, is still in linear time. We show that Sudoku-determinism even contains the set of 2-dimensional languages which can be recognized by 4-way alternating automata.

LATA 2007, submitted to Theoretical Computer Science

Bernd Borchert.
The dot-depth hierarchy vs. iterated block products of DA

Abstract. Like the sequence of the classes of the dot-depth hierarchy the sequence of classes given by the n-fold iterated block product of DA has the class of starfree regular languages as its limit. It is shown that this DA-block-product hierarchy grows more slowly than the dot-depth hierarchy: in fact already Sigma-2 of the dot-depth hierarchy contains properness witnesses for all levels of the DA-block-product hierarchy.

to be submitted.

Bernd Borchert, Pascal Tesson.
The atnext/atprevious hierarchy on the starfree languages

Abstract. The temporal logic operators atnext and atprevious are alternatives for the operators until and since. P atnext Q has the meaning: at the next position in the future where Q holds it holds P. We define an asymmetric but natural notion of depth for the expressions of this linear temporal logic. The sequence of classes at_n of languages expressible via such depth-n expressions gives a parametrization of the starfree regular languages which we call the atnext/atprevious hierarchy, or simply at hierarchy. It turns out that the at hierarchy equals the hierarchy given by the n-fold weakly iterated block product of DA. It is shown that the at hierarchy is situated properly between the until/since and the dot-depth hierarchy.

to be submitted.

Bernd Borchert, Klaus Reinhardt.
Searching paths of constant bandwith

Abstract. As a generalization of paths, the notion of paths of bandwidth w is introduced. We show that, for constant w≥1, the corresponding search problem for such a path of length k in a given graph is NP-complete and fixed-parameter tractable in the parameter k, like this is known for the special case w=1, the LONGEST PATH problem. We state the FPT algorithm in terms of a guess and check protocol which uses witnesses of size polynomial in the parameter.

SOFSEM 06, LNCS 3831, 187-196

Bernd Borchert.
Formal Language characterizations of P, NP, and PSPACE

Abstract. Based on the notions of locality and recognizability for n-dimensional languages n-dimensionally colorable 1-dimensional languages are introduced. It is shown: A language L is in NP if and only if L is n-dimensionally colorable for some n. An analogous characterization in terms of deterministic n-dimensional colorability is obtained for P. The addition of one unbounded dimension for coloring leads to a characterization of PSPACE.

Journal of Automata, Languages and Combinatorics 13 (2008), 161-183

Bernd Borchert, Klaus-Joern Lange, Frank Stephan, Pascal Tesson, Denis Therien.
The dot-depth and the polynomial hierarchy correspond on the Delta levels

Abstract. It is well-known that the Sigma_k and Pi_k levels of the dot-depth hierarchy and the polynomial hierarchy correspond via leaf languages. We extend this correspondence to the Delta_k levels of these hierarchies: Leaf^P(Delta^L_k) = Delta^p_k. The same methods are used to give evidence against an earlier conjecture of Straubing and Thérien about a leaf-language upper bound for BPP.

International Journal of Foundations of Computer Science 16 (2005), 625-644

Bernd Borchert, Desh Ranjan.
The circuit subfunction relations are Sigma^p_2-complete

Abstract. We show that given two Boolean circuits f and g the following three problems are Sigma^p_2-complete: (1) Is f a c-subfunction of g, i.e. can one set some of the variables of g to 0 or 1 so that the remaining circuit computes the same function as f? (2) Is f a v-subfunction of g, i.e. can one change the names of the variables of g so that the resulting circuit computes the same function as f? (3) Is f a cv-subfunction of g, i.e.\ can one set some variables of g to 0 or 1 and simultanously change some names of the other variables of g so that the new circuit computes the same function as f?

Unpublished manuscript

Bernd Borchert.
The complexity of mind changes

Abstract. Its maximal number of mind changes is a natural invariant of a Boolean function, this notion is studied and applied - under different names - in hardware design, computational complexity and cryptography. In this note it is shown that for each fixed k>1 the computational problem "Given a Boolean circuit f, is k the maximal number of mind changes of the Boolean function computed by f ?" is complete for the class DP of the Boolean Hierarchy over NP. If k is part of the input the corresponding problem is Theta^p_2 complete.

Unpublished manuscript

Bernd Borchert, Riccardo Silvestri.
Dot operators

Abstract. Well-known examples of dot operators are the existential, the counting, and the BP-operator. We will generalize this notion of a dot operator so that every language A will determine an operator A dot. In fact we will introduce the more general notion of promise dot operators for which the BP-operator is an example. Dot operators are a refinement of the leaf language concept because the class determined by a leaf language A equals A dot P. Moreover we are able to represent not only classes but reducibilities, in fact most of the known polynomial-time reducibilities can be represented by dot operators. We show that two languages determine the same dot operator if and only if they are reducible to each other by polylog-time computable monotone projections.

Theoretical Computer Science 262 (2001), 501-523

Bernd Borchert, Frank Stephan.
Looking for an analogue of Rice's Theorem in circuit complexity theory

Abstract. Rice's Theorem says that every nontrivial semantic property of programs is undecidable. In this spirit we show the following: Every nontrivial absolute (gap, relative) counting property of circuits is UP-hard with respect to polynomial-time Turing reductions. For generators [Yap 1983] we show a perfect analogue of Rice's Theorem.

Mathematical Logic Quaterly 46 (2000), 489-504

Bernd Borchert, Lane A. Hemaspaandra, Joerg Rothe.
Restrictive acceptance suffices for equivalence problems

Abstract. One way of suggesting that an NP problem may not be NP-complete is to show that it is in the promise class UP. We suggest an analogous new approach - weaker in strength of evidence but more broadly applicable - to suggesting that concrete NP problems are not NP-complete. In particular we introduce the class EP, the subclass of NP consisting of those languages accepted by NP machines that when they accept always have a number of accepting paths that is a power of two. We show that FewP, bounded ambiguity polynomial time (which contains UP), is contained in EP. The class EP applies as an upper bound to some concrete problems to which previous approaches have never been successful, for example the negation equivalence problem for OBDDs (ordered binary decision diagrams).

LMS Journal of Computation and Mathematics 3 (2000), 86-95

Bernd Borchert, Dietrich Kuske, Frank Stephan.
On existentially first-order definable languages and their relation to NP

Abstract. Under the assumption that the Polynomial-Time Hierarchy does not collapse we show for a regular language L: the unbalanced polynomial-time leaf language class determined by L equals NP iff L is existentially but not quantifierfree definable in FO[<,min,max,-1,+1]. Furthermore, no such class lies properly between NP and co-1-NP or NP join co-NP. The proofs rely on a result of Pin and Weil characterizing the automata of existentially first-order definable languages.

Theoretical Informatics and Applications 33 (1999) 259-269

Bernd Borchert, Desh Ranjan, Frank Stephan.
On the computational complexity of some classical equivalence relations on Boolean functions

Abstract. The paper analyzes in terms of polynomial time many-one reductions the computational complexity of several natural equivalence relations on Boolean functions which derive from replacing variables by expressions, one of them is the Boolean isomorphism relation. Most of these computational problems turn out to be between co-NP and Sigma-p-2.

Theory of Computing Systems 31 (1998) 679-693

Bernd Borchert, Riccardo Silvestri.
A characterization of the leaf language classes

Abstract. Bovet, Crescenzi, and Silvestri (1992,1995), and independently Vereshchagin (1994), showed that many complexity classes in the polynomial time setting are leaf language classes, i.e. classes which are determined by two disjoint languages. They gave many examples but they did not characterize the set of leaf language classes. This will be done in this paper. It will be shown that the set of leaf language classes equals the set of countable complexity classes which, with respect to polynomial-time many-one reducibility, are closed downward and closed under join. Moreover, the set of classes characterized by two complementary leaf languages will be shown to be equal to the set of complexity classes which, with respect to polynomial-time many-one reducibility, have a complete set and are closed downward.

Information Processing Letters 63 (1997) 153-158

Bernd Borchert, Antoni Lozano.
Succinct circuit representations and leaf language classes are basically the same concept

Abstract. This note connects two topics of Complexity Theory: The topic of succinct circuit representations initiated by Galperin and Wigderson (1983), and the topic of leaf language classes initiated by Bovet et al. (1992). It will be shown for any language that its succinct version is polynomial-time many-one complete for the leaf language class determined by it.

Information Processing Letters 59 (1996) 211-215

Bernd Borchert.
On the acceptance power of regular languages

Abstract. Hertrampf et al. (1993) looked at complexity classes which are characterized (say accepted) by a regular language for the words of output bits produced by nondeterministic polynomial-time computations. A number of well-known complexity classes between P and PSPACE are accepted by regular languages. For example, NP is accepted by the regular language which consists of the words which contain at least one letter 1. The main result will be that the inclusion order on the complexity classes accepted by regular languages has the following property: if a class accepted by a nontrivial regular language is not equal to P then it contains at least one of the classes NP, coNP and MOD_pP for p prime. This will be interpreted as a non-density result in two ways: (1) on the assumption that the Polynomial Time Hierarchy does not collapse, and (2) for the relativized case.

Theoretical Computer Science 148 (1995) 207-225

Copyright Notice. The copyrights for the journal papers belong to the publishers of the respective journals. All papers may be downloaded for personal or research purposes only.

Patent Applications

The patent applications present different solutions to the following problem. For online accounts - especially for online banking accounts - the PC of the user is a major security problem: SSL encryption prevents malware in the Internet to eavesdrop and to manipulate the user input but SSL cannot prevent malware on the PC of the user to do so. For example, a so-called keylogger can record the account password while the user is typing it. For online banking there is the special danger of a Man-in-the-Middle attack to a money transfer confirmed by a TAN or iTAN: the recipient account and the amount of money may be manipulated by the malware, while the user does not even notice the manipulation.

Bernd Borchert, Marc Fouquet, Heiko Niedermeyer, Klaus Reinhardt
Verfahren und System zur bidirektionalen, abhoer- und manipulationssicheren Uebertragung von Informationen ueber ein Netzwerk sowie Dekodiereinheit

Abstract. A device is suggested which is to be put between the computer and the screen: the device decodes a part of the screen. All the information needed for decoding is contained in some pixels of the screen signal itself. This way, a server can send a secret information to the client by sending the coded information to the client's screen: neither a virus in the internet nor a trojan on the client's computer can read the information but the client can, after decoding by the device. A protocol is presented which allows to send secure messages also in the other direction, i.e. from the client to the server.


Bernd Borchert
Faelschungssichere Online Transaktionen via Cardano Verschluesselung

Abstract. Cardano encryption is used in a punchcard-on-screen version in order to send secure messages from a server to a client and also from the client back to the server.


Bernd Borchert
Abhoersichere Verschluesselung fuer Online Accounts

Abstract. The invention relates to the encryption of online accounts. A method is presented which allows the client to send a message to the server which can not be tapped, for example the password for the account. For this purpose the server produces an image with areas randomly labeled by symbols from a given set of symbols and sends it to the client in a secure way. Now a tap-proof message composed of the symbols can be send from the client to the sever: the server shows the client a set of areas which have a similar arrangement like the the arrangement of the areas on the image send before but have no symbols. By activating the areas which correspond by their position to the areas with the symbols of the intended message the client can formulate a message. The information about which areas are activated are sent to the server. The server can reconstruct the message while an eavesdropper can only notice positions but can not make sence of them. The image produced by the server can be send to the client via paper or via transparency but also via some electronic device.


Bernd Borchert, Klaus Reinhardt.
Device and Method For Tap-Proof and Manipulation-Proof Encoding of Online Accounts

Abstract. The invention relates to a method and a device for the tap-proof and manipulation-proof transmission of messages between a server and the computer of a client, over a computer network, and for the decoding of encoded messages by clients. The method and the device can be especially used for encoding online accounts, especially for online banking. The device, described as a cryptocard, is preferably a flat appliance comprising photosensory elements on the rear side and a display on the front side. The device also contains a logic element/processor and an electronic memory containing codes. It is placed on the screen of the computer of the client, on which the following is displayed in image format: (1) an encoded message, (2) the number of the code required for the decoding, and (3) the co-ordinates of the actual position of the indicator symbol. This information received by the photosensors is decoded by the logic element/processor by means of the code, and the message is decoded and displayed in a clearly visible manner on the display. The indicator symbol on the screen is simulated on the display. By clicking buttons marked with characters on the cryptocard, a message can be transmitted from the client to the server. As the marking of the buttons by the characters is fixed previously at random by the server and transmitted in a tap-proof manner to the cryptocard, the transmission of the message from the client to the server is also tap-proof. The tap-proofness in both directions allows a protocol for online banking to be implemented, which renders the PIN tap-proof and prevents the falsification of transfers.

Patent DE-2007-029759.0, WO-2009-000223

Bernd Borchert, Klaus Reinhardt.
Anti-Tapping and Anti-Manipulation Encoding for Online Accounts

Abstract. The invention relates to a method for anti-tapping and anti-manipulation encoding for online accounts, in particular for online banking, by means of visual cryptography. A first partial secret image is generated on a film by the server according to the method of visual cryptography. A second partial secret image is generated by the server with keypads with random characters and displayed on the screen of the client, the keypad being clickable with the mouse. In the next step, the film and the screen are superimposed by the client such that both partial secret images give the image with the clickable keypad with written characters. The client can now enter a sequence of n characters by n mouse clicks on the keypads with characters. The information about which keys the client has clicked in which sequence is then transmitted to the server and the inputted sequence of characters reconstructed in the server.

Patent DE-2007-018802.3, WO-2008-128528