# American Institute of Mathematical Sciences

ISSN:
1930-5346

eISSN:
1930-5338

All Issues

## Advances in Mathematics of Communications

2010 , Volume 4 , Issue 2

A special issue
CHiLE 2009

Select all articles

Export/Reference:

2010, 4(2): i-ii doi: 10.3934/amc.2010.4.2i +[Abstract](213) +[PDF](42.7KB)
Abstract:
The Conference on Hyperellptic Curves, Discrete Logarithms, Encryption, etc. took place March 16-20, 2009 in Frutillar, Chile. This event derives its acronym CHiLE 2009 from its Spanish title

Curvas Hiperelĺpticas, Logaritmos discretos, Encriptación, etc.

The goal of this conference was to bring together researchers working on cryptographic aspects of algebraic geometry from all over the world, and especially from South America. It was hoped that this would help promote the development and expansion of this field of research in South America.

For more information please click the "Full Text" above.

2010, 4(2): 101-114 doi: 10.3934/amc.2010.4.101 +[Abstract](263) +[PDF](217.1KB)
Abstract:
We survey the interaction between local and global theory for studying the arithmetic properties of curves, jacobians, and abelian varieties.
2010, 4(2): 115-139 doi: 10.3934/amc.2010.4.115 +[Abstract](278) +[PDF](300.5KB)
Abstract:
The aim of this paper is to reduce the number of operations in Cantor's algorithm for the Jacobian group of hyperelliptic curves for genus 4 in projective coordinates. Specifically, we developed explicit doubling and addition formulas for genus 4 hyperelliptic curves over binary fields with $h(x)=1$. For these curves, we can perform a divisor doubling in $63M+19S$, while the explicit adding formula requires $203M+18S,$ and the mixed coordinates addition (in which one point is given in affine coordinates) is performed in $165M+15S$.
These formulas can be useful for public key encryption in some environments where computing the inverse of a field element has a high computational cost (either in time, power consumption or hardware price), in particular with embedded microprocessors.
2010, 4(2): 141-154 doi: 10.3934/amc.2010.4.141 +[Abstract](211) +[PDF](196.9KB)
Abstract:
We investigate improvements to the algorithm for the computation of ideal class groups described by Jacobson in the imaginary quadratic case. These improvements rely on the large prime strategy and a new method for performing the linear algebra phase. We achieve a significant speed-up and are able to compute ideal class groups with discriminants of 110 decimal digits in less than a week.
2010, 4(2): 155-168 doi: 10.3934/amc.2010.4.155 +[Abstract](235) +[PDF](193.8KB)
Abstract:
We give an efficient explicit algorithm to find the structure and generators of the maximal 2-subgroup of the Jacobian of a genus 2 curve over a finite field of odd characteristic. We use the 2-torsion points as seeds to successively perform a chain of halvings to find divisors of increasing 2-power order. The halving loop requires a solution to certain degree 16 polynomials over the base field, and the termination of the algorithm is based on the description of the graph structure of the maximal 2-subgroup. The structure of our algorithm is the natural extension of the even characteristic case.
2010, 4(2): 169-187 doi: 10.3934/amc.2010.4.169 +[Abstract](644) +[PDF](304.4KB)
Abstract:
The deployment of cryptography in sensor networks is a challenging task, given the limited computational power and the resource-constrained nature of the sensoring devices. This paper presents the implementation of elliptic curve cryptography in the MICAz Mote, a popular sensor platform. We present optimization techniques for arithmetic in binary fields, including squaring, multiplication and modular reduction at two different security levels. Our implementation of field multiplication and modular reduction algorithms focuses on the reduction of memory accesses and appears as the fastest result for this platform. Finite field arithmetic was implemented in C and Assembly and elliptic curve arithmetic was implemented in Koblitz and generic binary curves. We illustrate the performance of our implementation with timings for key agreement and digital signature protocols. In particular, a key agreement can be computed in 0.40 seconds and a digital signature can be computed and verified in 1 second at the 163-bit security level. Our results strongly indicate that binary curves are the most efficient alternative for the implementation of elliptic curve cryptography in this platform.
2010, 4(2): 189-213 doi: 10.3934/amc.2010.4.189 +[Abstract](319) +[PDF](339.9KB)
Abstract:
We describe a filtering technique improving the performance of index-calculus algorithms for hyperelliptic curves. Filtering is a stage taking place between the relation search and the linear algebra. Its purpose is to eliminate redundant or duplicate relations, as well as reducing the size of the matrix, thus decreasing the time required for the linear algebra step.
This technique, which we call harvesting, is in fact a new strategy that subtly alters the whole index calculus algorithm. In particular, it changes the relation search to find many times more relations than variables, after which a selection process is applied to the set of the relations - the harvesting process. The aim of this new process is to extract a (slightly) overdetermined submatrix which is as small as possible. Furthermore, the size of the factor base also has to be readjusted, in order to keep the (extended) relation search faster than it would have been in an index calculus algorithm without harvesting. The size of the factor base must also be chosen to guarantee that the final matrix will be indeed smaller than it would be in an optimised index calculus without harvesting, thus also speeding up the linear algebra step.
The version of harvesting presented here is an improvement over an earlier version by the same authors. By means of a new selection algorithm, time-complexity can be reduced from quadratic to linear (in the size of the input), thus making its running time effectively negligible with respect to the rest of the index calculus algorithm. At the same time we make the process of harvesting more effective - in the sense that the final matrix should (on average) be smaller than with the earlier approach.
We present an analysis of the impact of harvesting (for instance, we show that its usage can improve index calculus performance by more than 30% in some cases), we show that the impact on matrix size is essentially independent on the genus of the curve considered, and provide an heuristic argument in support of the effectiveness of harvesting as one parameter (which defines how far the relation search is pushed) increases.
2010, 4(2): 215-235 doi: 10.3934/amc.2010.4.215 +[Abstract](533) +[PDF](304.1KB)
Abstract:
We propose a public-key encryption scheme and key agreement protocols based on a group action on a set. We construct an implementation of these schemes for the action of the class group $\mathcal{CL}(\mathcal{O}_K)$ of an imaginary quadratic field $K$ on the set $\mathcal{ELL}$p,n$(\mathcal{O}_K)$ of isomorphism classes of elliptic curves over $\mathbb{F}_p$ with $n$ points and the endomorphism ring $\mathcal{O}_K$. This introduces a novel way of using elliptic curves for constructing asymmetric cryptography.
2010, 4(2): 237-260 doi: 10.3934/amc.2010.4.237 +[Abstract](281) +[PDF](288.4KB)
Abstract:
We present algorithms for computing the cube of an ideal in an imaginary quadratic number field or function field. In addition to a version that computes a non-reduced output, we present a variation based on Shanks' NUCOMP algorithm that computes a reduced output and keeps the sizes of the intermediate operands small. Extensive numerical results are included demonstrating that in many cases our formulas, when combined with double base chains using binary and ternary exponents, lead to faster exponentiation.
2010, 4(2): 261-279 doi: 10.3934/amc.2010.4.261 +[Abstract](293) +[PDF](262.4KB)
Abstract:
We present an algorithm for reducing a divisor on a hyperelliptic curve of arbitrary genus over any finite field. Our method is an adaptation of a procedure for reducing ideals in quadratic number fields due to Jacobson, Sawilla and Williams, and shares common elements with both the Cantor and the NUCOMP algorithms for divisor arithmetic. Our technique is especially suitable for the rapid reduction of a divisor with very large Mumford coefficients, obtained for example through an efficient tupling technique. Results of numerical experiments are presented, showing that our algorithm is superior to the standard reduction algorithm in many cases.
2010, 4(2): 281-305 doi: 10.3934/amc.2010.4.281 +[Abstract](295) +[PDF](293.4KB)
Abstract:
In the article we shall try to give an overview of the interplay between the design of public key cryptosystems and algorithmic arithmetic geometry. We begin in Section 2 with a very abstract setting and try to avoid all structures which are not necessary for protocols like Diffie-Hellman key exchange, ElGamal signature and pairing based cryptography (e.g. short signatures). As an unavoidable consequence of the generality the result is difficult to read and clumsy. But nevertheless it may be worthwhile because there are suggestions for systems which do not use the full strength of group structures (see Subsection 2.2.1) and it may motivate to look for alternatives to known group-based systems.
But, of course, the main part of the article deals with the usual realization by discrete logarithms in groups, and the main source for cryptographically useful groups are divisor class groups.
We describe advances concerning arithmetic in such groups attached to curves over finite fields including addition and point counting which have an immediate application to the construction of cryptosystems.
For the security of these systems one has to make sure that the computation of the discrete logarithm is hard. We shall see how methods from arithmetic geometry narrow the range of candidates usable for cryptography considerably and leave only carefully chosen curves of genus $1$ and $2$ without flaw.
A last section gives a short report on background and realization of bilinear structures on divisor class groups induced by duality theory of class field theory, the key concept here is the Lichtenbaum-Tate pairing.

2016  Impact Factor: 0.8

[Back to Top]