Shadow lines in the arithmetic of elliptic curves

Let E/Q be an elliptic curve and p a rational prime of good ordinary reduction. For every imaginary quadratic field K/Q satisfying the Heegner hypothesis for E we have a corresponding line in E(K)\otimes Q_p, known as a shadow line. When E/Q has analytic rank 2 and E/K has analytic rank 3, shadow lines are expected to lie in E(Q)\otimes Qp. If, in addition, p splits in K/Q, then shadow lines can be determined using the anticyclotomic p-adic height pairing. We develop an algorithm to compute anticyclotomic p-adic heights which we then use to provide an algorithm to compute shadow lines. We conclude by illustrating these algorithms in a collection of examples.

Um algoritmo de criptografia de chave pública semanticamente seguro baseado em curvas elípticas

Esta dissertação apresenta o desenvolvimento de um novo algoritmo de criptografia de chave pública. Este algoritmo apresenta duas características que o tornam único, e que foram tomadas como guia para a sua concepção. A primeira característica é que ele é semanticamente seguro. Isto significa que nenhum adversário limitado polinomialmente consegue obter qualquer informação parcial sobre o conteúdo que foi cifrado, nem mesmo decidir se duas cifrações distintas correspondem ou não a um mesmo conteúdo. A segunda característica é que ele depende, para qualquer tamanho de texto claro, de uma única premissa de segurança: que o logaritmo no grupo formado pelos pontos de uma curva elíptica de ordem prima seja computacionalmente intratável. Isto é obtido garantindo-se que todas as diferentes partes do algoritmo sejam redutíveis a este problema. É apresentada também uma forma simples de estendê-lo a fim de que ele apresente segurança contra atacantes ativos, em especial, contra ataques de texto cifrado adaptativos. Para tanto, e a fim de manter a premissa de que a segurança do algoritmo seja unicamente dependente do logaritmo elíptico, é apresentada uma nova função de resumo criptográfico (hash) cuja segurança é baseada no mesmo problema.

Criptografia e curvas elípticas

Pós-graduação em Matemática Universitária - IGCE

Euler characteristics and elliptic curves

Let E be a modular elliptic curve over ℚ, without complex multiplication; let p be a prime number where E has good ordinary reduction; and let F∞ be the field obtained by adjoining to ℚ all p-power division points on E. Write G∞ for the Galois group of F∞ over ℚ. Assume that the complex L-series of E over ℚ does not vanish at s = 1. If p ⩾ 5, we make a precise conjecture about the value of the G∞-Euler characteristic of the Selmer group of E over F∞. If one makes a standard conjecture about the behavior of this Selmer group as a module over the Iwasawa algebra, we are able to prove our conjecture. The crucial local calculations in the proof depend on recent joint work of the first author with R. Greenberg.

Deniable Authenticated Key Establishment for Internet Protocols

We propose two public-key schemes to achieve “deniable authentication” for the Internet Key Exchange (IKE). Our protocols can be implemented using different concrete mechanisms and we discuss different options; in particular we suggest solutions based on elliptic curve pairings. The protocol designs use the modular construction method of Canetti and Krawczyk which provides the basis for a proof of security. Our schemes can, in some situations, be more efficient than existing IKE protocols as well as having stronger deniability properties.

Jacobi quartic curves revisited

This paper provides new results about efficient arithmetic on Jacobi quartic form elliptic curves, y 2 = d x 4 + 2 a x 2 + 1. With recent bandwidth-efficient proposals, the arithmetic on Jacobi quartic curves became solidly faster than that of Weierstrass curves. These proposals use up to 7 coordinates to represent a single point. However, fast scalar multiplication algorithms based on windowing techniques, precompute and store several points which require more space than what it takes with 3 coordinates. Also note that some of these proposals require d = 1 for full speed. Unfortunately, elliptic curves having 2-times-a-prime number of points, cannot be written in Jacobi quartic form if d = 1. Even worse the contemporary formulae may fail to output correct coordinates for some inputs. This paper provides improved speeds using fewer coordinates without causing the above mentioned problems. For instance, our proposed point doubling algorithm takes only 2 multiplications, 5 squarings, and no multiplication with curve constants when d is arbitrary and a = ±1/2.

Multi-ciphersuite security of the Secure Shell (SSH) protocol

The Secure Shell (SSH) protocol is widely used to provide secure remote access to servers, making it among the most important security protocols on the Internet. We show that the signed-Diffie--Hellman SSH ciphersuites of the SSH protocol are secure: each is a secure authenticated and confidential channel establishment (ACCE) protocol, the same security definition now used to describe the security of Transport Layer Security (TLS) ciphersuites. While the ACCE definition suffices to describe the security of individual ciphersuites, it does not cover the case where parties use the same long-term key with many different ciphersuites: it is common in practice for the server to use the same signing key with both finite field and elliptic curve Diffie--Hellman, for example. While TLS is vulnerable to attack in this case, we show that SSH is secure even when the same signing key is used across multiple ciphersuites. We introduce a new generic multi-ciphersuite composition framework to achieve this result in a black-box way.

Post-quantum key exchange for the TLS protocol from the ring learning with errors problem

Lattice-based cryptographic primitives are believed to offer resilience against attacks by quantum computers. We demonstrate the practicality of post-quantum key exchange by constructing cipher suites for the Transport Layer Security (TLS) protocol that provide key exchange based on the ring learning with errors (R-LWE) problem, we accompany these cipher suites with a rigorous proof of security. Our approach ties lattice-based key exchange together with traditional authentication using RSA or elliptic curve digital signatures: the post-quantum key exchange provides forward secrecy against future quantum attackers, while authentication can be provided using RSA keys that are issued by today's commercial certificate authorities, smoothing the path to adoption. Our cryptographically secure implementation, aimed at the 128-bit security level, reveals that the performance price when switching from non-quantum-safe key exchange is not too high. With our R-LWE cipher suites integrated into the Open SSL library and using the Apache web server on a 2-core desktop computer, we could serve 506 RLWE-ECDSA-AES128-GCM-SHA256 HTTPS connections per second for a 10 KiB payload. Compared to elliptic curve Diffie-Hellman, this means an 8 KiB increased handshake size and a reduction in throughput of only 21%. This demonstrates that provably secure post-quantum key-exchange can already be considered practical.

Solutions of cubic equations in quadratic fields

Let K be any quadratic field with O-K its ring of integers. We study the solutions of cubic equations, which represent elliptic curves defined over Q, in quadratic fields and prove some interesting results regarding the solutions by using elementary tools. As an application we consider the Diophantine equation r + s + t = rst = 1 in O-K. This Diophantine equation gives an elliptic curve defined over Q with finite Mordell-Weil group. Using our study of the solutions of cubic equations in quadratic fields we present a simple proof of the fact that except for the ring of integers of Q(i) and Q(root 2), this Diophantine equation is not solvable in the ring of integers of any other quadratic fields, which is already proved in [4].

Fault Attacks on Pairing-Based Protocols Revisited

Several papers have studied fault attacks on computing a pairing value e(P, Q), where P is a public point and Q is a secret point. In this paper, we observe that these attacks are in fact effective only on a small number of pairing-based protocols, and that too only when the protocols are implemented with specific symmetric pairings. We demonstrate the effectiveness of the fault attacks on a public-key encryption scheme, an identity-based encryption scheme, and an oblivious transfer protocol when implemented with a symmetric pairing derived from a supersingular elliptic curve with embedding degree 2.

基于椭圆曲线的代理多签名方案的安全性分析

在一个安全的代理签名方案中，只有指定的代理签名人能够代表原始签名人生成代理签名．基于椭圆曲线离散对数问题，纪家慧和李大兴提出了一个代理签名方案和一个代理多签名方案，陈泽雄等人给出了另外两个代理多签名方案．但是，在他们的方案中，原始签名人能够伪造代理签名私钥．为了抵抗原始签名人的伪造攻击，改进了代理签名密钥的生成过程，并对改进的方案进行了安全性分析．

FPGA montgomery modular multiplication architectures suitable for ECCs over GF(p)

New FPGA architectures for the ordinary Montgomery multiplication algorithm and the FIOS modular multiplication algorithm are presented. The embedded 18×18-bit multipliers and fast carry look-ahead logic located on the Xilinx Virtex2 Pro family of FPGAs are used to perform the ordinary multiplications and additions/subtractions required by these two algorithms. The architectures are developed for use in Elliptic Curve Cryptosystems over GF(p), which require modular field multiplication to perform elliptic curve point addition and doubling. Field sizes of 128-bits and 256-bits are chosen but other field sizes can easily be accommodated, by rapidly reprogramming the FPGA. Overall, the larger the word size of the multiplier, the more efficiently it performs in terms of area/time product. Also, the FIOS algorithm is flexible in that one can tailor the multiplier architecture is to be area efficient, time efficient or a mixture of both by choosing a particular word size. It is estimated that the computation of a 256-bit scalar point multiplication over GF(p) would take about 4.8 ms.

Mersenne numbers

These notes have been issued on a small scale in 1983 and 1987 and on request at other times. This issue follows two items of news. First, WaIter Colquitt and Luther Welsh found the 'missed' Mersenne prime M110503 and advanced the frontier of complete Mp-testing to 139,267. In so doing, they terminated Slowinski's significant string of four consecutive Mersenne primes. Secondly, a team of five established a non-Mersenne number as the largest known prime. This result terminated the 1952-89 reign of Mersenne primes. All the original Mersenne numbers with p < 258 were factorised some time ago. The Sandia Laboratories team of Davis, Holdridge & Simmons with some little assistance from a CRAY machine cracked M211 in 1983 and M251 in 1984. They contributed their results to the 'Cunningham Project', care of Sam Wagstaff. That project is now moving apace thanks to developments in technology, factorisation and primality testing. New levels of computer power and new computer architectures motivated by the open-ended promise of parallelism are now available. Once again, the suppliers may be offering free buildings with the computer. However, the Sandia '84 CRAY-l implementation of the quadratic-sieve method is now outpowered by the number-field sieve technique. This is deployed on either purpose-built hardware or large syndicates, even distributed world-wide, of collaborating standard processors. New factorisation techniques of both special and general applicability have been defined and deployed. The elliptic-curve method finds large factors with helpful properties while the number-field sieve approach is breaking down composites with over one hundred digits. The material is updated on an occasional basis to follow the latest developments in primality-testing large Mp and factorising smaller Mp; all dates derive from the published literature or referenced private communications. Minor corrections, additions and changes merely advance the issue number after the decimal point. The reader is invited to report any errors and omissions that have escaped the proof-reading, to answer the unresolved questions noted and to suggest additional material associated with this subject.

p-adic L functions and trivial zeroes

The following is adapted from the notes for the lecture. It announces results and conjectures about values of the p-adic L function of the symmetric square of an elliptic curve.

Adjoint modular Galois representations and their Selmer groups

In the last 15 years, many class number formulas and main conjectures have been proven. Here, we discuss such formulas on the Selmer groups of the three-dimensional adjoint representation ad(φ) of a two-dimensional modular Galois representation φ. We start with the p-adic Galois representation φ0 of a modular elliptic curve E and present a formula expressing in terms of L(1, ad(φ0)) the intersection number of the elliptic curve E and the complementary abelian variety inside the Jacobian of the modular curve. Then we explain how one can deduce a formula for the order of the Selmer group Sel(ad(φ0)) from the proof of Wiles of the Shimura–Taniyama conjecture. After that, we generalize the formula in an Iwasawa theoretic setting of one and two variables. Here the first variable, T, is the weight variable of the universal p-ordinary Hecke algebra, and the second variable is the cyclotomic variable S. In the one-variable case, we let φ denote the p-ordinary Galois representation with values in GL2(Zp[[T]]) lifting φ0, and the characteristic power series of the Selmer group Sel(ad(φ)) is given by a p-adic L-function interpolating L(1, ad(φk)) for weight k + 2 specialization φk of φ. In the two-variable case, we state a main conjecture on the characteristic power series in Zp[[T, S]] of Sel(ad(φ) ⊗ ν−1), where ν is the universal cyclotomic character with values in Zp[[S]]. Finally, we describe our recent results toward the proof of the conjecture and a possible strategy of proving the main conjecture using p-adic Siegel modular forms.