Paper published in a journal (Scientific congresses, symposiums and conference proceedings)
Batching CSIDH Group Actions using AVX-512
CHENG, Hao; FOTIADIS, Georgios; GROSZSCHÄDL, Johann et al.
2021In IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2021 (4), p. 618-649
Peer reviewed
 

Files


Full Text
TCHES2021.pdf
Author postprint (785.41 kB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
Post-Quantum Cryptography; Isogeny-Based Cryptography; CSIDH; AVX-512IFMA; Software Optimization; Constant-Time Implementation
Abstract :
[en] Commutative Supersingular Isogeny Diffie-Hellman (or CSIDH for short) is a recently-proposed post-quantum key establishment scheme that belongs to the family of isogeny-based cryptosystems. The CSIDH protocol is based on the action of an ideal class group on a set of supersingular elliptic curves and comes with some very attractive features, e.g. the ability to serve as a “drop-in” replacement for the standard elliptic curve Diffie-Hellman protocol. Unfortunately, the execution time of CSIDH is prohibitively high for many real-world applications, mainly due to the enormous computational cost of the underlying group action. Consequently, there is a strong demand for optimizations that increase the efficiency of the class group action evaluation, which is not only important for CSIDH, but also for related cryptosystems like the signature schemes CSI-FiSh and SeaSign. In this paper, we explore how the AVX-512 vector extensions (incl. AVX-512F and AVX-512IFMA) can be utilized to optimize constant-time evaluation of the CSIDH-512 class group action with the goal of, respectively, maximizing throughput and minimizing latency. We introduce different approaches for batching group actions and computing them in SIMD fashion on modern Intel processors. In particular, we present a hybrid batching technique that, when combined with optimized (8 × 1)-way prime-field arithmetic, increases the throughput by a factor of 3.64 compared to a state-of-the-art (non-vectorized) x64 implementation. On the other hand, vectorization in a 2-way fashion aimed to reduce latency makes our AVX-512 implementation of the group action evaluation about 1.54 times faster than the state-of-the-art. To the best of our knowledge, this paper is the first to demonstrate the high potential of using vector instructions to increase the throughput (resp. decrease the latency) of constant-time CSIDH.
Research center :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > Applied Security and Information Assurance Group (APSIA)
Disciplines :
Computer science
Author, co-author :
CHENG, Hao ;  University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > APSIA
FOTIADIS, Georgios ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > APSIA
GROSZSCHÄDL, Johann ;  University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
RYAN, Peter Y A ;  University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
ROENNE, Peter ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > APSIA
External co-authors :
no
Language :
English
Title :
Batching CSIDH Group Actions using AVX-512
Publication date :
August 2021
Event name :
Conference on Cryptographic Hardware and Embedded Systems (CHES 2021)
Event place :
Beijing, China
Event date :
2021-09-13 to 2021-09-17
Audience :
International
Journal title :
IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES)
ISSN :
2569-2925
Publisher :
Ruhr-Universität Bochum
Volume :
2021
Issue :
4
Pages :
618-649
Peer reviewed :
Peer reviewed
Focus Area :
Security, Reliability and Trust
FnR Project :
FNR13643617 - Secure, Quantum-safe, Practical Voting Technologies, 2019 (01/04/2020-31/03/2023) - Peter Y. A. Ryan
Funders :
FNR - Fonds National de la Recherche [LU]
Available on ORBilu :
since 07 January 2022

Statistics


Number of views
306 (45 by Unilu)
Number of downloads
264 (13 by Unilu)

Scopus citations®
 
3
Scopus citations®
without self-citations
2

Bibliography


Similar publications



Contact ORBilu