Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

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

Download PDF
20 pages

Loading next page...
 
/lp/association-for-computing-machinery/analysis-of-linear-combination-algorithms-in-cryptography-Rq6UD5H5NW
Publisher
Association for Computing Machinery
Copyright
Copyright © 2005 by ACM Inc.
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

There are no references for this article.