# Analysis of linear combination algorithms in cryptography

Analysis of linear combination algorithms in cryptography Several cryptosystems rely on fast calculations of linear combinations in groups. One way to achieve this is to use joint signed binary digit expansions of small “weight.” We study two algorithms, one based on nonadjacent forms of the coefficients of the linear combination, the other based on a certain joint sparse form specifically adapted to this problem. Both methods are sped up using the sliding windows approach combined with precomputed lookup tables. We give explicit and asymptotic results for the number of group operations needed, assuming uniform distribution of the coefficients. Expected values, variances and a central limit theorem are proved using generating functions.Furthermore, we provide a new algorithm that calculates the digits of an optimal expansion of pairs of integers from left to right. This avoids storing the whole expansion, which is needed with the previously known right-to-left methods, and allows an online computation. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

# Analysis of linear combination algorithms in cryptography

, Volume 1 (1) – Jul 1, 2005
20 pages      /lp/association-for-computing-machinery/analysis-of-linear-combination-algorithms-in-cryptography-Rq6UD5H5NW
Publisher
Association for Computing Machinery
ISSN
1549-6325
DOI
10.1145/1077464.1077473
Publisher site
See Article on Publisher Site

### Abstract

Several cryptosystems rely on fast calculations of linear combinations in groups. One way to achieve this is to use joint signed binary digit expansions of small “weight.” We study two algorithms, one based on nonadjacent forms of the coefficients of the linear combination, the other based on a certain joint sparse form specifically adapted to this problem. Both methods are sped up using the sliding windows approach combined with precomputed lookup tables. We give explicit and asymptotic results for the number of group operations needed, assuming uniform distribution of the coefficients. Expected values, variances and a central limit theorem are proved using generating functions.Furthermore, we provide a new algorithm that calculates the digits of an optimal expansion of pairs of integers from left to right. This avoids storing the whole expansion, which is needed with the previously known right-to-left methods, and allows an online computation.

### Journal

ACM Transactions on Algorithms (TALG)Association for Computing Machinery

Published: Jul 1, 2005