LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » 链接 » 巴黎六大计算机科学实验室日志

GT PequanRSS

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


2019-2-28
报告人 : 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)
更多具体信息
Marc.Mezzarobba (at) nulllip6.fr
 Mentions légales
网站导航 |