International Association
for Cryptologic Research

Based on re-keying techniques by Abdalla, Bellare, and Borst [1,2], we consider two black-box secure block cipher based symmetric encryption schemes, which we prove secure in the physically observable cryptography model. They are proven side-channel secure against a strong type of adversary that can adaptively choose the leakage function as long as the leaked information is bounded. It turns out that our simple construction is side-channel secure against all types of attacks that satisfy some reasonable assumptions. In particular, the security turns out to be negligible in the block cipher’s block size n, for all attacks. We also show that our ideas result in an interesting alternative to the implementation of block ciphers using different logic styles or masking countermeasures.

RFID-Tags are small devices used for identification purposes in many applications nowadays. It is expected that they will enable many new applications and link the physical and the virtual world in the near future. Since the processing power of these devices is low, they are often in the line of fire when their security and privacy is concerned. It is widely believed that devices with such constrained resources can not carry out sufficient cryptographic operations to guarantee security in new applications. In this paper, we show that identification of RFID-Tags can reach high security levels. In particular, we show how secure identification protocols based on the DL problem on elliptic curves are implemented on a constrained device such as an RFID-Tag requiring between 8500 and 14000 gates, depending on the implementation characteristics. We investigate the case of elliptic curves over $F_{2^p}$ with p prime and over composite fields $F_{2^{2p}}$. The implementations in this paper make RFID-Tags suitable for anti-counterfeiting purposes even in the off-line setting.

For most of the time since they were proposed, it was widely believed that hyperelliptic curve cryptosystems (HECC) carry a substantial performance penalty compared to elliptic curve cryptosystems (ECC) and are, thus, not too attractive for practical applications. Only quite recently improvements have been made, mainly restricted to curves of genus 2. The work at hand advances the state-of-the-art considerably in several aspects. First, we generalize and improve the closed formulae for the group operation of genus 3 for HEC defined over fields of characteristic two. For certain curves we achieve over 50% complexity improvement compared to the best previously published results. Second, we introduce a new complexity metric for ECC and HECC defined over characteristic two fields which allow performance comparisons of practical relevance. It can be shown that the HECC performance is in the range of the performance of an ECC; for specific parameters HECC can even possess a lower complexity than an ECC at the same security level. Third, we describe the first implementation of a HEC cryptosystem on an embedded (ARM7) processor. Since HEC are particularly attractive for constrained environments, such a case study should be of relevance.