Advances Towards Practical Implementations of Isogeny Based Signatures

Abstract

Progress in the field of quantum computing has shown that, should construction of a sufficiently powerful quantum computer become feasible, much of the cryptography used on the Internet today will be rendered insecure. In lieu of this, several approaches to “quantum-safe” cryptography have been proposed, each one becoming a serious field of study. The youngest of these approaches, isogeny based cryptography, is oriented around problems in algebraic geometry involving a particular variety of elliptic curves. Supersingular isogeny Diffie-Hellman (SIDH) is this subfields main contender for quantum-safe key-exchange. Yoo et al. have provided an isogeny-based signature scheme built on top of SIDH. Currently, cryptographic algorithms in this class are hindered by poor performance metrics and, in the case of the Yoo et al. signature scheme, large communication overhead. In this dissertation we explore two different modifications to the implementation of this signature scheme; one with the intent of improving temporal performance, and another with the intent of reducing signature sizes. We show that our first modification, a mechanism for batching together expensive operations, can offer roughly 8% faster signature signing and verification. Our second modification, an adaptation of the SIDH public key compression technique outlined in [CJL + 17], can reduce Yoo et al. signature sizes from roughly 688λ bytes to 544λ bytes at the 128-bit security level on a 64-bit operating system. We also explore the combination of these techniques, and the potential of employing these techniques in different application settings. Our experiments reveal that isogeny based cryptosystems still have much potential for improved performance metrics. While some practitioners may believe isogeny-based cryptosystems impractical, we show that these systems still have room for improvement, and with continued research can be made more efficient - and eventually practical. Achieving more efficient implementations for quantum-safe algorithms will allow us to make them more accessible. With faster and lower-overhead implementations these primitives can be run on low bandwidth, low spec devices; ensuring that more and more machines can be made resistant to quantum cryptanalysis.