Minimum number of additions in elliptic curve cryptography using double-based number representation

28/02/2019
Palestrante(s) : Vorapong Suppakitpaisarn (Univ. Tokyo)
Double-based number representation (DBNS) is known to help reducing the computational complexity of elliptic curve cryptography. There are more than one ways to represent a particular number using DBNS, but even with a greedy representation of base 2 and 3 we can reduce the number of additions in ECC from O(log n) to O(log n / log log n). In this work, we generalize the greedy algorithm. Our algorithm leads to O(log / log log n) for most of the bases.
On the lower bound side, there are hopes that the number of additions can be reduced if we improve the representation or using a larger number of bases (such as triple-base number representation). We show in this work that the improvement is not possible: any multi-based number representation cannot lead to o(log n / log log n) additions.
(This talk is based on the joint work with D. Krenn and S. Wagner)