You are looking at a specific version 20030910:054335 of this paper. See the latest version.

Paper 2003/180

Parallelizing Explicit Formula for Arithmetic in the Jacobian of Hyperelliptic Curves

Pradeep Kumar Mishra and Palash Sarkar

Abstract

One of the recent thrust areas in research on hyperelliptic curve cryptography has been to obtain explicit formulae for performing arithmetic in the Jacobian of such curves. We continue this line of research by obtaining parallel versions of such formulae. Our first contribution is to develop a general methodology for obtaining parallel algorithm of any explicit formula. Any parallel algorithm obtained using our methodology is provably optimal in the number of multiplication rounds. We next apply this methodology to Lange's explicit formula for arithmetic in genus 2 hyperelliptic curve -- both for the affine coordinate and inversion free arithmetic versions. Since encapsulated add-and-double algorithm is an important countermeasure against side channel attacks, we develop parallel algorithms for encapsulated add-and-double for both of Lange's versions of explicit formula. For the case of inversion free arithmetic, we present parallel algorithms using 4, 8 and 12 multipliers. All parallel algorithms described in this paper are optimal in the number of parallel rounds. One of the conclusions from our work is the fact that the parallel version of inversion free arithmetic is more efficient than the parallel version of arithmetic using affine coordinates.

Metadata
Available format(s)
PS
Category
Implementation
Publication info
Published elsewhere. Accepted in Asiacrypt03
Keywords
hyperelliptic curve cryptographyexplicit formulaparallel
Contact author(s)
pradeep_t @ isical ac in
History
2003-09-10: revised
2003-08-29: received
See all versions
Short URL
https://ia.cr/2003/180
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.