International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Song Tian

Publications

Year
Venue
Title
2023
JOFC
Cover Attacks for Elliptic Curves over Cubic Extension Fields
Song Tian
We give a new approach to the elliptic curve discrete logarithm problem over cubic extension fields $${\mathbb {F}}_{q^3}$$ F q 3 . It is based on a transfer: First an $${\mathbb {F}}_q$$ F q -rational $$(\ell ,\ell ,\ell )$$ ( ℓ , ℓ , ℓ ) -isogeny from the Weil restriction of the elliptic curve under consideration with respect to $${\mathbb {F}}_{q^3}/{\mathbb {F}}_q$$ F q 3 / F q to the Jacobian variety of a genus three curve over $${\mathbb {F}}_q$$ F q is applied and then the problem is solved in the Jacobian via index-calculus attacks. Although it uses no covering maps in the construction of the desired homomorphism, this method is, in a sense, a kind of cover attack. As a result, it is possible to solve the discrete logarithm problem in some elliptic curve groups of prime order over $${\mathbb {F}}_{q^3}$$ F q 3 in a time of $${\tilde{O}}(q)$$ O ~ ( q ) .
2021
JOFC
Translating the Discrete Logarithm Problem on Jacobians of Genus 3 Hyperelliptic Curves with $(\ell ,\ell ,\ell )$-Isogenies
Song Tian
We give an algorithm to compute $$(\ell ,\ell ,\ell )$$ ( ℓ , ℓ , ℓ ) -isogenies from the Jacobians of genus three hyperelliptic curves to the Jacobians of non-hyperelliptic curves over a finite field of characteristic different from 2 in time $$\tilde{O}(\ell ^3)$$ O ~ ( ℓ 3 ) , where $$\ell $$ ℓ is an odd prime which is coprime to the characteristic. An important application is to reduce the discrete logarithm problem in the Jacobian of a hyperelliptic curve to the corresponding problem in the Jacobian of a non-hyperelliptic curve.
2019
ASIACRYPT
Strongly Secure Authenticated Key Exchange from Supersingular Isogenies
This paper aims to address the open problem, namely, to find new techniques to design and prove security of supersingular isogeny-based authenticated key exchange (AKE) protocols against the widest possible adversarial attacks, raised by Galbraith in 2018. Concretely, we present two AKEs based on a double-key PKE in the supersingular isogeny setting secure in the sense of CK$$^+$$, one of the strongest security models for AKE. Our contributions are summarised as follows. Firstly, we propose a strong OW-CPA secure PKE, $$\mathsf {2PKE_{sidh}}$$, based on SI-DDH assumption. By applying modified Fujisaki-Okamoto transformation, we obtain a [OW-CCA, OW-CPA] secure KEM, $$\mathsf {2KEM_{sidh}}$$. Secondly, we propose a two-pass AKE, $$\mathsf {SIAKE}_2$$, based on SI-DDH assumption, using $$\mathsf {2KEM_{sidh}}$$ as a building block. Thirdly, we present a modified version of $$\mathsf {2KEM_{sidh}}$$ that is secure against leakage under the 1-Oracle SI-DH assumption. Using the modified $$\mathsf {2KEM_{sidh}}$$ as a building block, we then propose a three-pass AKE, $$\mathsf {SIAKE}_3$$, based on 1-Oracle SI-DH assumption. Finally, we prove that both $$\mathsf {SIAKE}_2$$ and $$\mathsf {SIAKE}_3$$ are CK$$^+$$ secure in the random oracle model and supports arbitrary registration. We also provide an implementation to illustrate the efficiency of our schemes. Our schemes compare favourably against existing isogeny-based AKEs. To the best of our knowledge, they are the first of its kind to offer security against arbitrary registration, wPFS, KCI, and MEX simultaneously. Regarding efficiency, our schemes outperform existing schemes in terms of bandwidth as well as CPU cycle count.

Coauthors

Man Ho Au (1)
Kunpeng Wang (1)
Xiu Xu (1)
Haiyang Xue (1)