CSIDH on the Surface

被引:37
作者
Castryck, Wouter
Decru, Thomas [1 ]
机构
[1] IMEC, Res Grp, Cos, Leuven, Belgium
来源
POST-QUANTUM CRYPTOGRAPHY, PQCRYPTO 2020 | 2020年 / 12100卷
关键词
Isogeny-based cryptography; Hard homogeneous spaces; CSIDH; Montgomery curves;
D O I
10.1007/978-3-030-44223-1_7
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
For primes p equivalent to 3 mod 4, we show that setting up CSIDH on the surface, i.e., using supersingular elliptic curves with endomorphism ring Z[(1 + root-p)/2], amounts to just a few sign switches in the underlying arithmetic. If p equivalent to 7 mod 8 then horizontal 2-isogenies can be used to help compute the class group action. The formulas we derive for these 2-isogenies are very efficient (they basically amount to a single exponentiation in F-p) and allow for a noticeable speed-up, e.g., our resulting CSURF-512 protocol runs about 5.68% faster than CSIDH-512. This improvement is completely orthogonal to all previous speedups, constant-time measures and construction of cryptographic primitives that have appeared in the literature so far. At the same time, moving to the surface gets rid of the redundant factor Z(3) of the acting ideal-class group, which is present in the case of CSIDH and offers no extra security.
引用
收藏
页码:111 / 129
页数:19
相关论文
共 24 条
[1]  
[Anonymous], 2017, Topics in Computational Number Theory inspired by Peter L. Montgomery
[2]  
Baelen B., 2019, THESIS KU LEUVEN
[3]   Quantum Circuits for the CSIDH: Optimizing Quantum Evaluation of Isogenies [J].
Bernstein, Daniel J. ;
Lange, Tanja ;
Martindale, Chloe ;
Panny, Lorenz .
ADVANCES IN CRYPTOLOGY - EUROCRYPT 2019, PT II, 2019, 11477 :409-441
[4]   CSI-FiSh: Efficient Isogeny Based Signatures Through Class Group Computations [J].
Beullens, Ward ;
Kleinjung, Thorsten ;
Vercauteren, Frederik .
ADVANCES IN CRYPTOLOGY - ASIACRYPT 2019, PT I, 2019, 11921 :227-247
[5]  
Bonnetain X., 2018, IACR CRYPTOLOGY EPRI, P537
[6]   The Magma algebra system .1. The user language [J].
Bosma, W ;
Cannon, J ;
Playoust, C .
JOURNAL OF SYMBOLIC COMPUTATION, 1997, 24 (3-4) :235-265
[7]  
Castryck W., 2019, IACR CRYPTOLOGY EPRI, V2019, P1202
[8]  
Castryck W, 2018, LECT NOTES COMPUT SC, V11274, P395, DOI 10.1007/978-3-030-03332-3_15
[9]   Stronger and Faster Side-Channel Protections for CSIDH [J].
Cervantes-Vazquez, Daniel ;
Chenu, Mathilde ;
Chi-Dominguez, Jesus-Javier ;
De Feo, Luca ;
Rodriguez-Henriquez, Francisco ;
Smith, Benjamin .
PROGRESS IN CRYPTOLOGY - LATINCRYPT 2019, 2019, 11774 :173-193
[10]  
Couveignes, 2006, 2006291 CRYPT EPRINT