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