We study the relationship between size and depth for Boolean circuits. Over four decades, very few results were obtained for either special or general Boolean circuits. Spira showed in 1971 that any Boolean formula of size s can be simulated in depth O(log s). Spira's result means that an arbitrary Boolean expression can be replaced by an equivalent "balanced" expression, that can be evaluated very efficiently in parallel. For general Boolean circuits, the strongest known result is that Boolean circuits of size s can be simulated in depth O(s / log s). We obtain significant improvements over the general bounds for the size versus depth problem for special classes of Boolean circuits. We show that every layered Boolean circuit of size s can be simulated by a layered Boolean circuit of depth O(sqrt{s log s}). For planar circuits and synchronous circuits of size s, we obtain simulations of depth O(sqrt{s}). Improving any of the above results by polylog factors would immediately improve the bounds for general circuits. We generalize Spira's theorem and show that any Boolean circuit of size s with segregators of size f(s) can be simulated in depth O(f(s)log s). This improves and generalizes a simulation of polynomial-size Boolean circuits of constant treewidth k in depth O(k² log n) by Jansen and Sarma. Since the existence of small balanced separators in a directed acyclic graph implies that the graph also has small segregators, our results also apply to circuits with small separators. Our results imply that the class of languages computed by non-uniform families of polynomial size circuits that have constant size segregators equals non-uniform NC¹. As an application of our simulation of circuits in small depth, we show that the Boolean Circuit Value problem for circuits with constant size segregators (or separators) is in deterministic SPACE (log² n). Our results also imply that the Planar Circuit Value problem, which is known to be P-Complete, is in SPACE (sqrt{n} log n). We also show that the Layered Circuit Value and Synchronous Circuit Value problems, which are both P-complete, are in SPACE(sqrt{n}). Our study of circuits with small separators and segregators led us to obtain space efficient algorithms for computing balanced graph separators. We extend this approach to obtain space efficient approximation algorithms for the search and optimization versions of the SUBSET SUM problem, which is one of the most studied NP-complete problems. Finally we study the relationship between simultaneous time and space bounds on Turing machines and Boolean circuit depth. We observe a new connection between planar circuit size and simultaneous time and space products of input-oblivious Turing machines. We use this to prove quadratic lower bounds on the product of time and space for several explicit functions for input-oblivious Turing machines. / text

Graph communication protocols are a generalization of classical communi- cation protocols to the case when the underlying graph is a directed acyclic graph. Motivated by potential applications in proof complexity, we study variants of graph communication protocols and relations between them. The main result is a comparison of the strength of two types of protocols, protocols with equality and protocols with a conjunction of a constant num- ber of inequalities. We prove that protocols of the first type are at least as strong as protocols of the second type in the following sense: For a Boolean function f, if there is a protocol with a conjunction of a constant number of inequalities of polynomial size solving f, then there is a protocol with equality of polynomial size solving f. We also introduce two new types of graph communication protocols, protocols with disjointness and protocols with non-disjointness, and prove that the first type is at least as strong as the previously considered protocols and that the second type is too strong to be useful for applications.

Whitebox cryptography aims at protecting standard cryptographic algorithmsthat execute in attacker-controlled environments. In these, the attacker is ableto read a secret key directly from memory. Common implementations mask alldata at runtime and operate on masked data by using many small precomputedtables. Practical whiteboxes involve trade-offs between security and executionspeed, to limit their footprints and enable applications such as real-time videostreaming.To improve this compromise, we study the use of bitslicing (or bitparallelism)to implement whiteboxes. Bitslicing is commonly used to writefast constant-time implementations of cryptographic algorithms and relies onthe synthesis of boolean circuits implementing the corresponding algorithms.The synthesis of optimal circuits for lookup tables is resource intensive andgenerally only performed once. In a whitebox context however, many randomlookup tables are generated at compile-time. We therefore require the booleancircuit generation to be time efficient.In this master thesis, we review the existing circuit-synthesis algorithms,and analyse their usability in the whitebox context. In particular, we studythe technique of Binary Decision Diagrams to generate efficient circuits ina cheap and adaptable manner. We implemented a flexible version of thisalgorithm as a C++ library. Eventually, we go through different techniques toevaluate the generated circuits and analyse the performances of our algorithm,and recommand the best parameters for the whitebox context. / Vit-låda kryptografi syftar till att skydda kryptografiska standardalgoritmersom körs i miljöer som kontrolleras av angripare, där angriparen kan läsa enhemlig nyckel direkt från minnet. Vanliga tillämpningar maskerar alla data vidkörning och bearbetar maskerade data med hjälp av många små förberäknadetabeller. Praktiska vit-låda innebär att man måste göra avvägningar mellansäkerhet och exekveringshastighet, för att begränsa deras fotavtryck och möjliggöratillämpningar som till exempel videoströmning i realtid.För att förbättra denna kompromiss studerar vi användningen av bitslicing(eller bit-parallelism) för att genomföra vit-låda. Bitslicing används vanligenför att skriva snabba konstanttidsimplementationer av kryptografiska algoritmeroch kräver syntes av boolska kretsar som implementerar motsvarande funktioner.Syntesen av optimala kretsar för uppslagstabeller är resurskrävande och utförsi allmänhet bara en gång. I ett vit-låda-sammanhang genereras dock mångaslumpmässiga uppslagstabeller vid kompilering, och därför kräver vi attgenereringen av boolska kretsar är tidseffektiv.I denna masteruppsats går vi igenom de befintliga algoritmerna för kretssyntesoch analyserar deras användbarhet i vit-låda-sammanhang. Vi studerar särskilttekniken med binära beslutsdiagram för att generera effektiva kretsar på ettbilligt och anpassningsbart sätt. Vi har implementerat en flexibel version avdenna algoritm som ett C++-bibliotek. Slutligen går vi igenom olika teknikerför att utvärdera de genererade kretsarna och analysera vår algoritms prestandaoch rekommenderar de bästa parametrarna för whitebox-kontexten. / La cryptographie en boîte blanche est connue comme protection pour desalgorithmes cryptographiques s’exécutant dans des environnements contrôléspar l’attaquant. L’approche classique consiste à remplacer les opérations pardes accès à des tables précalculées, ce qui a un coût en performance. Il estdifficile d’obtenir un bon compromis entre sécurité et vitesse d’exécution pourdes applications lourdes telles que la diffusion de contenus vidéos en tempsréel.Le parallélisme au bit ou bitslicing est utilisé en cryptographie traditionnellepour accélérer les implémentations, mais aussi en boîte blanche. Cettetechnique d’implémentation demande la synthèse d’un circuit booléen pourchaque table, recherche qui peut être très coûteuse en temps. En pratique, ilest commun de regénérer régulièrement toutes les tables utilisées dans uneboîte blanche pour renouveler sa défense, ce qui complique l’application dubit-parallélisme.Nous présentons dans cette thèse de master notre effort pour une synthèseefficace de circuits booléens à l’usage de la compilation de boîtes blanchesparallèles au bit. Nous publierons avec cet article une bibliothèque C++ etun module de compilation LLVM pour l’écriture d’implémentation bitslicée,avec un objectif de performance et de lisibilité.