Calendrier des animations scientifiques

Blind Signatures are a useful primitive for privacy preserving applications such as electronic payments, e-voting, anonymous credentials, and more. However, existing practical blind signature schemes based on standard assumptions require either pairings or lattices. We present the first practical construction of a round-optimal blind signature in the random oracle model based on standard assumptions without resorting to pairings or lattices. In particular, our construction is secure under the strong RSA assumption and DDH (in pairing- free groups). For our construction, we provide a NIZK-friendly signature based on strong RSA, and efficiently instantiate a variant of Fischlin’s generic framework (CRYPTO’06). Our Blind Signature scheme has signatures of size 4.28 KB and communication cost 10.98 KB. On the way, we develop techniques that might be of independent interest. In particular, we provide efficient relaxed range-proofs for large ranges with subversion zero-knowledge and compact commitments to elements of arbitrary groups.

This is a joint work with Julia Kastner (CWI) and Michael Reichle (ETH Zurich), available at https://eprint.iacr.org/2023/1810.

We initiate a case study for the problem of deciding graph class properties, based on their finite descriptions. In particular, we deal with properties of minor-closed graph classes where such a description is their finite obstruction set. The question on whether there is a polynomial-time algorithm for such problems is related to the conjecture that $ω^2$-WQO of graphs with respect to the minor relation, which is a major open problem in Order Theory. We present a series of instantiations of the above problem where such algorithms exist and can be constructed.

En combinatoire des mots, il est courant de compter le nombre de motifs spécifiques apparaissant dans une suite infinie. En effet, de nombreux travaux sont consacrés à l’étude de la célèbre complexité en facteurs, c’est-à-dire le nombre de facteurs (blocs continus de lettres) différents. Une variante bien connue est la complexité abélienne, où les facteurs sont comptés à équivalence abélienne près, c’est-à-dire à permutation des lettres près. Dans cet exposé, nous discuterons du concept relativement peu exploré de la complexité additive, qui compte les facteurs à équivalence additive près. Deux facteurs sont dits additivement équivalents s’ils sont de même longueur et que la somme des lettres qui les composent est la même. Notre contribution consiste à élargir les connaissances générales sur la complexité additive d’un point de vue théorique et à examiner divers exemples bien connus en combinatoire des mots. En particulier, nous utilisons le formalisme de la logique et le logiciel Walnut pour décider des propriétés liées aux suites automatiques. Ce travail est en collaboration avec Jeffrey Shallit et Manon Stipulanti.

NOTICE THE SEMINAR WILL TAKE PLACE IN THE SEMINAR ROOM UNLIKE THE FIRST ANNOUNCEMENT

The simplex method is a very efficient algorithm. In this talk we see a few of the state-of-the-art theories for explaining this observation. We will discuss what it takes for a mathematical model to explain an algorithm’s qualities, and whether existing theories meet this bar. Following this, we will question what the simplex method is and if the theoretician’s simplex method is the same algorithm as the practitioner’s simplex method. Along the way I will sprinkle in some historical anecdotes about linear programming.

We establish a parametric framework for obtaining obstruction characterizations of graph parameters with respect to a quasi-ordering $\leq$ on graphs.
At the center of this framework lies the concept of a $\leq$-parametric graph: a non $\leq$-decreasing sequence ${G} = \langle {G}_{t} \rangle_{t \in \mathbb{N}}$ of graphs indexed by non-negative integers.
Parametric graphs allow us to define combinatorial objects that capture the approximate behaviour of graph parameters.
A finite set $\mathfrak{G}$ of $\leq$-parametric graphs is a $\leq$-universal obstruction for a parameter $\mathsf{p}$ if there exists a function $f \colon \mathbb{N} \to \mathbb{N}$ such that, for every $k \in \mathbb{N}$ and every graph $G$, 1) if $\mathsf{p}(G) \leq k$, then for every ${G} \in \mathfrak{G},$ ${G}_{f(k)}
ot\leq G$, and 2) if for every ${G} \in \mathfrak{G},$ ${G}_{k}
ot\leq G$, then $\mathsf{p}(G) \leq f(k).$
To solidify our point of view, we identify sufficient order-theoretic conditions that guarantee the existence of universal obstructions and in this case we examine algorithmic implications on the existence of fixed-parameter tractable algorithms.

Our parametric framework has further implications related to finite obstruction characterizations of properties of graph classes.
A $\leq$-class property is defined as any set of $\leq$-closed graph classes that is closed under set inclusion.
By combining our parametric framework with established results from order theory, we derive a precise order-theoretic characterization that ensures $\leq$-class properties can be described in terms of the exclusion of a finite set of $\leq$-parametric graphs.

As a proof of concept we apply our viewpoint to the study of Erdős-Pósa dualities for the minor relation.
We say that a pair $({H},{G})$ of minor-closed classes is an {Erdős-Pósa pair} (EP-pair for short) if there exists a function $f \colon \mathbb{N} \to \mathbb{N}$ such that for every $k \in \mathbb{N}$ and every graph $G \in {G},$ either $G$ has $k$ pairwise vertex-disjoint subgraphs which do not belong to ${H},$ or there exists a set $S\subseteq V(G)$ of size at most $f(k)$ for which $G – S \in {H}.$
For every minor-closed class ${H}$ we define the minor-class property $\mathbb{EP}_{H}$ as the set of all minor-closed classes ${G}$ for which $(H, G)$ is an EP-pair.

We prove that for every minor-closed class ${H}$ there exists a {finite} set of grid-like minor-parametric graphs $\mathfrak{G}_{H}$ such that a minor-closed class ${G}$ belongs to $\mathbb{EP}_{H}$ if and only if for every ${G} \in \mathfrak{G}_{H},$ ${G}$ does not contain ${G}_{k},$ for some $k \in \mathbb{N}.$
In particular, we provide an explicit description for $\mathfrak{G}_{H}$ for every ${H}$ and give a constructive upper bound on its size.
Moreover, each ${G}_{k}$ admits a half-integral packing, i.e., $k$ copies of some graph in ${H}$ where no vertex is used more than twice.
This implies a complete delineation of the half-integrality threshold of the Erdős-Pósa property for minors, and as a corollary, we obtain a constructive proof of Thomas’ conjecture on the half-integral Erdős-Pósa property for minors which was recently confirmed by Liu.
Our results are algorithmic.
For every minor-closed graph class ${H},$ we obtain an algorithm that, given a graph on $n$ vertices and $k \in \mathbb{N},$ outputs either a half-integral packing of $k$ copies of some graph in ${H}$ or a set of at most $2^{k^{O(1)}}$ vertices whose deletion yields a graph in ${H}$ in time $O_{k}(n^4 \log n).$
As a consequence of our results we obtain minor-universal obstructions for the graph parameters ${H}$-treewidth, elimination distance to ${H},$ and apex number to ${H},$ for every minor-closed class ${H}.$

OR-Proofs allow for proving the validity of 1 out of n different statements without revealing which one this is. In this presentation, we describe a new approach for transforming certain proofs system into new ones that allows for OR-proofs. The communication complexity of the resulting proof system only depends logarithmically on the total number of statements and its security only relies on the existence of collision-resistant hash functions. As an example, we show that our transformation is applicable to the proof systems of Goldreich, Micali, and Wigderson (FOCS’86) for the graph isomorphism problem.
Our main technical tool, which we believe to be of independent interest, is a new cryptographic primitive called non-adaptively programmable functions (NAPs). Those functions can be seen as pseudorandom functions which allow for re-programming the output at an input point, which must be fixed during key generation. Even when given the re-programmed key, it remains infeasible to find out where re-programming happened. Finally, as an additional technical tool, we also build explainable samplers for any distribution that can be sampled efficiently via rejection sampling and use them to construct NAPs for various output distributions.
The presentation starts with introducing the concepts of Sigma-protocols and OR-proofs. Then, the new NAP primitive is introduced and instantiated from one-way functions. Lastly, we explain how to use NAPs to efficiently compress Sigma-protocols.
Joint work with Mark Simkin, published at TCC’24.