Calendrier des animations scientifiques

Consider a data structure problem with possible data coming from a set
$\mathcal D$, queries coming from a set $\mathcal Q$, and in the dynamic
case updates coming from a set $\mathcal U$. Then, the current state of
the art in data structure lower bounds is
$t = \tilde\Omega(\log |\mathcal Q|)$ for static data structure
problems, and
$\max(t_{\mathrm q},t_{\mathrm u}) = \tilde\Omega((\log n)^2)$ where
$n = \max(|\mathcal Q|,|\mathcal U|,\log |\mathcal D|)$ for dynamic.

We port Razborov and Rudich’s natural-proofs framework to the setting of
static and dynamic data structures in the cell probe model, in a way
that strongly suggests this state of the art is unlikely to be improved
anytime soon. A similar direction was recently taken also by Korten,
Pitassi and Impagliazzo (FOCS 2025) who look at static data structure
lower bounds in a different regime of parameters. Our contribution is:

– We define notions analogous to pseudorandom functions (PRF). We call
these primitives *local PRFs*, in the context of static data
structures, and *local and locally updatable (LLU) PRFs*, in the
context of dynamic data structures.
– We then formulate cryptographic conjectures, namely, that secure
local PRFs and secure LLU PRFs exist, precisely at the frontier
where we are no longer able to prove static, respectively dynamic,
data structure lower bounds. If these conjectures are true, it
follows that the current state of the art in data structure lower
bounds cannot be improved by a natural proof.
– We show that (almost) every single known data structure lower bound
proof is a natural proof, by surveying all lower bounds in the
literature (known to us). (The only exception is proofs based on
lifting theorems.)
– It follows that, if our cryptographic conjecture is true, then all
known lower bound proof techniques (minus the two exceptions) are
unable to improve upon the state of the art. (We also present
obstacles for the two exceptions.)
– Further, we provide concrete candidate constructions for our two
pseudo-random primitives. We conjecture that our constructions are
secure for parameters just above the state-of-the-art lower bounds.
– We also show that, whether or not they are secure, our candidate
PRFs at least satisfy the natural properties appearing in all (but
one) known proofs.
– So if one is interested in improving upon the state of the art in
static or dynamic data structure lower bounds, one must either find
a non-natural method of proving such lower bounds (no such method
currently exists), or one may as well begin by trying to break our
PRF candidates.

The devastating attacks against SIDH (Supersingular Isogeny Diffie-Hellman) in 2022 introduced higher-dimensional isogenies as a cryptanalytic tool. As opposed to elliptic curve isogenies, higher-dimensional isogenies are defined between abelian varieties (which generalize elliptic curves in higher dimension). These isogenies quickly became a powerful constructive tool with the introduction of SQIsignHD and FESTA, followed up by many new isogeny-based schemes.

The digital signature scheme SQIsignHD, based on SQIsign was the first scheme to use 4-dimensional isogenies but soon became obsolete when 2-dimensional alternatives were introduced and proposed as a part of the SQIsign NIST post-quantum signatures standard submission. For efficiency reasons, most isogeny based schemes aiming for practical use rely on isogenies of dimension at most 2, and it is widely believed in the isogeny community that isogenies of dimension bigger than 2 should be avoided.

The recent introduction of the Pegasis algorithm to compute the ideal class group action on oriented supersingular elliptic curves without restriction on the ideal has changed this perspective. This algorithm using 4-dimensional isogenies beats all 2-dimensional alternatives. Pegasis can be used as a tool to improve advanced cryptographic schemes that require unrestricted cryptographic group actions and is to be integrated in a NIST post-quantum threshold cryptographic standard submission. 4-dimensional isogenies also appear in the tensor-MIKE key exchange that remains to be implemented.

These works make 4-dimensional isogenies more credible while algorithms to compute them are still making progress.

An elimination tree of a connected graph $G$ is a rooted tree on the vertices of $G$ obtained by choosing a root $v$ and recursing on the connected components of $G-v$ to obtain the subtrees of $v$. The graph associahedron of $G$ is a polytope whose vertices correspond to elimination trees of $G$ and whose edges correspond to tree rotations, a natural operation between elimination trees. These objects generalize associahedra, which correspond to the case where $G$ is a path. Ito et al. [ICALP 2023] recently proved that the problem of computing distances on graph associahedra is NP-hard. In this talk we will show that the problem, for a general graph $G$, is fixed-parameter tractable parameterized by the distance $k$. Prior to our work, only the case where $G$ is a path was known to be fixed-parameter tractable. To prove our result, we use a novel approach based on a marking scheme that restricts the search to a set of vertices whose size is bounded by a (large) function of $k$.

TBA

TBA

TBA