This chapter gives an overview of proof complexity and connections to SAT solving, focusing
on proof systems such as resolution, Nullstellensatz, polynomial calculus, and cutting planes …

For any n-bit boolean function f, we show that the randomized communication complexity of
the composed function fog n, where g is an index gadget, is characterized by the …

We present new protocols for conditional disclosure of secrets (CDS), where two parties
want to disclose a secret to a third party if and only if their respective inputs satisfy some …

A secret-sharing scheme allows to distribute a secret s among n parties such that only some
predefined “authorized” sets of parties can reconstruct the secret, and all other …

Separations: We introduce a monotone variant of Xor-Sat and show it has exponential
monotone circuit complexity. Since Xor-Sat is in NC^ 2, this improves qualitatively on the …

We characterize the size of monotone span programs computing certain “structured”
boolean functions by the Nullstellensatz degree of a related unsatisfiable Boolean formula …

For many cryptographic primitives, it is relatively easy to achieve selective security (where
the adversary commits a-priori to some of the choices to be made later in the attack) but …

This note, based on my 4ECM lecture, exposes few basic points of proof complexity in a way
accessible to any mathematician. In many parts of mathematics one finds statements …

A secret-sharing scheme allows to distribute a secret s among n parties such that only some
predefined “authorized” sets of parties can reconstruct the secret, and all other …

A secret-sharing scheme for a monotone Boolean (access) function F:{0, 1\}^ n → {0, 1\} is a
randomized algorithm that on input a secret, outputs n shares s_1, ..., s_n such that for any …