Description
The problem of computing the zeta function of a variety over a finite field has attracted considerable interest in recent years, motivated in part by an application in cryptography. (In less fancy language, the problem is just to compute the number of solutions to a system of polynomial equations over a finite field.) I will discuss a new algorithm for computing zeta functions which is based upon relative p-adic cohomology. The idea is that to compute the zeta function of a single projective hypersurface, say , one puts it in a one-dimensional family of hypersurfaces. As one moves through this family, the zeta function varies in a manner which is controlled by a differential equation. One can arrange matters so that one fibre in the family has an easily computed zeta function. By solving the differential equation locally around this fibre, and using a form of analytic continuation, one can now recover the zeta function of any fibre in the family. In particular, one gets the zeta function of the original hypersurface! The key point is that because the `deformation' from the original hypersurface to the easy one is one-dimensional, the complexity of this approach is largely independent of the dimension of the hypersurface. In fact, one gets a uniform dependence on the input size over all dimensions. This contrasts starkly with existing approaches, whose performance deteriorates as the dimension increases. I believe the talk should be of interest to both cryptographers and p-adic cohomologists.
Next sessions
-
Random lattices that are modules over the ring of integers
Speaker : Nihar Gargava - Institut de Mathématiques d'Orsay
We investigate the average number of lattice points within a ball where the lattice is chosen at random from the set of unit determinant ideal or modules lattices of some cyclotomic number field. The goal is to consider the space of such lattice as a probabilistic space and then study the distribution of lattice point counts. This is inspired by the connections of this problem to lattice-based[…]-
Cryptography
-
-
Schéma de signature à clé publique : Frobénius-UOV
Speaker : Gilles Macario-Rat - Orange
L'exposé présente un schéma de signature à clé publique post-quantique inspiré du schéma UOV et introduisant un nouvel outil : les formes de Frobénius. L'accent est mis sur le rôle et les propriétés des formes de Frobénius dans ce nouveau schéma : la simplicité de description, la facilité de mise en oeuvre et le gain inédit sur les tailles de signature et de clé qui bat RSA-2048 au niveau de[…] -
Yoyo tricks with a BEANIE
Speaker : Xavier Bonnetain - Inria
TBD-
Cryptography
-
Symmetrical primitive
-