Minimum number of additions in elliptic curve cryptography using double-based number representation
Quinta-feira, 28 de fevereiro de 2019Vorapong 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)