Optimal recoding of binary numbers for cryptographic operations

North Dakota State University Fargo, Fargo ND

Investigators

Abstract

0429523 Rajendra S. Katti North Dakota State University Fargo Algorithms to recode a binary number into a signed binary number (such numbers have digits {0,1,-1}) will be developed by the proposed work. The main advantage of the algorithms developed is that they examine the binary numbers from left-to-right. The algorithms must result in minimal joint weight to reduce the number of operations in the multi-exponentiation operation used in cryptography. Developing such algorithms for more than one integer has never been done before. In fact this was considered as a hard problem in the literature. The PI developed a left-to-right recoding algorithm for two integers that resulted in minimal joint weight. This resulted in a solution to a problem that had been an open problem since 2001. Extending this to the general case of N integers will be considered. This extension is no trivial task because the only known solution to minimal joint weight recoding of N integers examines the integers from right-to-left. Examining the integers from left-to-right makes the algorithm compatible with Shamir.s left-to-right multi-exponentiation method. This leads to less memory requirement for multi-exponentiation, which is very important in memory-constrained systems like smart cards. Other extensions like recoding for sliding window methods of multi- exponentiation will also be considered. In this case the algorithms developed, other than being left-to-right will also maximize the length of zeros between windows. This again results in decreasing memory requirement while increasing the speed of multi- exponentiation. Recoding with other digit sets like {0,1,-1,3,-3} will also be considered. Recodings developed by the proposed project are useful in cases where group inversion is very fast. Such groups include the elliptic curve group, groups of rational divisor classes of hyperelliptic curves, trace zero varieties and XTR subgroups.