Collision Attack on XTR and a Countermeasure with a Fixed Pattern ⋆

Abstract. Public-key cryptosystem (PKC) is one of inevitable key technologies in order to accomplish fruitful security applications in ubiquitous computing sys-tems. The ubiquitous computer only has scarce computational resources (like Smart cards, RFID, Sensor Network), however, so that the light weight PKC is necessary for those miniaturized low-power devices. Recently, XTR is considered as one of good candidates for more energy efficient cryptosystems. Among XTR exponentiation algorithms, the most efficient one is the Improved XTR Single Ex-ponentiation (XTR-ISE) proposed by Stam-Lenstra. Thus among the family of XTR algorithms, XTR-ISE is the most efficient one suitable for ubiquitous com-puter. Even though the security of such devices against side channel attacks is very dangerous, there are few works on side channel attacks against XTR-ISE. In this paper we propose a new collision attack on XTR-ISE, derived from the structural properties of XTR-ISE. The analysis complexity of the proposed one is about 240 where the key size is 160-bit, which is 55 % improvement from the previously best known analysis of Page-Stam. We also propose a novel countermeasure using