On the Performance Analysis for CSIDH-Based Cryptosystems
Source abstract
Abstract
In this paper, we present the performance and security analysis for various commutative SIDH (CSIDH)-based algorithms. As CSIDH offers a smaller key size than SIDH and provides a relatively efficient signature scheme, numerous CSIDH-based key exchange algorithms have been proposed to optimize the CSIDH. In CSIDH, the private key is an ideal class in a class group, which can be represented by an integer vector. As the number of ideal classes represented by these vectors determines the security level of CSIDH, it is important to analyze whether the different vectors induce the same public key. In this regard, we generalize the existence of a collision for a base prime p≡7mod8. Based on our result, we present a new interval for the private key to have a similar security level for the various CSIDH-based algorithms for a fair comparison of the performance. Deduced from the implementation result, we conclude that for a prime p≡7mod8, CSIDH on the surface using the Montgomery curves is the most likely to be efficient. For a prime p≡3mod8, CSIDH on the floor using the hybrid method with Onuki’s collision-free method is the most likely to be efficient and secure.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Cryptography and Residue Arithmetic · Coding theory and cryptography · Cryptography and Data Security
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Graduate School of Information Security, Institute of Cyber Security and Privacy (ICSP), Korea University, Seoul 02841, Korea
Department of Information Security, Graduate School of Information Security, Sejong Cyber University, Seoul 05000, Korea
References (21)
Show source-provided references
1. Couveignes, J.-M. (2020, June 06). Hard Homogeneous Spaces. Available online: https://eprint.iacr.org/2006/291.
2. Constructing elliptic curve isogenies in quantum subexponential time10.1515/jmc-2012-0016 ↗
3. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies10.1515/jmc-2012-0015 ↗
4. Koziel, B., Ackie, A.B., El Khatib, R., Azarderakhsh, R., and Kermani, M.M. (2020, June 06). Supersingular Isogeny Key Encapsulation, Available online: https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions.
5. Feo, L.D., Kieffer, J., and Smith, B. (2018, January 2–6). Towards practical key exchange from ordinary isogeny graphs. Proceedings of the 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, Australia.
6. Castryck, W., Lange, T., Martindale, C., Panny, L., and Renes, J. (2018, January 2–6). CSIDH: An efficient post-quantum commutative group action. Proceedings of the 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, Australia.10.1007/978-3-030-03332-3_15 ↗
7. Beullens, W., Kleinjung, T., and Vercauteren, F. (2019, January 8–12). CSI-FiSh: Efficient isogeny based signatures through class group computations. Proceedings of the 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan.10.1007/978-3-030-34578-5_9 ↗
8. Yoo, Y., Azarderakhsh, R., Jalali, A., Jao, D., and Soukharev, V. (2017, January 10–14). A post-quantum digital signature scheme based on supersingular isogenies. Proceedings of the International Conference on Financial Cryptography and Data Security, Kota Kinabalu, Malaysia.10.1007/978-3-319-70972-7_9 ↗
9. De Feo, L., and Galbraith, S.D. (2019, January 19–23). SeaSign: Compact isogeny signatures from class group actions. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany.10.1007/978-3-030-17659-4_26 ↗
10. Meyer, M., and Reith, S. (2018, January 9–12). A faster way to the CSIDH. Proceedings of the 19th International Conference Cryptology in India, New Delhi, India.10.1007/978-3-030-05378-9_8 ↗
11. Heo, D., Kim, S., Yoon, K., Park, Y.-H., and Hong, S. (2020). Optimized CSIDH Implementation Using a 2-Torsion Point. Cryptography, 4.10.3390/cryptography4030020 ↗
12. Kim, S., Yoon, K., Park, Y.H., and Hong, S. (2019, January 8–12). Optimized method for computing odd-degree isogenies on Edwards curves. Proceedings of the 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan.10.1007/978-3-030-34621-8_10 ↗
13. Onuki, H., and Takagi, T. (2020, August 20). On Collisions Related to an Ideal Class of Order 3 in CSIDH. Available online: https://eprint.iacr.org/2019/1209.10.1007/978-3-030-58208-1_8 ↗
14. Castryck, W., and Decru, T. (2020, January 15–17). CSIDH on the surface. Proceedings of the 11th International Conference PQCrypto 2020, Paris, France.10.1007/978-3-030-44223-1_7 ↗
15. Fan, X., Tian, S., Li, B., and Xiu, X. (2020, August 20). CSIDH on Other Form of Elliptic Curves. Available online: https://eprint.iacr.org/2019/1417.
16. Costello, C., and Hisil, H. (2017, January 3–7). A simple and compact algorithm for SIDH with arbitrary degree isogenies. Proceedings of the 23rd International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, China.10.1007/978-3-319-70697-9_11 ↗
17. Canteaut, A., and Ishai, Y. (2020). He Gives C-Sieves on the CSIDH. Advances in Cryptology—EUROCRYPT 2020, Springer. Lecture Notes in Computer Science.10.1007/978-3-030-45727-3 ↗
18. Canteaut, A., and Ishai, Y. (2020). Quantum Security Analysis of CSIDH. Advances in Cryptology—EUROCRYPT 2020, Springer. Lecture Notes in Computer Science.10.1007/978-3-030-45724-2 ↗
19. Meyer, M., Campos, F., and Reith, S. (2020, September 23). On Lions and Elligators: An Efficient Constant-Time Implementation of CSIDH. Available online: https://eprint.iacr.org/2018/1198.
20. Cervantes-Vázquez, D., Chenu, M., Chi-Domínguez, J.J., De Feo, L., Rodríguez-Henríquez, F., and Smith, B. (2020, September 23). Stronger and Faster Side-Channel Protections for CSIDH. Available online: https://eprint.iacr.org/2019/837.10.1007/978-3-030-30530-7_9 ↗
21. Bernstein, D., De Feo, L., Leroux, A., and Smith, B. (2020, September 23). Faster Computation of Isogenies of Large Prime Degree. Available online: https://eprint.iacr.org/2020/341.