Speeding up XTR

Abstract. This paper describes several speedups and simpli¯cations for XTR. The most important results are new XTR double and single ex-ponentiation methods where the latter requires a cheap precomputation. Both methods are on average more than 60 % faster than the old methods, thus more than doubling the speed of the already fast XTR signature applications. An additional advantage of the new double exponentiation method is that it no longer requires matrices, thereby making XTR easier to implement. Another XTR single exponentiation method is presented that does not require precomputation and that is on average more than 35 % faster than the old method. Existing applications of similar methods to LUC and elliptic curve cryptosystems are reviewed