David Lubicz

Accueil     Publications     Presentations     Themes

List of publications

Research papers

Computing Isogenies Between Abelian Varieties. David Lubicz, Damien Robert Compositio, 2012

We describe an efficient algorithm for the computation of isogenies between abelian varieties represented in the coordinate system provided by algebraic theta functions. We explain how to compute all the isogenies from an abelian variety whose kernel is isomorphic to a given abstract group. We also describe an analog of Vélu's formulas to compute an isogeny with a prescribed kernel. All our algorithms rely in an essential manner on a generalization of the Riemann formulas.

In order to improve the efficiency of our algorithms, we introduce a point compression algorithm that represents a point of level $4\ell$ of a $g$ dimensional abelian variety using only $g(g+1)/2\cdot 4^g$ coordinates. We also give formulas to compute the Weil and commutator pairing given input points in theta coordinates. All the algorithms presented in this paper work in general for any abelian variety defined over a field of odd characteristic.


Computing modular correspondances for abelian varieties. Jean-Charles Faugère, David Lubicz, Damien Robert Journal of Algebra, 2011

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.


Efficient Pairing Computation With Theta Functions. ANTS IX, 2010

In this paper, we present a new approach based on theta functions to compute Weil and Tate pairings. A benefit of our method, which does not rely on the classical Miller's algorithm, is its generality since it extends to all abelian varieties the classical Weil and Tate pairing formulas. In the case of dimension $1$ and $2$ abelian varieties our algorithms lead to implementations which are efficient and naturally deterministic. We also introduce symmetric Weil and Tate pairings on Kummer varieties and explain how to compute them efficiently. We exhibit a nice algorithmic compatibility between some algebraic groups quotiented by the action of the automorphism $-1$, where the $\Z$-action can be computed efficiently with a Montgomery ladder type algorithm.

On the security of oscillator-based random number generators. Mathieu Baudet, David Lubicz, Julien Micolod, André Tassiaux Journal of Cryptology, 2010

Physical random number generators (a.k.a. TRNGs) appear to be critical components of many cryptographic systems. Yet, such building blocks are still too seldom provided with a formal assessment of security, in comparison to what is achieved for conventional cryptography. In this work, we present a comprehensive statistical study of TRNGs based on the sampling of an oscillator subject to phase noise (a.k.a. phase jitters). This classical layout, typically instantiated with a ring oscillator, provides a simple and attractive way to implement a TRNG on a chip. Our mathematical study allows one to evaluate and control the main security parameters of such a random source, including its entropy rate and the biases of certain bit patterns, provided that a small number of physical parameters of the oscillator are known. In order to evaluate these parameters in a secure way, we also provide an experimental method for filtering out the global perturbations affecting a chip and possibly visible to an attacker. Finally, from our mathematical model, we deduce specific statistical tests applicable to the bit stream of a TRNG. In particular, in the case of an insecure configuration, we show how to recover the parameters of the underlying oscillator.

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

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.


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, 2008

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, 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, 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.

Preprints

Linear Algebra over $\Z_p[[u]]$ and related rings} . Xavier Caruso, David Lubicz preprint

Let R be a complete discrete valuation ring, S=R[[u]] and $n$ a positive integer. The aim of this paper is to explain how to compute efficiently usual operations such as sum and intersection of sub-$\mS$-modules of $\mS^n$. As $\mS$ is not principal, it is not possible to have a uniform bound on the number of generators of the modules resulting of the preceding operations. We explain how to mitigate this problem, following an idea of Iwasawa, by computing an approximation of the result of this operation up to a quasi-isomorphism. In the course of the analysis of the $p$-adic and $u$-adic precision of the computations, we have to introduce more general coefficient rings that may be interesting for their own sake. Being able to perform linear algebra operations modulo quasi-isomorphism with $\mS$-modules has applications in Iwasawa theory and $p$-adic Hodge theory.

Un algorithme de calcul de réseaux dans les représentations semi-stables. Xavier Caruso, David Lubicz preprint

The aim of this paper is to obtain an algorithm the complexity of which is polynomial in order to compute the semi-simplified modulo p of a semi-stable Q_p-representation of the absolute Galois group of a p-adic field. In order to do so, we make an essential use of the p-adic Hodge theory and in particulier of the theory of Breuil-Kisin modules.

A generalisation of Miller's algorithm and applications to pairing computations. David Lubicz, Damien Robert preprint

In this paper we use the theory of theta functions to generalise to all abelian varieties the usual Miller's algorithm to compute a function associated to a principal divisor. We also explain how to use the Frobenius morphism on abelian varieties defined over a finite field in order to shorten the loop of the Weil and Tate pairings algorithms. This extend preceding results about Ate pairings to all abelian varieties. Then we use the two preceding ingredients to obtain a variant of optimal pairings on abelian varieties. We compare in term of performance the resulting algorithms to the algorithms already known in the genus one and two case.

Towards an oscillator based TRNG with a certified entropy rate. David Lubicz, Nathalie Bochard preprint

We describe a practical and efficient method to measure the entropy rate of a TRNG based on free running oscillators that does not require to output and analyse the clock signals with an external device. It rather relies on very simple computations, that can be embedded into any FPGA or ASIC with minor adaptation of classical designs. It can be used for the calibration of an oscillator based TRNG or to certify the entropy rate of a TRNG while in operation. Our approach, which is inspired by the coherent sampling method, works under the general hypothesis that the phase jitter is small compared to the period of the oscillators. In this case, we show that it is possible to measure the relative phase between two oscillators with a precision far higher than the time resolution given by the period of any internal clock signal. We use this observation to recover, under some reasonable heuristics, the distribution of the random walk component of the phase jitter from which it is possible to compute a lower bound of the entropy rate of the TRNG. Our method has been thoroughly tested with simulations and hardware implementations. We draw some conclusions and recommendations for a reliable implementation of TRNGs to be used for cryptographic applications.

A Secure Key Management Interface with Asymmetric Cryptography. Marion Daubignard, David Lubicz, Graham Steel preprint

Cryptographic devices such as Hardware Security Modules are only as secure as their application programming interfaces (APIs) that offer cryptographic functionality to the outside world. Design flaws and implementation errors in security APIs have been shown to cause vulnerabilities that may leak secrets such as keys and PINs. Ideally, we would like to design such interfaces in such a way that we can formally prove security properties, even in the presence of some corrupted keys. In this work, we propose the first such provably secure interface to support asymmetric key operations for key management: Cachin and Chandran's secure token interface supports asymmetric key operations only for encrypting and signing data, but not for managing keys, while Cortier and Steel handle only symmetric keys. Due to the fact that anyone can encrypt under a public key, in order to secure integrity of the keys under management, we must consider confidentiality and integrity properties separately and provide support for classical operations of public key infrastructure (e.g. certification of public keys).

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.


Manuscripts

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$.