Constructing multidimensional differential addition chains and their applications

摘要

We propose new algorithms for constructing multidimensional differential addition chains and for performing multidimensional scalar point multiplication based on these chains. Our algorithms work in any dimension and offer some key efficiency and security features. In particular, our scalar point multiplication algorithm is uniform, it can be parallelized, and differential addition formulas can be deployed. It also allows trading speed for precomputation cost and storage requirements. These key features and our theoretical estimates indicate that this new algorithm may offer some performance advantages over the existing point multiplication algorithms in practice. We also report some experimental results and verify some of our theoretical findings, and a simplistic Magma implementation is provided.