Bounds and trade-offs for Double-Base Number Systems

详细信息    查看全文

• 作者：Tiancheng Lou^a ; ^{loutiancheng860214@gmail.com} ; Xiaoming Sun ; ^a ; ^{xiaomings@tsinghua.edu.cn} ; Christophe Tartary^a ; ^{ctartary@mail.tsinghua.edu.cn}
• 关键词：Cryptography ; Elliptic curve cryptography ; Scalar multiplication ; Double-Base Number System ; Double-Base Chain
• 刊名：Information Processing Letters
• 出版年：2011
• 出版时间：30 April 2011
• 年：2011
• 卷：111
• 期：10
• 页码：488-493
• 全文大小：155 K

文摘

During the past twenty years, elliptic curves have attracted more and more attention from the cryptography community. One of the core operations of elliptic curve cryptography protocols is the scalar multiplication. Any algorithm reducing the complexity of such multiplications will speed up cryptographic primitives based on these algebraic structures. In this paper, we study two recently introduced techniques for scalar multiplication: Double-Base Number System (DBNS) and Double-Base Chain (DBC). Our results are twofold. First, we demonstrate a theoretical bound on the length of any DBC used to decompose some -bit integers. Second, we present a new algorithm to obtain a {2,3}-integer expansion of n. The bound previously computed will imply the optimality of this algorithm. Our scheme represents a trade-off method between the DBNS approach and the DBC technique. Experimentally, our algorithm constructs shorter chains on average than both the binary/ternary method and the greedy algorithm approach.