Paper 2020/181
$L_1$Norm Ball for CSIDH: Optimal Strategy for Choosing the Secret Key Space
Kohei Nakagawa, Hiroshi Onuki, Atsushi Takayasu, and Tsuyoshi Takagi
Abstract
Isogenybased cryptography is a kind of postquantum cryptography whose security relies on the hardness of an isogeny problem over elliptic curves. In this paper, we study CSIDH, which is one of isogenybased cryptography presented by Castryck et al. in Asiacrypt 2018. In CSIDH, the secret key is taken from an $L_\infty$norm ball of integer vectors and the public key is generated by calculating the action of an ideal class corresponding to a secret key. For faster key exchange, it is important to accelerate the algorithm calculating the action of the ideal class group, many such approaches have been studied recently. Several papers showed that CSIDH becomes more efficient when a secret key space is changed to weighted $L_\infty$norm ball. In this paper, we revisit the approach and try to find an optimal secret key space which minimizes the computational cost of the group action. At first, we obtain an optimal secret key space by analyzing computational cost of CSIDH with respect to the number of operations on $\mathbb{F}_p$. Since the optimal key space is too complicated to sample a secret key uniformly, we approximate the optimal key space by using $L_1$norm ball and propose algorithms for uniform sampling with some precomputed table. By experiment with CSIDH512, we show that the computational cost of the $L_1$norm ball is reduced by about 20\% compared to that of the $L_\infty$norm ball, using a precomputed table of 160 Kbytes. The cost is only 1.08 times of the cost of the optimal secret key space. Finally, we also discuss possible sampling algorithms using other norm balls and their efficiency.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 postquantum cryptographyCSIDHsupersingular elliptic curve
 Contact author(s)
 kouhei_nakagawa @ mist i utokyo ac jp
 History
 20200214: received
 Short URL
 https://ia.cr/2020/181
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/181, author = {Kohei Nakagawa and Hiroshi Onuki and Atsushi Takayasu and Tsuyoshi Takagi}, title = {$L_1$Norm Ball for CSIDH: Optimal Strategy for Choosing the Secret Key Space}, howpublished = {Cryptology ePrint Archive, Paper 2020/181}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/181}}, url = {https://eprint.iacr.org/2020/181} }