Vector oblivious linear evaluation, or VOLE, has recently been shown to be a useful tool for designing efficient zero-knowledge proof systems that can scale to large statements with a low memory footprint (Yang et al. CCS 2021, Baum et al. CRYPTO 2021). While most ZK protocols require statements to be expressed in terms of arithmetic operations over a single finite field, recent works in VOLE-based ZK have shown how to mix Boolean and arithmetic operations in a single statement, through conversions between different finite fields (Baum et al. CCS 2021, Weng et al. USENIX 2021).

We present new, lightweight protocols for arithmetic/Boolean conversions in VOLE-based ZK. In contrast to previous works, which rely on an expensive cut-and-choose method, we take a new approach that leverages the ability of recent proof systems to prove high-degree polynomial constraints, and combines this with specialized low-degree pseudorandom generators. This not only simplifies conversions, but we showcase how it also improves the concrete efficiency of tasks important in practical ZK protocols of complex statements, including fixed point arithmetic, comparison and range proofs.

Joint work with Amit Agarwal (currently visiting IRIF), Carsten Baum, and Peter Scholl. To be presented at Eurocrypt 2025.

Regular word grammars are context-free grammars having restricted rules, that define all recognizable languages of words. This paper generalizes regular grammars from words to certain classes of graphs, by defining regular grammars for unordered unranked trees and graphs of tree-width 2 at most. The qualifier ``regular'' is justified because these grammars define precisely the recognizable (equivalently, CMSO-definable) sets of the respective graph classes. The proof of equivalence between regular and recognizable sets of graphs relies on the effective construction of a recognizer algebra of size doubly-exponential in the size of the grammar. This sets a 2EXPTIME upper bound on the (EXPTIME-hard) problem of inclusion of a context-free language in a regular language, for graphs of tree-width 2 at most. A further syntactic restriction of regular grammars suffices to capture precisely the MSO-definable sets of graphs of tree-width 2 at most, i.e., the sets defined by CMSO formulae without cardinality constraints. Moreover, we show that MSO-definability coincides with recognizability by algebras having an aperiodic parallel composition semigroup, for each class of graphs defined by a bound on the tree-width.

Les circuits reconfigurables FPGA (Field-Programmable Gate Arrays) constituent une cible de choix pour la mise en œuvre d'architectures matérielles spécialisées : ils exposent du parallélisme à grain très fin et offrent un accès direct au monde physique via des broches d'entrées/sorties.

Dans cet exposé, je présenterai un modèle de programmation pour mélanger calcul et interaction sur FPGA. Ce modèle de programmation permet de composer à la fois des comportements réactifs orientés flot de données et des calculs parallèles en mémoire partagée, avec de la concurrence déterministe et des performances prédictibles. Il s'est avéré suffisamment expressif pour développer des environnements d'exécution sur mesure, comme par exemple, une implémentation matérielle de la machine virtuelle OCaml ainsi qu'une bibliothèque d'exécution simplifiée pour OCaml (incluant un gestionnaire automatique de mémoire) avec appel d'accélérateurs via la FFI.

We present a complete characterization of two non-integers with the same Rényi-Parry measure. We prove that for two non-integers $\beta_1 ,\beta_2 >1$, the Rényi-Parry measures coincide if and only if $\beta_1$ is the root of equation $x^2-qx-p=0$, where $p,q\in\mathbb{N}$ with $p\leq q$, and $\beta_2 = \beta_1 + 1$, which confirms a conjecture of Bertrand-Mathis in [A. Bertrand-Mathis, Acta Math. Hungar. 78, no. 1-2 (1998):71–78].

Continuation of part I. I intend to cover

1. applications of WQOs in algorithmic graph theory,
2. a focus on classes of graphs that are well-quasi-ordered by the induced subgraph ordering, along with Pouzet’s Conjecture,
3. the generalisation to preservation properties in first-order logic.