Advertisement
Published in:
2020 | OriginalPaper | Chapter
Security Analysis of Group Action Inverse Problem with Auxiliary Inputs with Application to CSIDH Parameters
Author : Taechan Kim
Published in: Information Security and Cryptology – ICISC 2019
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In this paper, we consider the security of a problem called Group Action Inverse Problem with Auxiliary Inputs (GAIPwAI). The Group Action Inverse Problem (GAIP) plays an important role in the security of several isogeny-based cryptosystems, such as CSIDH, SeaSign and CSI-FiSh.
Briefly speaking, given two isogenous supersingular curves E and \(E'\) over \(\mathbb F_p\), where \(E'\) is defined by an ideal \(\mathfrak a\) in the \(\mathbb F_p\)-endomorphism ring of E and denoted by \(E' = [\mathfrak a]*E\), GAIP requires finding \(\mathfrak a \subset {\text {End}}_{\mathbb F_p}(E)\). Its best classical algorithm is based on the baby-step-giant-step method and it runs in time \(O(p^{1/4})\).
In this paper, we show that if E and \(E'\) are given together with \([\mathfrak a^d]*E\) for a positive divisor d that divides the order of the class group of \({\mathbb Z}[\sqrt{-p}]\), then \(\mathfrak a\) can be computed in \(O\big ( ( p^{1/2} /d)^{1/2} + d^{1/2} \big )\) time complexity. In particular, when \(d \approx p^{1/4}\), it can be solved in time \(O( p^{1/8} )\) which is significantly less than \(O( p^{1/4} )\).
Applying the idea to CSIDH-512 parameters, we show that, if an additional isogenous curve \([\mathfrak a^d] * E\) is given, the security level of this cryptosystem reduces to 68-bit security instead of 128-bit security as originally believed.