[Resource Topic] 2003/180: Parallelizing Explicit Formula for Arithmetic in the Jacobian of Hyperelliptic Curves

Welcome to the resource topic for 2003/180

Parallelizing Explicit Formula for Arithmetic in the Jacobian of Hyperelliptic Curves

Authors: Pradeep Kumar Mishra, Palash Sarkar


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.

ePrint: https://eprint.iacr.org/2003/180

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .