CWI Cryptology Group

Abstract: In order to bound the rank of the group of rational points A(k) on an abelian variety A over a number field k, one often does a 2-descent to bound the order of the finite group A(k)/2A(k). This group injects into H^1(k,A[2]), where A[2] denotes the group of 2-torsion points. The elements of this galois cohomological group correspond to certain twists of A, which are varieties over k that become isomorphic to A over the algebraic closure of k. Such a twist is in the image of A(k)/2A(k) if and only if it contains a rational point. In this talk I will first explain how twists correspond to cocyles. then I will show how to find explicit equations of these twists as the intersection of 72 quadrics in P^15 in the case that A is the Jacobian of a curve of genus 2.

Abstract: This talk addresses the problem of inverting the RSA function and the problem of factorizing integers. We relax these problems in several ways and show that the relaxations lead to polynomial time solvable problems. In this approach, we model the relaxed problems as polynomial equations which have roots of small size. The roots are then found by a method originally introduced by D. Coppersmith in 1996, which in turn is based on the famous LLL lattice reduction algorithm.
We also present a novel application for RSA with so-called small CRT exponents. Namely, we show that the factorization of an RSA modulus N=pq can be found in polynomial time provided that RSA is used with a secret exponent d such that both d (mod p-1) and d (mod q-1) are smaller than N^0.073. The existence of such a polynomial time attack answers a long-standing open problem by Wiener.

Abstract: In recent years, the Weil and Tate pairings on abelian varieties over finite fields have been used to construct a vast number of new and useful cryptosystems. The abelian varieties used in these systems must have small embedding degree with respect to a large prime-order subgroup. Such ``pairing-friendly'' abelian varieties are rare and thus require specific constructions.
In this talk we describe our two recent contributions to the catalogue of pairing-friendly abelian varieties: ordinary elliptic curves of prime order with embedding degree 10, and ordinary abelian surfaces over $\mathbb{F}_q$ having arbitrary embedding degree with respect to a prime subgroup of order roughly $q^{1/4}$. Both results require finding curves with complex multiplication by a specified CM field; making this step feasible while maintaining the pairing-friendly property is the difficult part of such constructions.