## Abstract

This paper analyzes the best speeds that can be obtained for single-scalar multiplication with variable base point by combining a huge range of options: many choices of coordinate systems and formulas for individual group operations, including new formulas for tripling on Edwards curves; double-base chains with many different doubling/tripling ratios, including standard base-2 chains as an extreme case; many precomputation strategies, going beyond Dimitrov, Imbert, Mishra (Asiacrypt 2005) and Doche and Imbert (Indocrypt 2006). The analysis takes account of speedups such as S -M tradeoffs and includes recent advances such as inverted Edwards coordinates. The main conclusions are as follows. Optimized precomputations and triplings save time for single-scalar multiplication in Jacobian coordinates, Hessian curves, and tripling-oriented Doche/Icart/Kohel curves. However, even faster single-scalar multiplication is possible in Jacobi intersections, Edwards curves, extended Jacobi-quartic coordinates, and inverted Edwards coordinates, thanks to extremely fast doublings and additions; there is no evidence that double-base chains are worthwhile for the fastest curves. Inverted Edwards coordinates are the speed leader.

Keyword: edwards curves,scalar multiplication,Algorithms,double-base chains,addition chains,Computation theory,Double-base number systems,quintupling,T,tripling,COMPUTER,double-base number systems,Problem solving,Optimization

Keyword: edwards curves,scalar multiplication,Algorithms,double-base chains,addition chains,Computation theory,Double-base number systems,quintupling,T,tripling,COMPUTER,double-base number systems,Problem solving,Optimization

Original language | English |
---|---|

Title of host publication | PROGRESS IN CRYPTOLOGY - INDOCRYPT 2007 |

Volume | Volume 4859 |

Publisher | Springer Verlag, Berlin |

Publication date | 2007 |

Pages | 167-182 |

ISBN (Print) | 978-35-40-77025-1 |

DOIs | |

Publication status | Published - 2007 |

Externally published | Yes |

Event | 8th International Conference on Cryptology in India: Progress in Cryptology - Chennai, India Duration: 9 Dec 2007 → 13 Dec 2007 Conference number: 8 http://www.informatik.uni-trier.de/~ley/db/conf/indocrypt/indocrypt2007.html |

### Conference

Conference | 8th International Conference on Cryptology in India |
---|---|

Number | 8 |

Country/Territory | India |

City | Chennai |

Period | 09/12/2007 → 13/12/2007 |

Internet address |

Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Number | Volume 4859 |