## Abstract

The Joint Sparse Form is currently the standard representation system to perform multi-scalar multiplications of the form [n]P + m[Q]. We introduce the concept of Joint Double-Base Chain, a generalization of the Double-Base Number System to represent simultaneously n and m. This concept is relevant because of the high redundancy of Double-Base systems, which ensures that we can find a chain of reasonable length that uses exactly the same terms to compute both n and m. Furthermore, we discuss an algorithm to produce such a Joint Double- Base Chain. Because of its simplicity, this algorithm is straightforward to implement, efficient, and also quite easy to analyze. Namely, in our main result we show that the average number of terms in the expansion is less than 0.3945 log2 n. With respect to the Joint Sparse Form, this induces a reduction by more than 20% of the number of additions. As a consequence, the total number of multiplications required for a scalar multiplications is minimal for our method, across all the methods using two precomputations, P + Q and P - Q. This is the case even with coordinate systems offering very cheap doublings, in contrast with recent results on scalar multiplications. Several variants are discussed, including methods using more precomputed points and a generalization relevant for Koblitz curves. Our second contribution is a new way to evaluate f, the dual endomorphism of the Frobenius. Namely, we propose formulae to compute ± f(P) with at most 2 multiplications and 2 squarings in the base field F _{2}. This represents a speed-up of about 50% with respect to the fastest known techniques. This has very concrete consequences on scalar and multi-scalar multiplications on Koblitz curves.

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

Title of host publication | Advances in Cryptology - EUROCRYPT 2009 - 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings |

Editors | Antoine Joux |

Place of Publication | Berlin; Heidelberg; NewYork |

Publisher | Springer, Springer Nature |

Pages | 502-517 |

Number of pages | 16 |

Volume | 5479 LNCS |

ISBN (Print) | 3642010008, 9783642010002 |

DOIs | |

Publication status | Published - 2009 |

Event | 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT - 2009 - Cologne, Germany Duration: 26 Apr 2009 → 30 Apr 2009 |

### Publication series

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

Volume | 5479 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Other

Other | 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT - 2009 |
---|---|

Country | Germany |

City | Cologne |

Period | 26/04/09 → 30/04/09 |