In this talk, we will then present a hardware co-processor designed to accelerate the computation of the Tate pairing in characteristics 2 and 3. As the title suggests, this talk will emphasize on reducing the silicon footprint or in our case the usage of FPGA resources of the circuit to ensure scalability, while trying to minimize the impact on the overall performances. In , Coppersmith introduced two lattice reduction based techniques to find small roots in polynomial equations.
One technique works for modular univariate polynomials, the other for bivariate polynomials over the integers. Since then, these methods have been used in a huge variety of cryptanalytic applications. Some applications also use extensions of Coppersmith's techniques on more variables. However, these extensions are heuristic methods.
In this presentation, we present and analyze a new variation of Coppersmith's algorithm on three variables over the integers. We also study the applicability of our method to short RSA exponents attacks. Moreover, at least in principle, it can be generalized to four or more variables. Since their introduction in constructive cryptographic applications, pairings over hyper elliptic curves are at the heart of an ever increasing number of protocols. Software implementations being rather slow, the study of hardware architectures became an active research area.
We then describe ways to extend our approach to any characteristic and any extension field. The talk will be based on the following research reports:. The question of which quaternion algebras may be obtained in this way is one of our motivations. For quaternion algebras to occur, the class group of K must have non-cyclic 2-Sylow subgroup, the simplest possible examples occuring when K has class number 4.
Construction of such defining polynomials for CM curves is an area of active interest for use in cryptographic constructions. In this talk I will report on recent progress and challenges in extending and improving these algorithms. We describe that algorithm and report on its implementation in NTL.
Abstract: We describe a new multi-level blocking algorithm for distinct-degree factorization of polynomials over GF 2. The idea of the algorithm is to use one level of blocking to replace most GCD computations by multiplications, and a finer level of blocking to replace most multiplications by squarings which are much faster than multiplications over GF 2. As an application we give an algorithm that searches for all irreducible trinomials of given degree.
Under plausible assumptions, the expected running time of this algorithm is much less than that of the classical algorithm. For example, our implementation gives a speedup of more than 60 over the classical algorithm for trinomials of degree a Mersenne exponent.
Isogenies — surjective homomorphisms of algebraic groups with finite kernel — are of great interest in number theory and cryptography. Algorithms for computing with isogenies of elliptic curves are well-known, but in higher dimensions, the situation is more complicated, and few explicit examples of non-trivial isogenies are known. We will discuss some of the computational issues, and describe some examples and applications of isogenies of Jacobians of hyperelliptic curves.
Digital signatures have the sometimes unwanted property of being universally verifiable by anybody having access to the signer's public key. In recent work with F. Laguillaumie and P. Pailler, we have proposed a signature scheme where the verification requires interaction with the signer. We present in this talk the underlying algorithmical problem within its cryptographical context, and give some assessment of its difficulty. The AGM can be interpreted using functions called theta constants. We show how this special case extends to higher genus, using a generalization of the AGM known as the Borchardt mean.
In particular, we develop an algorithm for computing genus 2 Riemann matrices in almost linear time.
This algorithm can be implemented easily. As we also show, this technique allows for rapid computation of modular forms and functions, and we discuss the applications thereof construction of CM curves, explicit computation of isogenies, …. B, slides: pdf kb. Since their first introduction as a cryptanalytic tool, bilinear pairings have moved to a very useful building block for cryptography.
Current real-world applications of pairings include remote attestation, privacy-preserving blockchains and identity-based cryptography. However, recent advances in the discrete log computation have reduced the efficiency of the most popular pairing constructions and previous candidates for standardization. This talk discusses ongoing work regarding the efficient implementation of new sets of parameters for bilinear groups, to adjust security against these recent attacks, and techniques for their realization in software.
Then, we assume that A and B are given in total degree and we consider the usual degree lexicographic order. Although the bases are not vanilla in this case, they admit a so-called concise representation with similar properties. In this talk we consider CSIDH, a new post-quantum key-exchange algorithm based on the hardness of constructing an unknown isogeny between two given elliptic curves.
We will describe some algorithmic improvements, and also some important relations between the underlying "hard" problems in both the quantum and classical worlds. I will conclude with several open problems that have been opened by this line of research. Friday September 7, Simon Abelard Caramba team Point-counting on hyperelliptic curves defined over finite fields of large characteristic: algorithms and complexities PhD defense C, There have been recent advances in solving the finite extension field discrete logarithm problem as it arises in the context of pairing-friendly elliptic curves.
This has lead to the abandonment of approaches based on supersingular curves of small characteristic, and to the reconsideration of the field sizes required for implementation based on non-supersingular curves of large characteristic. This has resulted in a revision of recommendations for suitable curves, particularly at a higher level of security. Indeed for AES levels of security the BLS48 curves have been suggested, and demonstrated to be superior to other candidates. These curves have an embedding degree of The well known taxonomy of Freeman, Scott and Teske only considered curves with embedding degrees up to Given some uncertainty around the constants that apply to the best discrete logarithm algorithm, it would seem to be prudent to push a little beyond In this note we announce the discovery of a new family of pairing friendly elliptic curves which includes a new construction for a curve with an embedding degree of Joint work with Michael Scott Miracl.
Tuesday June 5, Svyatoslav Covanov Caramba team Multiplication algorithms: bilinear complexity and fast asymptotic methods PhD defense C, In the same manner, Strassen's algorithm allows one to multiply two matrices 2 n x2 n with only seven products of matrices n x n. Among the most classical bilinear maps, we have the multiplication of polynomials, matrices, or even elements of algebraic extension of finite fields.
Given a bilinear map Phi , computing the minimal number of multiplications necessary to the evaluation of this map is a NP-hard problem. The purpose of this thesis is to propose algorithms minimizing this number of multiplications. Two angles of attack have been studied. The first aspect of this thesis is to study the problem of the computation of the bilinear complexity under the angle of the reformulation of this problem in terms of research of matrix subspaces of a given rank.
This work led to an algorithm taking into account intrinsic properties of the considered products such as matrix or polynomial products over finite fields.
This algorithm allows one to find all the possible decompositions, over F 2 , for the product of polynomials modulo X 5 and the product of matrices 3x2 by 2x3. Another aspect of this thesis was the development of fast asymptotic methods for the integer multiplication. In this thesis, an algorithm, relying on a number theoretical conjecture, has been proposed, involving the use of FFT and generalized Fermat primes.
In this talk, I will explain techniques to achieve fast and secure implementations. I will introduce a vector unit, which is a part of a CPU, and ways to utilize it. I will also briefly emphasize the importance of and ways to prevent software side-channel attacks. Karatsuba's method plays an important role in the former case, while combinations of Karatsuba's method and Toom--Cook's method are crucial in the latter case.
Both implementations utilize the CPU's vector unit. This talk focuses on the relation collection phase or harvesting in Index-Calculus algorithms to compute discrete logs in an algebraic curve.
I will present results from my thesis, improving two different types of harvesting. Second, when the target curve is defined over an extension of a finite field, the harvesting can be presented as the resolutions of multivariate systems.
When the curve is hyperelliptic and the field has characteristic two, we show that several equations in the involved systems are "squares". We then exploit this property to improve the asymptotic complexity of the harvesting phase. In term of practical difficulty, it compares to recent records over finite fields.
We study the geometry of units and ideals of cyclotomic rings, and derive an algorithm to find a mildly short vector in any given cyclotomic ideal lattice in quantum polynomial time, under some plausible number-theoretic assumptions. More precisely, it finds an approximation of the shortest vector by a subexponential factor. This result exposes an unexpected hardness gap between these structured lattices and general lattices: the best known polynomial time generic lattice algorithms can only reach an exponential approximation factor.
Following a recent series of attacks, these results call into question the hardness of various problems over structured lattices, such as Ideal-SVP and Ring-LWE, upon which relies the security of a number of cryptographic schemes.kygyxexe.ga
Monday December 11, Matthieu Rambaud Inria Saclay Dense families of curves over prime fields with many points after field extension B, The talk will recall facts on the descent of covering maps, and illustrate recent numerical methods of Sijsling-Voight. Wednesday July 5, Chloe Martindale Technical University of Eindhoven, Netherlands Isogeny graphs, modular polynomials, and point counting for higher genus curves.
A, We recap the theory of modular polynomials and isogeny graphs of ordinary elliptic curves and give a natural generalisation to abelian g -folds e. This is joint work with Marco Streng. We then recap the algorithm of Schoof, Elkies, and Atkin for efficient point counting on elliptic curves over finite fields, and show how to generalise the algorithm to genus 2 curves over finite fields with maximal real multiplication , using our generalisation of modular polynomials to genus 2. Under some heuristic assumptions, this is the fastest known algorithm to count points on genus 2 curves over large prime fields.
In this talk, we present recent results about fast algorithms for fundamental operations for matrices over K[X] univariate polynomials. We mainly focus on the computation of normal forms, obtained by transforming the input matrix via elementary row operations. Depending on a degree measure specified by a "shift", these normal forms range from the Hermite form, which is triangular, to the Popov form, which minimizes the degrees of the rows.
The last point will lead us to consider the problem of solving systems of linear modular equations over K[X], which generalizes Hermite-Pade approximation and rational reconstruction. Waterloo, ON, Canada. Groebner basis is an important tool in computational ideal theory, and the term ordering plays an important role in the theory of Groebner bases.
In particular, the common strategy to solve a polynomial system is to first compute the basis of the ideal defined by the system w. Thus it is of crucial importance to design efficient algorithms to perform the change of ordering.