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