The Cryptography & Graphs Research Group (C&G) in Universitat de Lleida constitutes a well-established research team with a track record of more than 10 years of scientific activities. The team members in the C&G group are part of the Department of Mathematics and the Polytechnic Institute of Research and Innovation in Sustainability (InsPIReS). Most members of the C&G group teach in the degree and the master of Computer Science at the Escola Politècnica Superior (EPS).
The research interests of the members in the C&G group lie between theory and applications, mainly in the following two areas: Cryptography and Graph Theory. In the area of Cryptography, our research focuses on computational aspects of algebraic curve cryptography and design of secure cryptographic protocols for RFID technology, smart cards and e-voting systems. In the area of Graph Theory, our research concerns open problems on dense and eccentric digraphs, extremal problems and privacy-preserving social network data analysis. [Més informació]
(Elsevier, 2018) Fouquet, Mireille; Miret, Josep M. (Josep Maria); Valera Martín, Javier
Volcanoes of ℓ–isogenies of elliptic curves are a special case of graphs
with a cycle called crater. In this paper, given an elliptic curve E of a
volcano of ℓ–isogenies, we present a condition over an endomorphism ϕ of
E in order to determine which ℓ–isogenies of E are non-descending. The
endomorphism ϕ is defined as the crater cycle of an m–volcano where E
is located, with m 6= ℓ. The condition is feasible when ϕ is a distortion
map for a subgroup of order ℓ of E. We also provide some relationships
among the crater sizes of volcanoes of m–isogenies whose elliptic curves
belong to a volcano of ℓ–isogenies.
(Springer International Publishing Switzerland, 2015) Fouquet, Mireille; Miret, Josep M. (Josep Maria); Valera Martín, Javier
Given an ordinary elliptic curve over a finite field located in
the floor of its volcano of ℓ-isogenies, we present an efficient procedure
to take an ascending path from the floor to the level of stability and
back to the floor. As an application for regular volcanoes, we give an
algorithm to compute all the vertices of their craters. In order to do this,
we make use of the structure and generators of the ℓ-Sylow subgroups of
the elliptic curves in the volcanoes.
In recent years, several lightweight cryptographic protocols whose security lies in the
assumed intractability of the learning parity with noise (LPN) problem have been proposed.
The LPN problem has been shown to be solvable in subexponential time by algorithms that
have very large (subexponential) memory requirements, which limits their practical applicability.
When the memory resources are constrained, a brute-force search is the only
known way of solving the LPN problem. In this paper, we propose a new parallel implementation,
called Parallel-LPN, of an enhanced algorithm to solve the LPN problem. We
implemented the Parallel-LPN in C and MPI (Message Passing Interface), and it was tested
on a cluster system, where we obtained a quasi-linear speedup of approximately 90%. We
also proposed a new algorithm by using combinatorial objects that enhances the ParallelLPN
performance and its serial version.
(Australian Computer Society Inc, 2008) Miret, Josep M. (Josep Maria); Tomàs, Rosana; Valls Marsal, Magda; Sadornil Renedo, Daniel; Tena Ayuso, Juan
The security of most elliptic curve cryptosystems is based on the intractability of the Elliptic Curve
Discrete Logarithm Problem (ECDLP). Such a problem turns out to be computationally unfeasible
when elliptic curves are suitably chosen. This paper provides an algorithm to obtain cryptographically
good elliptic curves from a given one. The core of such a procedure lies on the usage
of successive chains of isogenies, visiting different volcanoes of isogenies which are located in
(Springer Verlag, 2015) Miret, Josep M. (Josep Maria); Pujolàs Boix, Jordi; Valera Martín, Javier
Let E be an elliptic curve defined over a finite field Fq of odd
characteristic. Let l≠2 be a prime number different from the characteristic and dividing #E(Fq). We describe how the l-adic valuation of the number of points grows by taking finite extensions of the base field. We also investigate the group structure of the corresponding l-Sylow subgroups.