Welcome to the resource topic for 2020/181
Title:
L_1-Norm Ball for CSIDH: Optimal Strategy for Choosing the Secret Key Space
Authors: Kohei Nakagawa, Hiroshi Onuki, Atsushi Takayasu, Tsuyoshi Takagi
Abstract:Isogeny-based cryptography is a kind of post-quantum cryptography whose security relies on the hardness of an isogeny problem over elliptic curves. In this paper, we study CSIDH, which is one of isogeny-based 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 CSIDH-512, 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.
ePrint: https://eprint.iacr.org/2020/181
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .