David Lubicz

Accueil     Publications     Presentations     Themes

List of publications

Research papers

The arithmetic of characteristic 2 Kummer surface. Pierrick Gaudry, David Lubicz. Finite Fields and Applications, 2009.

The purpose of this paper is a description of a model of Kummer surfaces in characteristic 2, together with the associated formulas for the pseudo-group law. Since the classical model has bad reduction, a renormalization of the parameters is required, that can be justified using the theory of algebraic theta functions. The formulas that are obtained are very efficient and may be usefull in cryptographic applications. We also show that applying the same strategy to elliptic curves gives Montgomery-like formulas in odd characteristic that are of some interest, and we recover already known formulas by Stam in characteristic 2.

A p-adic quasi-quadratic point counting algorithm. Robert Carls, David Lubicz. Int. Math. Res. Not., 2008.

In this article we give an algorithm for the computation of the number of rational points on the Jacobian variety of a generic ordinary hyperelliptic curve defined over a finite field $\F_q$, which has $q$ elements, with time complexity $O(n^{2+o(1)})$, where $n=\log(q)$. In the latter complexity estimate the genus and the characteristic are assumed as fixed. We provide a detailed complexity analysis of the algorithm. A proof of the correctness will be published elsewhere because it is beyond the scope of this article.

Our algorithm forms a generalization of both, the AGM algorithm of J.-F. Mestre and the canonical lifting method of T. Satoh. We canonically lift a certain arithmetic invariant in terms of theta constants. The theta null values are computed with respect to a semi-canonical product theta structure of level $2p$ where $p=\mathrm{char}(\F_q)>2$.

The results of this paper suggest a global positive answer to the question whether there exists a quasi-quadratic time algorithm for the computation of the number of rational points of an ordinary abelian variety defined over a finite field.

Attribute-Based Broadcast Encryption Scheme Made Efficient. David Lubicz, Thomas Sirvent. Proc. of Advances in Cryptology- Africacrypt'08, 2008, Casablanca

In this paper, we describe a new broadcast encryption scheme for stateless receivers. The main difference between our scheme and the classical ones derived from the complete subtree paradigm is that the group of privileged users is described by attributes. Actually, some real applications have been described where the use of a more adaptable access structure brings more efficiency and ease of deployment. On the other side, the decryption algorithm in so far existing attribute-based encryption schemes adapted for broadcast applications is time-consuming for the receiver, since it entails the computation of a large number of pairings. This is a real drawback for broadcast applications where most of the technological constraints are on the receiver side.

Our scheme can be viewed as a way to benefit at the same time from the performance of decryption of the classical broadcast schemes and the management easiness provided by the use of a more adaptable data structure based on attributes. More precisely, our scheme allows one to select or revoke users by sending ciphertexts of linear size with respect to the number of attributes, which is in general far less than the number of users. We prove that our scheme is fully collusion secure in the generic model of groups with pairing.

Pseudo-random groups and related problems. David Lubicz, Thomas Sirvent. Identity-Based Cryptography, M. Joye et G. Neven, Cryptology and Information Security Series, IOS Press

Family of groups with pairing are now considered as standard building blocks for cryptographic primitives. The security of schemes based on such groups relies on some hypotheses related to the discrete logarithm problem. As these hypotheses are not proved, one would like to have some positive security argument for these problems. It is usual to assess their security in the so called generic group model introduced by Nechaev and Shoup. The relevance of this model is nevertheless subject to criticisms: in particular, the fact that the answer to any fresh query is a random bit string is not what one expects from a usual group law. In order to improve this model, we introduce the notion of pseudo-random family of groups. We show how to reduce the security of a problem in a pseudo-random family of groups to the security of the same problem in the generic group model and the security of an underlying strong pseudo-random family of permutations.

Higher dimensional 3-adic CM construction. Robert Carls, David Kohel, David Lubicz. J. of Algebra, 319(4)971-2006, 2008.

We outline a method for the construction of genus $2$ hyperelliptic curves over small degree number fields whose Jacobian has complex multiplication and good ordinary reduction at the prime $3$. We prove the existence of a quasi-quadratic time algorithm for computing a canonical lift in characteristic $3$ based on equations defining a higher dimensional analogue of the classical modular curve $X_0(3)$. We give a detailed description of our method in the special case of genus $2$.

On a classification of finite statistical tests. David Lubicz. Adv. Math. of Com., 1(4):509-524, 2007.

Statistical tests of random sequences are often used in cryptography in order to perform some routine checks for random and pseudo-random number generators. Most of the test suites available are based on the theory of hypothesis testing which allows one to decide whether a sample has been drawn following a certain distribution. In this article, we develop a theoretical foundation of statistical tests of random sequences and hypothesis testing with a focus on cryptographic applications and we draw some interesting practical consequences.

A quasi-quadratic time algorithm for hyperelliptic curve point counting. Reynald Lercier and David Lubicz. Ramanujan J., 12(3):399-423, 2006.

We describe an algorithm to compute the cardinality of Jacobians of ordinary hyperelliptic curves of small genus over finite fields F_2^n with cost O(n^{2+o(1)}). This algorithm is derived from ideas due to Mestre. More precisely, we state the mathematical background behind Mestre's algorithm and develop from it a variant with quasi-quadratic time complexity. Among others, we present an algorithm to find roots of a system of generalized Artin-Schreier equations and give results that we obtain with an efficient implementation. Especially, we were able to obtain the cardinality of curves of genus one, two or three in finite fields of huge size.

Counting points in elliptic curves over finite fields of small characteristic in quasi quadratic time. Reynald Lercier and David Lubicz. Advances in cryptology-EUROCRYPT 2003, 360-373, Lecture Notes in Comput. Sci., 2656, Springer, Berlin, 2003.

Let $p$ be a small prime and $q=p^n$. Let $E$ be an elliptic curve over $\F_q$. We propose an algorithm which computes without any preprocessing the $j$-invariant of the canonical lift of $E$ with the cost of $O(\log n)$ times the cost needed to compute a power of the lift of the Frobenius. Let $\mu$ be a constant so that the product of two $n$-bit length integers can be carried out in $O(n^\mu)$ bit operations, this yields an algorithm to compute the number of points on elliptic curves which reaches, at the expense of a $O(n^{\frac{5}{2}})$ space complexity, a theoretical time complexity bound equal to $O(n^{\max(1.19, \mu)+\mu+\frac{1}{2}}\log n)$. When the field has got a Gaussian Normal Basis of small type, we obtain furthermore an algorithm with $O(\log(n)n^{2\mu})$ time and $O(n^2)$ space complexities. From a practical viewpoint, the corresponding algorithm is particularly well suited for implementations. We outline this by a 100002-bit computation.

Pencils of curves defined by a regular function. David Lubicz. Bull. Sci. Math. 125,no. 2, 139-160, 2001.

In this article, we generalize many results on the topology of a polynomial function, $f:C^2-> C$ in the case of a regular function $f:U-> C$.

Description of the cohomology of the complement of a nonreducible divisor. David Lubicz. Bull. Sci. Math. 124,no. 6, 447-458, 2000.

In this paper, we study the topology of the complement of an algebraic curve in $\proj_{\comp}^2$ by giving an explicit basis for the cohomology with complex coefficients. In particular, we obtain a upper bound for the pole order of such a basis which is better than the one describe in the works of P. Griffiths. We provide some examples in order to illustrate some results of comparison between the pole filtration and the Hodge filtration of the cohomology with complex coefficients.


A point counting algorithm using cohomology with compact support. Gweltaz Chatel, David Lubicz. Submited to LMS Journal of Computation and Mathematics

We describe an algorithm to count the number of rational points of an hyperelliptic curve defined over a finite field of odd characteristic which is based upon the computation of the action of the Frobenius morphism on a basis of the Monsky-Washnitzer cohomology with compact support. This algorithm follows the vein of a systematic exploration of potential application of cohomology theories to point counting.

Our algorithm decomposes in two steps. A first step which consists in the computation of a basis of the cohomology and then a second step to obtain a representation of the Frobenius morphism. Neglecting logarithmic terms, we achieve a O(g^4 n^3) time complexity and O(g^3 n^3) memory complexity where g is the genus of the curve and n is the absolute degree of its base field. We give a detailed complexity analysis of the algorithm as well as a proof of correctness.

Computing modular correspondances for abelian varieties. Jean-Charles Faugère, David Lubicz. preprint

The aim of this paper is to give a higher dimensional equivalent of the classical modular polynomials $\Phi_\ell(X,Y)$. If $j$ is the $j$-invariant associated to an elliptic curve $E_k$ over a field $k$ then the roots of $\Phi_\ell(j,X)$ correspond to the $j$-invariants of the curves which are $\ell$-isogeneous to $E_k$. Denote by X_0(N) the modular curve which parametrizes the set of elliptic curves together with a $N$-torsion subgroup. It is possible to interpret \Phi_\ell(X,Y) as an equation cutting out the image of a certain modular correspondence X_0(\ell) \rightarrow X_0(1) \times X_0(1) in the product X_0(1) \times X_0(1).

Let g be a positive integer and \overline{n} \in \N^g. We are interested in the moduli space that we denote by \mathcal{M}_{\overline{n}} of abelian varieties of dimension g over a field k together with an ample symmetric line bundle \pol and a theta structure of type \overline{n}. If \ell is a prime and let \overline{\ell}=(\ell, \ldots , \ell), there exists a modular correspondence \mathcal{M}_{\overline{\ell n}} \rightarrow \mathcal{M}_{\overline{n}} \times \mathcal{M}_{\overline{n}}. We give a system of algebraic equations defining the image of this modular correspondence.

We describe an algorithm to solve this system of algebraic equations which is much more efficient than a general purpose Groebner basis algorithms. As an application, we explain how this algorithm can be used to speed up the initialisation phase of a point counting algorithm.

Chapters of books

Random numbers generation and testing. Tanja Lange, David Lubicz, Andrew Weigl. Handbook of elliptic and hyperelliptic curve cryptography, 715--735, Discrete Math. Appl. (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006.

Point counting on elliptic and hyperelliptic curves. Reynald Lercier, David Lubicz, Frederik Vercauteren. Handbook of elliptic and hyperelliptic curve cryptography, 407--453, Discrete Math. Appl. (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006.

Cohomological background on point counting. David Lubicz, Frederik Vercauteren. Handbook of elliptic and hyperelliptic curve cryptography, 133--141, Discrete Math. Appl. (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006.

Background on $p$-adic numbers. David Lubicz. Handbook of elliptic and hyperelliptic curve cryptography, 39--44, Discrete Math. Appl. (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006.

Algebraic background. Christophe Doche, David Lubicz. Handbook of elliptic and hyperelliptic curve cryptography, 19--37, Discrete Math. Appl. (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006.


Quelques aspects algorithmiques de la cryptographie. David Lubicz. [French] Mémoire d'Habilitation à Diriger des Recherches.

Asymmetric cryptography, invented in the seventies by W. Diffie and M. Hellman, brings a large number of features to the more classical symmetric cryptography which are particularly interesting for practical applications. Most of the time, its operation relies on the computational hardness of some problems coming from number theory. From this, it is possible to deduce one-way functions, trap-door functions and then design and prove by reduction protocols to achieve a variety of security objectives among which the most common are encryption or digital signature.

A problem classically used in asymmetric cryptography is the discrete logarithm problem which is for instance a corner stone for all the elliptic curve cryptography. The discrete logarithm problem allows one to design supposed to be one-way functions from a family of groups enjoying certain good properties. In the dissertation, we present some techniques to define, represent and compute family of groups to be used in discrete logarithm based cryptosystems. Security and performance issues leads us to revisit from a computational point of view some concepts developed during the sixties for the purpose of number theory and arithmetic geometry : complex multiplication, algebraic theta functions, rigid cohomology and Serre-Tate theory are worth mentioning.

Les tests statistiques en cryptographie. David Lubicz. [French] preprint.

The object of this document is to give a definition of what is a random sequence and to justify tests in order to ensure that a random number generator or a pseudo-random number generator is working properly.

Mémoire de thèse.. David Lubicz. [French] Thèse de l'Université Bordeaux I.

In this thesis, we are interested by the topology of the complement $U=\proj^2 \backslash C$, which is a smooth affine surface. In the first chapter, we decuce explicit bases for cohomology groups with complex coefficients, $H^i(U)$ with $i=1,2$, knowing bases for thes groups $H^i(U_j)$ where $U_j=\proj^2 \backslash C_j$. In the second chapter, we generalize a lot of results about the topology of a polynomial fonction, $f: \comp^2 \rightarrow \comp$ in the case of a regular fonction $f:U \rightarrow \comp$.