Top | Introduction | Members | Activities | Call for Paper | Link | Japanese

    "Reserch for Optimaization of Hyperelliptic Curve Cryptography"

    A public-key cryptography, such as RSA and ElGamal cryptography has been proposed. However, development of computer threatens usual cryptosystems. Elliptic curve and Hyperelliptic curve cryptography have received a attention as a next generation cryptosystem. Elliptic curve cryptosystems and Hyperelliptic curve cryptosystems, chosen appropriately to avoid some attacks, are vulnerable agains only the Pollard\rho-method and the Pohlig-Hellman method. As a result, they can be constructed over a smaller definition field than the discrete-logarithm-problem (DLP)-based cryptosystems and RSA cryptosystems. Elliptic curve cryptosystems and Hyper-elliptic curve cryptosystems with a 160-bit key are thus believed to have the same security as both the ElGamal cryptosystems and RSA with a 1,024-bit key. This is why elliptic curve and Hyper-elliptic curve cryptosystems have been attractive in smart card applications, whose memory storage and CPU power is very limited. Elliptic curve and Hyper-elliptic curve cryptosystems execute an exponentiation algorithm of $dP$ for a secret key d and a publicly known P as a cryptographic primitive. Thus, the efficiency on a smart card depends on the implementation of exponentiation.
    In the execution on a smart card, side channel attacks such as the simple power analysis (SPA) and the differential power analysis (DPA) have become serious threat. Side channel attacks, first introduced by Kocher, monitor power consumption and even exploit the leakage information related to power consumption to reveal bits of a secret key d although d is hidden inside a smart card. Thus, it is a serious issue that the implementation should be resistant against SPA and DPA, and many countermeasures have been proposed. Recently, in the case of elliptic curve cryptosystems, DPA is further improved to the Refined Power Analysis (RPA), which exploits a special point with a zero value and reveals a secret key.
    This paper focuses on countermeasures against SPA. In order to be resistant against SPA, there are mainly two types of countermeasures: the fixed procedure method and the indistinguishable method. The fixed procedure method deletes any branch instruction conditioned by a secret exponent d like add-and-double-always method , Montgomery-ladder method, and window-based method. The indistinguishable method conceals all branch instructions of exponentiation algorithm by using indistinguishable addition formulae. However, the indistinguishable addition formulae reveals the Hamming weight of d when it is used to execute dP in such an addition chain that depends on the Hamming weight. As a result, to make the execution of dP secure, even indistinguishable addition formulae must use an addtion chain that outputs a fixed-hamming weight. Thus, in order to have an advantage against the fixed procedure method, the indistinguishable method needs such an addition chain that outputs a fixed-hamming weight but does not run in a fixed procedure. In the case of binary method, the add-and-double-always method is only a method that outputs exactly fixed-hamming weight. In the case of window method, is only a method that outputs exactly fixed-hamming weight. Therefore, it is useless for indistinguishable addition formulae to be used with such addition chains.
    In this paper, we focus on the signed binary method, since any converted method that outputs a fixed-hamming weight but not run in a fixed procedure has not ben proposed. In this research, we first give a way to represent any d in a signed binary whose Hamming weight is always fixed. Combined with such an addition chain, the indistinguishable method has an advantage against the fixed procedure method. We also give the indistinguishable addition formulae for Hyperelliptic curve.

    [ back ]