POKEx: Performance analysis of POKE-key exchange and SIDH-variants

Date of publication xxxx 00, 0000, date of current version xxxx 00, 0000. Digital Object Identifier 10.1109/ACCESS.2017.DOI

POKEx: Performance analysis of POKE-key exchange and SIDH-variants HYEONHAK KIM1 , SUHRI KIM2

1 2

School of Cybersecurity, Korea University, Seoul 02841, South Korea School of Mathematics, Statistics and Data Science, Sungshin Women’s University, Seoul, 02844, South Korea

Corresponding author: Suhri Kim (e-mail: suhrikim@sungshin.ac.kr).

arXiv:2608.06826v1 [cs.CR] 7 Aug 2026

This work was supported by the Sungshin Women’s University Research Grant of 2024 (H20240079).

ABSTRACT In this paper, we present a comparative performance analysis of the POKÉ-based key exchange and SIDH variants. SIDH gained attention for its small key size and efficient performance, and has been selected as an alternate candidate in NIST PQC Round 4. However, following the key recovery attack by Castryck and Decru in 2022, SIDH was shown to be vulnerable to polynomial-time attacks on classical computers, undermining its security and removing it from consideration. Given that SIDH was regarded as the leading isogeny-based algorithm, several countermeasures, such as MSIDH, MD-SIDH, and bin/terSIDH have been proposed. However, these approaches still face performance limitations. Meanwhile, POKÉ, proposed by Basso and Maino at Eurocrypt 2025, is an isogeny-based public key encryption scheme that combines a SIDH-like protocol with higher-dimensional isogenies and has drawn attention for its efficient performance. In this work, we adapt POKÉ into a key exchange algorithm and benchmark it against M-SIDH, terSIDH, and CSIDH. Targeting NIST security level 1, POKÉ-based KEM is approximately 21.21 times faster than terSIDH and 64.97 times faster than CSIDH, showing that the POKÉ-based KEM is currently the most promising isogeny-based key exchange candidate. INDEX TERMS Isogeny, Post-quantum cryptography, SIDH, key recovery attack, POKÉ

I. INTRODUCTION

The start of isogeny-based cryptography can be traced back to the work of Couveignes in [1], which is now known as the CRS scheme. However, it was the introduction of SIDH (Supersingular Isogeny Diffie-Hellman) by De Feo and Jao that marked the beginning of active research in this area [2]. In contrast to the original CRS scheme and standard elliptic curve cryptography, which are based on ordinary elliptic curves, SIDH uses supersingular elliptic curves. As the endomorphism ring of the supersingular elliptic curve is non-commutative, this allows SIDH to withstand the attack proposed in [3] that solves the CRS scheme with subexponential complexity. Moreover, various optimization efforts, including the influential work by Costello et al. in [4], lead to efficient performance, which significantly contributed to the proposal of the encapsulation algorithm SIKE in the NIST PQC standardization project. Unlike many other algorithms submitted to the PQC standardization project, which required increasingly larger key or signature sizes due to newly discovered attacks, SIKE stood out by maintaining resistance against all known attacks for nearly a decade. In fact, since VOLUME 4, 2016

its introduction, no attack more efficient than the Meet-inthe-Middle (MitM) approach was found [5], and analysis showed that smaller parameters could be used while maintaining the same security level, which strengthens the SIKE’s advantage in terms of key size. Some studies even suggested that, for SIDH-based algorithms, classical attacks could be more effective than quantum ones, further supporting its consideration as an alternate candidate in Round 4. However, in 2023, Castryck and Decru showed that the private key in SIDH can be recovered in classical polynomial time [6]. Due to the non-commutative property of supersingular elliptic curves, SIDH requires publishing the computation of other parties’ public keys with one’s private key. This is called torsion point information. Torsion-point information is not seen in general key exchange algorithms and is unique to SIDH-based cryptography. Hence, a significant amount of research has targeted this feature as a potential weakness [7]–[10]. The Castryck–Decru attack in 2023 was the first to fully exploit it, demonstrating that SIDH can be broken in polynomial time [6]. The attack uses the torsion point information together with Kani’s glue-and-split 1

Author et al.: Preparation of Papers for IEEE TRANSACTIONS and JOURNALS

algorithm. Because this attack fundamentally exploits torsion point information, cryptosystems such as SIDH, BSIDH, and SETA that use torsion point information can be broken in polynomial time. Subsequently, Maino et al. [11] and Robert [12] independently showed that SIDH-based algorithms remain vulnerable even with arbitrary starting curves, confirming that SIDH-based schemes are no longer secure. As SIDH is regarded as one of the most efficient among isogeny-based cryptosystems, several studies have been conducted to preserve its advantages while mitigating the Castryck–Decru attack. The Castryck-Decru attack relies on three main facts: 1) torsion-point information that SIDHbased cryptography publishes, 2) the degree of the isogeny connecting two elliptic curves is known, and 3) this degree is power-smooth for efficiency. Among these, torsionpoint information plays the most critical role. To address these points, [13] proposed two countermeasures: M-SIDH (masked torsion point SIDH), which hides torsion-point information by masking it with random values, and MDSIDH (masked-degree SIDH), which masks the degree of the isogeny used. However, unlike conventional SIDH-based cryptosystems, which use primes of the form p = 2e1 3e2 − 1 that enable efficient reduction, Q M-SIDH and MD-SIDH adopt primes of the form p = ℓi − 1, where ℓi s are odd primes. This choice prevents efficient reduction and requires primes more than ten times larger for the same security level (MSIDH requires a 5911-bit prime for NIST security level 1), resulting in reduced efficiency. In [14], Basso et al. proposed binSIDH (binary SIDH) and terSIDH (ternary SIDH) to counter the key recovery attack. Both binSIDH and terSIDH introduce the concept of artificial orientation and adopt new forms of secret keys. Among them, terSIDH provides about 1.6 bits of security per private key bit and offers relatively fast performance, making it a competitive SIDH variant. However, the total isogeny degree of terSIDH depends on the private key, causing variations in execution time and exposing it to potential timing attacks. Overall, while several SIDH variants have been proposed to address the Castryck–Decru attack, none have proven to be truly practical, highlighting the need for exploring a wider range of scheme designs. Meanwhile, the Castryck–Decru attack prompted a major redesign of SIDH-based cryptosystems. Traditionally, isogenies were represented by their corresponding cyclic kernel. Knowing the kernel allows the isogeny to be computed using Vélu’s formulas, and the smooth order of torsion points is required for an efficient isogeny computation. However, keyrecovery attacks have shown that it is possible to perform an efficient isogeny computation even when the degree is not smooth. Hence, knowing a pair of curves, their associated torsion points, and the isogeny degree is sufficient to compute the connecting isogeny. Applying this new highdimensional approach has yielded more efficient results, as seen in schemes such as SQIsign and SCALLOP [15]– [19]. However, applying such a high-dimensional approach to SIDH to counter the key recovery attack was first done in 2

[20]. In [20], Basso and Maino proposed POKÉ, an isogenybased encryption algorithm that constructs a SIDH-like commutative diagram integrating a two-dimensional representation. As mentioned above, SIDH variants designed to counter existing key-recovery attacks are not only defined over larger finite fields than SIDH, but also use field structures that are not reduction-efficient, which has the greatest impact on their performance. On the other hand, POKÉ is based on a finite field with a prime of the form p = 2a 3b 5c f − 1, a structure that is central to its high efficiency. In POKÉ, one party computes isogenies of non-smooth degree using the two-dimensional representation, while the other computes smooth-degree isogenies in the traditional way. For a security parameter λ, POKÉ requires a prime of size 10λ/3 bits. This means that current public keys and ciphertexts are small and compare favorably with most protocols in the literature, resulting in very efficient performance. A. OUR CONTRIBUTIONS

As noted above, POKÉ benefits from relatively small key sizes and efficient finite field structure. Furthermore, POKÉ is an IND-CPA secure public-key encryption (PKE) scheme, and it is well known that the IND-CPA PKE can be transformed into an IND-CCA secure KEM via the FujisakiOkamoto (FO) transform [21]. Although this fact is mentioned in [20], the application of the FO-transform to POKÉ has not been explicitly formalized. In addition, although various isogeny-based key exchange protocols have been proposed in response to key recovery attack, a unified sideby-side comparison of performance is unavailable in the literature. In this work, we address this gap by performing a comparative analysis of POKÉ-based key exchange and other SIDH variants, evaluating their performance under a unified experimental setting. Specifically, we first explicitly define a KEM derived from POKÉ and analyze its security. Then, we perform a side-by-side evaluation against other isogenybased key exchange protocols, including terSIDH, M-SIDH, and CSIDH, at the same security level. The contributions of this paper are summarized as follows: This paper provides a complete description of a key encapsulation mechanism (KEM) built on POKÉ – which we denote by POKEx. Although [20] provides a high-level description of a POKÉ-based key exchange method, its main focus is the encryption algorithm, and it does not present details of the KEM. This paper supplies that detailed specification. We also provide a C implementation based on [22]. Our implementation of POKEx can be found at: https://github.com/gusgkr0117/poke • This paper provides a comparison of key sizes and performance results across representative isogeny-based key exchange methods—namely, M-SIDH, terSIDH, CSIDH, and a POKÉ-based KEM (POKEx). We eval•

VOLUME 4, 2016

Author et al.: Preparation of Papers for IEEE TRANSACTIONS and JOURNALS

uate POKEx against these isogeny-based algorithms targeting NIST security level 1. The results show that POKEx is the most efficient, achieving speedups of 21.21 times over terSIDH and 64.97 times over CSIDH. Details of our implementation are provided in Section 4.

with kernel γ(H1 ) and γ ′ : E1 → E3 be an isogeny with kernel ϕ(H2 ) : E0 E2

II. PRELIMINARY

This section introduces the background knowledge necessary for the paper. This section specifically discusses other isogeny-based key exchange algorithms in comparison with POKÉ. First, SIDH and the Castryck-Decru attack are introduced, followed by an introduction to the M-SIDH and bin/terSIDH that counters the Castryck-Decru attack. A. SIDH AND CASTRYCK-DECRU ATTACK 1) Outline of SIDH

Let p be a prime p = ℓeAA ℓeBB ± 1 for a relatively prime ℓA eB and ℓB , and ℓeAA ≈ ℓB . Then, select supersingular elliptic curve E over Fp2 having order (ℓeAA ℓeBB )2 . Let ⟨PA , QA ⟩ and ⟨PB , QB ⟩ be the basis of the torsion subgroup E[ℓeAA ] and E[ℓeBB ], respectively. E[ℓeAA ] is taken as Alice’s subgroup, and E[ℓeBB ] as Bob’s subgroup. Alice computes ⟨RA ⟩ = ⟨PA + [nA ]QA ⟩ using her private key nA . Then, Alice generates an isogeny ϕA : E → EA , where ker ϕA = ⟨RA ⟩, using the Velu’s formula. Alice also computes ϕA (PB ) and ϕA (QB ) and sends (ϕA (PB ), ϕA (QB ), EA ) to Bob. Bob follows a similar process and then sends (ϕB (PA ), ϕB (QA ), EB ) to Alice, where ϕB : E → EB = E/⟨RB ⟩. Using the points and curve received from Bob, Alice computes the group ′ ⟨RA ⟩ = ⟨ϕB (PA ) + [nA ]ϕB (QA )⟩ and obtains the image ′ curve EAB = EB /⟨RA ⟩ through the isogeny from EB ′ whose kernel is ⟨RA ⟩. Bob follows a similar process and ′ obtained EBA = EA /⟨RB ⟩. The shared secret key is the j-invariant of the image curves j(EAB ) = j(EBA ). 2) Castryck-Decru attack on SIDH

As supersingular elliptic curves are non-commutative, SIDH requires each party to apply their private key to the other party’s public key in order to derive the shared secret. The Castryck–Decru attack exploits this property, combining the leaked torsion-point information with Kani’s glue-and-split algorithm to break SIDH-based schemes in polynomial time. Let the two subgroups of the elliptic curve E0 whose orders are coprime to each other be H1 and H2 . Consider two isogenies ϕ and γ, where ϕ : E0 → E1 = E/H1 and γ : E0 → E2 = E/H2 . Let ϕ′ : E2 → E3 be an isogeny VOLUME 4, 2016

E1 γ′

γ

B. ORGANIZATION

This paper is organized as follows. In Section II, the background knowledge necessary for understanding this paper is provided. Section II, describes the SIDH, Castryck-Decru attack, M-SIDH and bin/terSIDH that counter the CastryckDecru attack. Section III describes POKÉ and POKÉ-based KEM. Section IV shows the implementation results, and the conclusion is drawn in Section V.

ϕ

ϕ′

E3

Let N = #H0 + #H1 and P0 , Q0 be the basis of E0 [N ]. Define P1 , Q1 , P2 and Q2 as follows: (P1 , Q1 ) = (ϕ(P0 ), ϕ(Q0 )) (P2 , Q2 ) = (γ(P0 ), γ(Q0 )) Define the following two-dimensional isogeny: ! ϕ γ̂ ′ : E0 × E3 → E1 × E2 ρ= −γ ϕ̂′ Kani prove that ρ is an isogeny with kernel H = ⟨([−d1 ]P0 , γ ′ ◦ ϕ(P0 )), ([−d1 ]Q0 , γ ′ ◦ ϕ(Q0 ))⟩ where d1 = #H1 . An isogeny between abelian surfaces of this form is called a (N, N )-isogeny. The Castryck-Decru attack divides a given isogeny path of smooth degree into several isogeny fragments of small degrees, and guesses each small isogeny with Kani’s lemma as a verification tool. If the computation of a two-dimensional isogeny ρ made up of a guessed isogeny path is a product of elliptic curves, then the guessing is correct; however, if it is an unsplit Jacobian curve, then the guessing is incorrect. This leads to a polynomial time attack on SIDH. B. M-SIDH

In [13], Fouotsa et al. proposed a masking-based countermeasure to mitigate the key recovery attack on SIDH. They proposed M-SIDH and MD-SIDH, which mask the torsion point information and the isogeny degree, respectively. This paper mainly focuses on M-SIDH, which uses a relatively smaller finite field than MD-SIDH for the same security level. The core of M-SIDH is to mask torsion point information using a random value α. Instead of sending ϕ(P ), ϕ(Q), each party transmits [α]ϕ(P ), [α]ϕ(Q). Let B denote the order of the torsion subgroup of the other party. Since the isogeny degree degϕ is fixed, the Weil pairing satisfies 2 eB ([α]P, [α]Q) = eB (P, Q)α deg ϕ . If α is used such that α2 ≡ 1 mod B, the other party can verify through the Weil pairing whether the masking was applied correctly. To prevent attackers from easily guessing α, the parameter B is selected so that the number of α that satisfy α2 ≡ 1 mod B is sufficiently large. 1) Parameter Generation

Let λ be a security level and t = t(λ) be an integer determined Q by λ. The prime pQ is of the form p = ABf − 1, t t where A = i=1 ℓi and B = i=1 qi . The ℓi s and qi s are all distinct prime numbers, A, B are relatively prime, A ≈ B ≈ √ p, and f is the cofactor. For a supersingular elliptic curve 3

Author et al.: Preparation of Papers for IEEE TRANSACTIONS and JOURNALS

E defined over Fp2 , let ⟨PA , QA ⟩ and ⟨PB , QB ⟩ be the basis of E[A] and E[B], respectively. Define µ2 (N ) as follows: µ2 (N ) = {x ∈ Z/N Z | x2 ≡ 1

mod N }

(1)

2) Public Key Generation

ϕA : E0 → EA defined by ⃗a, where deg ϕA | A. Alice computes the push-forward B′ of B on EA through ϕA and sends (EA , B′ ) to Bob. Bob follows a similar process and sends (EB , A′ ) to Alice with his secret vector ⃗b ∈ {0, 1, 2}t . 3) Shared secret

Alice selects random integers α and a in µ2 (B) and Z/AZ, respectively. Then, Alice computes an isogeny ϕA : E → EA , where ker ϕA = ⟨PA + [a]QA ⟩. Alice sends (EA , [α]ϕA (PB ), [α]ϕA (QB )) to Bob. Similarly, Bob selects random integers β and b in µ2 (A) and Z/BZ, respectively. Then, Bob computes an isogeny ϕB : E → EB , where ker ϕB = ⟨PB + [b]QB ⟩, and sends (EB , [β]ϕB (PA ), [β]ϕB (QA )) to Alice.

Upon receiving Bob’s public key (EB , A′ ), Alice checks that A′ is an artificial A-orientation on EB . If not, she aborts. Then, Alice computes the A′ -oriented isogeny ϕ′A : EB → EBA of degree A defined by ⃗a. Bob follows a similar process and computes the B′ -oriented isogeny ϕ′B : EA → EAB . The shared secret key between Alice and Bob is j(EAB ) = j(EBA ).

3) Shared Secret

In [23], the computation of a (2, 2)-isogeny becomes very fast based on the theta model, which leads to the twodimensional representation of an isogeny with an arbitrary degree. This randomized degree makes the Castryck-Decru attack infeasible. In [20], Basso proposed a fast key exchange scheme by combining the SIDH structure and the two-dimensional isogeny representation. In this section, we present the POKÉ encryption algorithm and the key exchange algorithm derived from it. Although the name POKÉ originates from POint-based Key Exchange, [20] does not explicitly describe a key exchange algorithm. Since a key exchange algorithm is as important as the performance analysis, we first explain the encryption process given in [20], and then describe the key exchange algorithm based on it. POKÉ uses a prime p of a form p = 2a 3b 5c f − 1 such that a ≈ λ, 3b ≈ 2λ/2 and 5c ≈ 2λ/3 . Let E0 : y 2 = x3 + x of j-invariant 1728 as the starting curve with known endomorphism ring. Let (P0 , Q0 ) be a 2a -torsion basis on E0 , (R0 , S0 ) be a 3b -torsion basis and (X0 , Y0 ) be a 5c -torsion basis.

III. POKÉ

Let (EB , RA , SA ) be the tuple Alice receives. Alice checks eA (RA , SA ) equals eA (PA , QA )B . If not, the algorithm terminates. Then, Alice computes an isogeny ϕ′A : EB → EAB = EB /⟨RA + [a]SA ⟩. Bob also computes eB (RB , SB ) and checks eB (RB , SB ) equals eB (PB , QB )B using the information (EA , RB , SB ) received from Alice. Then, Bob computes an isogney ϕ′B : EA → EBA = EA /⟨RB + [b]SB ⟩. The shared secret between Alice and Bob is j(EAB ) = j(EBA ). C. BIN/TERSIDH

In [14], they present binSIDH (binary SIDH) and terSIDH (ternary SIDH) as countermeasures against the Castryck–Decru attack. Both introduce the concept of artificial orientation and adopt new forms of secret keys. Among them, terSIDH provides about 1.6 bits of security per bit of the private key and offers reasonably fast execution. For this reason, we focus on terSIDH in this paper. An artificial A-orientation of a supersingular elliptic curve E over Fp2 is defined as a pair of cyclic subgroups A = (G1 , G2 ) of order A, where G1 , G2 ⊂ E[A] satisfying G1 ∩ G2 = {0}. The pair (E, A) is referred to as an artificial A-oriented curve. This notion enables the construction of isogenies whose kernels are direct sums of subgroups taken from G1 and G2 , that is, kernels of the form H1 ⊕ H2 with Hi ⊆ Gi . 1) Setup

Let λ be a security level and t = t(λ) be an integer determined Q by λ. The prime pQ is of the form p = ABf − 1, t t where A = i=1 ℓi and B = i=1 qi . The ℓi s and qi s are all distinct prime numbers, A, B are relatively prime, A ≈ B ≈ √ p, and f is the cofactor. Let E0 be a supersingular elliptic curve defined over Fp2 , A be an artificial A-orientation on E0 and let B be an artificial B-orientation on E0 . The public parameters are E0 , p, A, B, A, and B. 2) Public Key generation t

Alice samples a secret vector ⃗a from {0, 1, 2} , uniformly at random. Then, Alice computes the A-oriented isogeny 4

A. POKÉ ENCRYPTION ALGORITHM 1) Key Generation

Here, we adopt the heuristic version of the keygen algorithm in [20]. Alice computes an endomorphism θ ∈ End(E0 ) of degree 3b · q(2a − q) for some uniformly random value q ∈ [0, 2a ). Let θ = ϕ̂ ◦ ψ where deg ϕ = 3b and deg ψ = q(2a − q). Alice can computes the ϕ : E0 → EA by evaluating its kernel ker ϕ = ker θ ∩ E0 [3b ]. Since ψ = [3−b ] ◦ ϕ̂ ◦ θ, she can compute ψ. Alice chooses uniformly random scalars α, β ∈ [0, 2a ), γ ∈ [0, 3b ) and δ5 ∈ [0, 5c ). Alice’s public key is EA , (PA , QA ) = ([α]ψ(P0 ), [β]ψ(Q0 )), (RA , SA ) = ([γ]ψ(R0 ), [γ]ψ(S0 )), (XA , YA ) = ([δ5 ]ψ(X0 ), [δ5 ]ψ(Y0 )). Note that an attacker cannot recover the random scalars γ and δ5 since the degree of ψ is randomized. Alice’s secret key is α, β, δ5 , q. VOLUME 4, 2016

Author et al.: Preparation of Papers for IEEE TRANSACTIONS and JOURNALS

2) Encryption

Bob chooses a uniformly random scalar δ ∈ [0, 3b ) and computes isogenies ϕB : E0 → EB and ϕ′B : EA → EAB such that ker ϕB = ⟨R0 +[δ]S0 ⟩ and ker ϕ′B = ⟨RA +[δ]SA ⟩. For a uniformly random matrix D5 ∈ SL2 (Z/5c Z) and a uniformly random scalar ω ∈ [0, 2a ), Bob computes (PB , QB ) = ([ω]ϕB (P0 ), [ω −1 ]ϕB (Q0 )) (PAB , QAB ) = ([ω]ϕ′B (PA ), [ω −1 ]ϕ′B (QA )) (XB , YB ) = D5 · (ϕB (X0 ), ϕB (Y0 )) (XAB , YAB ) = D5 · (ϕ′B (XA ), ϕ′B (YA )). The ciphertext is EB , (PB , QB ), (XB , YB ), EAB , (PAB , QAB ), and ct = m ⊕ KDF(XAB , YAB ), where KDF is a key derivation function. 3) Decryption

Alice recovers the points (XAB , YAB ) and computes m from ct. The secrets q, α and β are used to compute the isogeny ψ ′ and δ5 is used to unmask the given torsion basis. Alice computes the message m as ′

′

(XAB , YAB ) = ([δ5 ]ψ (XB ), [δ5 ]ψ (YB )) m = ct ⊕ KDF(XAB , YAB ), where KDF is the key derivation function used in the encryption algorithm and ψ ′ : EB → EAB with a two-dimensional representation ker Ψ′ = ⟨(PB , [α−1 ]PAB ), (QB , [β −1 ]QAB )⟩. The overall process of POKÉ protocol is described as a diagram in Figure 1. P0 , Q0 ∈ E0 [2a ] R0 , S0 ∈ E0 [3b ] X0 , Y0 ∈ E0 [5c ] E0

Remark 1. POKÉ withstands the key recovery attack against SIDH. As discussed previously, the key recovery attack requires the following conditions: (1) access to the torsionpoint information published by SIDH-based cryptographic schemes, (2) knowledge of the degree of the isogeny connecting two elliptic curves, and (3) that this degree is powersmooth to enable an efficient attack. As can be seen in the algorithm description, the publicly revealed torsion points are masked by random values, thereby addressing condition (1). Furthermore, by employing isogenies of arbitrary degree, the scheme mitigates conditions (2) and (3). In addition, since the isogeny degree is both unknown and sufficiently large, POKÉ also resists the backdoor attack against FESTA described in [24]. B. POKÉ KEY ENCAPSULATION MECHANISM

As the author mentioned in [20], POKÉ public key encryption scheme can be converted to IND-CCA KEM by applying the Fujisaki-Okamoto (FO) transform [21]. However, the paper does not present an explicit construction. In this work, we provide a complete FO-based KEM design, including the full algorithms, which we refer to as POKEx. Algorithm 1 POKEx Key Genearation Require: The starting curve E0 and the bases ⟨P0 , Q0 ⟩ = E0 [2a ], ⟨R0 , S0 ⟩ = E0 [3b ], and ⟨X0 , Y0 ⟩ ∈ E0 [5c ] Ensure: (pk, sk) 1: Sample a random q ∈ [0, 2a ) such that q(2a − q) is coprime with 2, 3, and 5. 2: Generate a q(2a − q)-isogeny ϕ : E0 → EA . $ 3: Sample a random α2 , β2 ← − Z× 2a . $ . 4: Sample a random γ3 ← − Z× 3b $

×

5: Sample a random δ5 ← − Z5c . 6: Compute PA , QA = [α2 ]ϕ(P0 ), [β2 ]ϕ(Q0 ). 7: Compute RA , SA = [γ3 ]ϕ(S0 ), [γ3 ]ϕ(R0 ). 8: Compute XA , YA = [δ5 ]ϕ(X0 ), [δ5 ]ϕ(Y0 ).

PA , QA = [α]ϕ(P0 ), [β]ϕ(Q0 ) RA , SA = [γ]ϕ(R0 ), [γ]ϕ(S0 ) $ XA , YA = [δ5 ]ϕ(X0 ), [δ5 ]ϕ(Y0 ) 9: Sample a random s ← − {0, 1}256 . EA 10: Return sk = (q, α2 , β2 , δ5 , s) and ψ, deg ψ = q(2a − q)

pk = (EA , PA , QA , RA , SA , XA , YA ).

ϕ′B

ϕB

Algorithm 2 POKEx Key Encapsulation EB PB , Q B = [ω]ϕB (P0 ), [1/ω]ϕB (Q0 ) XB , YB = D5 · (ϕB (X0 ), ϕB (Y0 ))

ψ′

Require: A public key pk. Ensure: A shared key K and a ciphertext ct. $ ′ ′ 1: Sample a random message m ← − {0, 1}256 . = [ω]ϕB (PA ), [1/ω]ϕB (QA ) 2: ct ← POKE.ENC(pk, m; Gλ (m)). XAB , YAB ′ ′ 3: Return K = Hλ (m, ct). = D5 · (ϕB (XA ), ϕB (YA )) EAB

PAB , QAB

= [δ5 ]ψ ′ (XB ), [δ5 ]ψ ′ (YB )

FIGURE 1: The POKÉ protocol. Public parameters are in black; elements in red are part of the secret key or computed during decryption; orange parts are public keys; blue are ephemeral secrets; light blue are ciphertext parts; purple shows the shared secret. VOLUME 4, 2016

1) Setup and Key Generation

Let G = {Gλ } and H = {Hλ } be families of cryptographic hash functions such that Gλ : Mλ → Rλ and Hλ : {0, 1}∗ → Mλ , where Mλ denotes the message space and Rλ is the randomness space for the POKÉ encryption. 5

Author et al.: Preparation of Papers for IEEE TRANSACTIONS and JOURNALS

Algorithm 3 POKEx Key Decapsulation Require: A ciphertext ct, a public key pk, and a secret key sk Ensure: A shared key K 1: m ← POKE.DEC(sk, ct). 2: Compute ct′ ← POKE.ENC(pk, m; Gλ (m)). 3: if ct′ = ct then K ← Hλ (m, ct). 4: else K ← Hλ (s, ct). 5: end if 6: Return K.

Let ϕ : E0 → EA be an isogeny of degree q(2a − q), for some unknown value q ∈ [0, 2a ]. Write PA , QA = [α2 ] ϕ(P0 ),

[β2 ] ϕ(Q0 ),

RA , SA = [γ3 ] ϕ(R0 ),

[γ3 ] ϕ(S0 ),

XA , YA = [δ5 ] ϕ(X0 ),

[δ5 ] ϕ(Y0 ),

where α2 , β2 , γ3 , δ5 are uniformly random scalars from × × × Z× 2a × Z2a × Z3b × Z5c .

Let ψ : E0 → EB be an isogeny of degree 3b , and write ψ : EA → EAB for its pushforward ϕ∗ ψ. Write ′

For key generation, we compute (pk, sk) from the POKÉ key generation algorithm. We then choose a uniformly random dummy message s, and define the secret key as the pair (sk, s), while the public key is pk. 2) Key Encapsulation

Let m ∈ Mλ be a uniformly random message. The ciphertext is computed as ct ← Enc(pk, m; Gλ (m)), where Enc denotes the POKÉ encryption algorithm, and Gλ (m) provides the randomness used in the encryption. The shared key is derived as K ← Hλ (m, ct).

PB , QB = [ω2 ] ψ(P0 ),

[1/ω2 ] ψ(Q0 ),

′

PAB , QAB = [ω2 ] ψ (PA ), [1/ω2 ] ψ ′ (QA ),  T XB , YB = D5 ψ(X0 ), ψ(Y0 ) ,  T XAB , YAB = D5 ψ ′ (XA ), ψ ′ (YA ) , where ω2 is a uniformly random scalar from Z× 2a , and D5 is a uniformly random matrix from SL2 (Z5c ). Given (E0 , (P0 , Q0 ), (R0 , S0 ), (X0 , Y0 )) , (EA , (PA , QA ), (RA , SA ), (XA , YA )) , (EB , (PB , QB ), (XB , YB )) , (EAB , (PAB , QAB )) ,

3) Key Decapsulation

We extract m ← Dec(sk, ct) and compute ct′ ← Enc(pk, m; G(m)). If ct′ = ct, we compute the key K ← Hλ (m, ct). Otherwise, we compute K ← Hλ (s, ct). The following Algorithms 1, 2, and 3 correspond to the key generation (setup), Encapsulation, and Decapsulation procedures of POKEx, respectively. In Algorithm 1, Step 2 follows Algorithm 3 of [20] in our implementation. Within the algorithms, POKE.ENC denotes the POKÉ encryption (Algorithm 4 in [20]) and POKE.DEC denotes the POKÉ decryption (Algorithm 5 in [20]). The Figure 2 depicts the POKEx algorithm. 4) Security of POKEx

We briefly describe the security of POKEx. The outline is as follows. The security of POKÉ PKE is based on the hardness of the C-POKE problem in [20], and according to [20], it is IND-CPA secure PKE in the random oracle model under the assumption that the C-POKE problem is hard. By adopting the FO-transform, it is well-known that an IND-CCA secure KEM can be constructed from an IND-CPA secure PKE, which has been proven in [21]. This application has already been mentioned in [20], and that is what we call POKEx. For the security of POKEx, we only restate the security assumption and the relevant theorem on which the security of POKÉ PKE is based. Problem 1 (C-POKE). [20] Let E0 be a supersingular elliptic curve defined over Fp2 , with known endomorphism ring. Let P0 , Q0 be a basis of E0 [2a ], R0 , S0 a basis of E0 [3b ], and X0 , Y0 a basis of E0 [5c ]. 6

compute the points XAB , YAB . Theorem 1. [20] The POKÉ protocol, where the keyderivation function KDF is modeled as a random oracle, is IND-CPA secure in the random oracle model under the assumption that the C-POKE problem is hard. Proof. The proof follows directly from [20, Theorem 8]. Theorem 2. [25] For any IND-CCA adversary B against POKEx, issuing at most qG (resp. qH ) queries to the random oracle G (resp. H), there exists an IND-CPA adversary A against POKÉ PKE with 2qG + qH + 1 AdvIND-CCA + 3 · AdvIND-CPA POKEx (B) ≤ POKE-PKE (A), 2n where the size of the message space of PKE is 2n . Proof. POKÉ PKE is perfectly correct [26]. Hence, the proof follows directly from combining the results from Theorem 3.2 and Theorem 3.4 in [25]. IV. IMPLEMENTATION RESULTS

In this section, we present the comparison result of MSIDH, terSIDH, and POKÉ. We selected MSIDH, terSIDH, and CSIDH as comparison baselines for POKEx for the following reasons. MSIDH is regarded as more efficient than MD-SIDH among masked variants designed to counter the SIDH attacks, and terSIDH is considered the most efficient among alternative approaches that mitigate those attacks by introducing artificial orientation. Lastly, CSIDH is a CRSbased isogeny key exchange algorithm that is not affected by SIDH key-recovery attacks. Except for MSIDH, terSIDH, VOLUME 4, 2016

Author et al.: Preparation of Papers for IEEE TRANSACTIONS and JOURNALS

FIGURE 2: POKEx: POKÉ-based KEM KEM.KeyGen() $

q← − [0, 2a ) $

α2 , β2 ← − Z× 2a $

γ3 ← − Z× 3b $

δ5 ← − Z× 5c PA , QA ← [α2 ]ϕ(P0 ), [β2 ]ϕ(Q0 ) RA , SA ← [γ3 ]ϕ(S0 ), [γ3 ]ϕ(R0 ) XA , YA ← [δ5 ]ϕ(X0 ), [δ5 ]ϕ(Y0 ) $

s← − {0, 1}256 sk = (q, α2 , β2 , δ5 , s) pk = (EA , PA , QA , RA , SA , XA , YA ) KEM.Decap(ct, pk, sk) m ← POKE.DEC(sk, ct) ct′ ← POKE.ENC(pk, m; Gλ (m)) if ct′ = ct then return K ← Hλ (m, ct) else return K ← Hλ (s, ct)

KEM.Encap(pk) pk

−−−−−−−−−−−−−−−→

ct

←−−−−−−−−−−−−−−−−

POKEx, and CSIDH use parameters targeting NIST security level 1.

$

m← − {0, 1}256 ct ← POKE.ENC(pk, m; Gλ (m)) K ← Hλ (m, ct) return (K, ct)

The exact coefficients are available in [27]. 2) Parameter selection for terSIDH

A. PARAMETER SELECTION 1) Parameter selection for MSIDH

The parameters of MSIDH follow those specified in [27]. To follow NIST security level 1, MSIDH requires a large finite field of at least 5911 bits [13]. However, as denoted in [27], MSIDH still performs significantly slower than other SIDH variants. Therefore, [27] also used the 4096-bit parameters mainly to provide a rough performance estimate. Following the same approach, we also adopt the MSIDH-4096 parameters proposed in [27], targeting the classical 94-bit security level. For MSIDH-4096, the following 4095-bit prime number is used. p = 22 ℓ1 ℓ2 · · · ℓ417 − 1 Here, ℓ1 , · · · ℓ416 denote the first 228 odd prime numbers, and ℓ417 = 2897. Alice’s torsion subgroup has order A = 22 · ℓ1 ℓ3 · · · ℓ417 , while Bob’s torsion subgroup has order B = ℓ2 ℓ4 · · · ℓ416 . This choice of primes ensures that the subgroup orders of Alice and Bob are comparable in size and that the degrees of the corresponding isogenies align appropriately. The resulting parameters provide a classical security level of 94 bits and an estimated quantum security level of about 47 bits. Using this prime, M-SIDH uses the following curve as the starting curve defined over Fp2 = Fp [i], where i2 = −1: E : y 2 = x3 + M4095 · ix2 + x. VOLUME 4, 2016

Targeting NIST security level 1, the following 1570-bit prime number is used. p = 4 · 363 · ℓ1 ℓ2 · · · ℓ185 − 1 A=4 B=

92 Y

ℓ2i

i=1 93 Y

ℓ2i−1

i=1

where, ℓ1 · · · ℓ185 denote the first 185 odd prime numbers. Using this prime, terSIDH uses the following curve as the starting curve defined over Fp2 : E : y 2 = x3 + 6x2 + x. 3) Parameter selection for POKEx

For NIST security level 1, it uses a 431-bit prime number such as p = 2129 · 3164 · 518 − 1. The starting curve is E0 : y 2 = x3 + x defined over Fp2 such that j(E0 ) = 1728. B. PERFORMANCE RESULTS

First, we provide the uncompressed versions of public key and secret key sizes of M-SIDH, terSIDH, POKEx, and CSIDH at NIST security level 1. The CPU used for the measurements was an Intel Core i9-10980XE with a clock 7

Author et al.: Preparation of Papers for IEEE TRANSACTIONS and JOURNALS

TABLE 1: Public key and secret key sizes targeting NIST security level 1

log2 p pk size (B) sk size (B)

M-SIDH

terSIDH

POKEx

CSIDH-4096

ML-KEM-512

ECDH (secp256r1)

DH (MODP-2048)

5911 4434 369

1570 1178 24

431 324 54

4095 512 35

800 1632

256 65 32

2048 256 256

TABLE 2: Performance comparison of key exchange algorithms in C Classic Security Key exchange (ms)

MSIDH-4096 94 189,769.19

terSIDH 128 6,510.83

CSIDH-4096 128 19,941.20

speed of 3.0 GHz, and the tests were conducted on an Ubuntu 20.04 LTS operating system using the optimization level -O3 and the gcc 9.4.0 compiler. Also, for comparison with standardized algorithms from the NIST PQC competition as well as representative prequantum key establishment mechanisms, we selected MLKEM, ECDH, and DH. For the post-quantum setting, we chose ML-KEM-512, which achieves NIST security level 1 and corresponds to approximately 128-bit classical security. For pre-quantum algorithms, ECDH over the NIST P-256 (secp256r1) curve and DH-2048 were employed, both of which are commonly regarded as providing comparable 128bit classical security. All implementations used in this work are reference implementations. For ML-KEM, we adopted the official Round 3 reference implementation provided by the NIST PQC project. For ECDH and DH, we used the wolfSSL cryptographic library [28]. In particular, for finite-field Diffie–Hellman, we used the standardized MODP-2048 group (RFC 3526, Group 14), where public keys and shared secrets have a fixed size of 256 bytes. In Table 2, Key exchange denotes the total time required for Alice and Bob to establish a shared key. Specifically, Key exchange is the total time of the following four steps: 1) Alice generates her public value from her private key and sends it to Bob, 2) Bob generates his public value from his private key and sends it to Alice, 3) Alice computes the shared secret using Bob’s public value, and 4) Bob computes the shared secret using Alice’s public value. For the KEM algorithm, Key exchange is the total time of 1) Key generation, 2) Encapsulation, and 3) Decapsulation. As shown in Table 2, POKEx is the most efficient key exchange method among isogeny-based algorithms. First, MSIDH offers a lower security strength than the other algorithms and exhibits the slowest performance, indicating that it is impractical for real-world implementations. POKEx is about 64.97 times faster than CSIDH and about 21.21 times faster than terSIDH. These results show that POKEx currently provides the most efficient key exchange algorithm among isogeny-based cryptosystems. Nevertheless, when compared with other post-quantum cryptographic schemes and classical pre-quantum algorithms such as ECC- and DH-based key exchange, further per8

POKEx 128 306.95

ML-KEM-512 128 0.10

ECDH(secp256r1) 128 1.43

DH (MODP-2048) 128 2.26

formance improvements of POKEx are still required. In particular, compared to ML-KEM, POKEx exhibits considerably slower performance. However, as discussed in [29], ML-KEM suffers from a notable drawback: its substantially larger public keys and ciphertexts introduce non-negligible bandwidth overhead compared to ECDH, which has direct implications for practical protocol design. Recent TLS-level evaluations further corroborate this observation, showing that while ML-KEM offers excellent computational performance, it incurs a substantial bandwidth overhead due to its large public keys and ciphertexts, highlighting that rather than computation, communication cost remains a critical bottleneck in post-quantum protocol design [30]. In this respect, POKEx offers an important advantage that its key sizes are significantly smaller than those of MLKEM, resulting in reduced communication overhead. This bandwidth efficiency suggests that POKEx has considerable potential for further optimization and may serve as a competitive alternative in scenarios where both post-quantum security and communication efficiency are critical. V. CONCLUSION

This paper explicitly specified a POKÉ-based key encapsulation mechanism – POKEx – and evaluated its performance against representative isogeny-based key exchange algorithms at the same security level. Our comparison algorithms consist of M-SIDH, the most efficient masking-based countermeasure against SIDH key recovery attacks; terSIDH, the most efficient SIDH-variant with conceptually different countermeasure; and CSIDH, a CRS-based scheme that is unaffected by SIDH key recovery attacks. Targeting NIST security level 1, M-SIDH exhibited the slowest performance. POKEx outperformed terSIDH and CSIDH by factors of 21.21 and 64.97, respectively. These results show that POKEx is currently the most efficient isogeny-based key exchange algorithm. On the other hand, when compared with other postquantum cryptographic schemes and classical pre-quantum algorithms such as ECC- and DH-based key exchange, further performance improvements of POKEx are still required. Nevertheless, POKEx offers an important advantage over many PQC schemes in terms of key size, which can lead to reduced bandwidth consumption and lower communication VOLUME 4, 2016

Author et al.: Preparation of Papers for IEEE TRANSACTIONS and JOURNALS

overhead when deployed in practical settings such as TLS. This suggests that, with further optimization, POKEx has the potential to become a competitive candidate for postquantum key establishment. REFERENCES [1] J. M. Couveignes, “Hard homogeneous spaces.” IACR Cryptology ePrint Archive, no. 2006/291, 2006, [Online]. Available: https://eprint.iacr.org/2006/291. [2] D. Jao and L. De Feo, “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies,” in Proc. Int. Conf. Post-Quantum Cryptogr. (PQCrypto), 2011, pp. 19–34. [3] A. Childs, D. Jao, and V. Soukharev, “Constructing elliptic curve isogenies in quantum subexponential time,” Journal of Mathematical Cryptology, vol. 8, no. 1, pp. 1–29, 2014. [4] C. Costello, P. Longa, and M. Naehrig, “Efficient algorithms for supersingular isogeny Diffie-Hellman,” in Annual Cryptology Conference. Springer, 2016, pp. 572–601. [5] C. Costello, “The case for SIKE: a decade of the supersingular isogeny problem,” IACR Cryptology ePrint Archive, no. 2021/543, 2021, [Online]. Available: https://eprint.iacr.org/2021/543. [6] W. Castryck and T. Decru, “An efficient key recovery attack on SIDH,” in Proc. Adv. Cryptol. (EUROCRYPT). Springer, 2023, pp. 423–447. [7] C. Petit, “Faster algorithms for isogeny problems using torsion point images,” in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. (ASIACRYPT), 2017, pp. 330–353. [8] V. de Quehen, P. Kutas, C. Leonardi, C. Martindale, L. Panny, C. Petit, and K. E. Stange, “Improved torsion-point attacks on SIDH variants,” in Proc. Adv. Cryptol. (CRYPTO), 2021, pp. 432–470. [9] L. De Feo, C. Delpech de Saint Guilhem, T. B. Fouotsa, P. Kutas, A. Leroux, C. Petit, J. Silva, and B. Wesolowski, “Séta: supersingular encryption from torsion attacks,” in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. (ASIACRYPT), 2021, pp. 249–278. [10] T. B. Fouotsa, P. Kutas, S.-P. Merz, and Y. B. Ti, “On the isogeny problem with torsion point information,” in Proc. Public-Key Cryptogr. Conf. (PKC), 2022, pp. 142–161. [11] L. Maino, C. Martindale, L. Panny, G. Pope, and B. Wesolowski, “A direct key recovery attack on SIDH,” in Proc. Adv. Cryptol. (EUROCRYPT). Cham: Springer, 2023, pp. 448–471. [12] D. Robert, “Breaking SIDH in polynomial time,” in Proc. Adv. Cryptol. (EUROCRYPT). Cham: Springer, 2023, pp. 472–503. [13] T. B. Fouotsa, T. Moriya, and C. Petit, “M-SIDH and MD-SIDH: countering SIDH attacks by masking information,” in Proc. Adv. Cryptol. (EUROCRYPT). Cham: Springer, 2023, pp. 282–309. [14] A. Basso and T. B. Fouotsa, “New SIDH countermeasures for a more efficient key exchange,” in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. (ASIACRYPT). Springer, 2023, pp. 208–233. [15] A. Basso, P. Dartois, L. D. Feo, A. Leroux, L. Maino, G. Pope, D. Robert, and B. Wesolowski, “SQIsign2D–West,” in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. (ASIACRYPT), 2024, pp. 339–370. [16] K. Nakagawa, H. Onuki, W. Castryck, M. Chen, R. Invernizzi, G. Lorenzon, and F. Vercauteren, “SQIsign2D-East: A new signature scheme using 2-dimensional isogenies,” in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. (ASIACRYPT), 2024, pp. 272–303. [17] M. Duparc and T. B. Fouotsa, “SQIPrime: A dimension 2 variant of SQISignHD with non-smooth challenge isogenies,” in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. (ASIACRYPT), 2024, pp. 396–429. [18] M. Chen, A. Leroux, and L. Panny, “SCALLOP-HD: Group action from 2dimensional isogenies,” in Proc. Public-Key Cryptogr. Conf. (PKC), 2024, pp. 190–216. [19] L. Panny, C. Petit, and M. Stopar, “KLaPoTi: An asymptotically efficient isogeny group action from 2-dimensional isogenies,” IACR Communications in Cryptology, vol. 2, no. 3, 2025. [20] A. Basso and L. Maino, “POKÉ: A compact and efficient PKE from Higher-Dimensional Isogenies,” in Proc. Adv. Cryptol. (EUROCRYPT), S. Fehr and P.-A. Fouque, Eds. Cham: Springer, 2025, pp. 94–123. [21] E. Fujisaki and T. Okamoto, “Secure integration of asymmetric and symmetric encryption schemes,” in Proc. Adv. Cryptol. (CRYPTO), 1999, pp. 537–554. VOLUME 4, 2016

[22] H. Kim, S. Hong, and S. Kim, “INKE: Fast isogeny-based PKE using intermediate curves,” IACR Cryptology ePrint Archive, no. 2025/1458, 2025, [Online]. Available: https://eprint.iacr.org/2025/1458. [23] P. Dartois, L. Maino, G. Pope, and D. Robert, “An algorithmic approach to (2, 2)-isogenies in the theta model and applications to isogeny-based cryptography,” in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. (ASIACRYPT), K.-M. Chung and Y. Sasaki, Eds., 2025, pp. 304–338. [24] W. Castryck and F. Vercauteren, “A polynomial time attack on instances of M-SIDH and FESTA,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2023, pp. 127–156. [25] D. Hofheinz, K. Hövelmanns, and E. Kiltz, “A modular analysis of the Fujisaki-Okamoto transformation,” in Proc. Theory Cryptogr. Conf. (TCC), 2017, pp. 341–371. [26] N. A. Idris, Y. Abdulsalam, and M. Hedabou, “Transforming the POKE public key protocol into a key encapsulation mechanism,” IACR Cryptology ePrint Archive, no. 2025/1616, 2025, [Online]. Available: https://eprint.iacr.org/2025/1616. [27] S. Kim, “Performance and efficiency evaluation of M-SIDH,” IEEE Access, 2024. [28] wolfSSL Inc., “wolfSSL embedded SSL/TLS library,” https://https:// github.com/wolfSSL/wolfssl, 2026, accessed: 2026-01-09. [29] D. Stebila, “Security analysis of the imessage PQ3 protocol,” IACR Cryptology ePrint Archive, no. 2024/357, 2024, [Online]. Available: https://eprint.iacr.org/2024/357. [30] J. A. Montenegro, R. Rios, and J. López-Cerezo, “A performance evaluation framework for post-quantum TLS,” Future Generation Computer Systems, vol. 175, p. 108062, 2025.

HYEONHAK KIM received the B.A. degree in cybersecurity from Korea University, in 2017. He is currently pursuing the Ph.D. degree in the School of Cybersecurity, Korea University, with a focus on post-quantum cryptography, especially isogeny-based cryptosystems, and quantum algorithms.

SUHRI KIM received her B.A. degree in mathematics and M.A. in information security from Korea University in 2014 and 2016, respectively. She received her Ph.D. degree in the Graduate School of Information Security at Korea University in 2020. She currently holds the position of Associate Professor in the School of Mathematics, Statistics and Data Science at Sungshin Women’s University. Her research focuses on post-quantum cryptography and efficient computations for isogenybased cryptosystems.

9

Related documents

• Algorithm Implementation Requirements and Usage Guidance for the Internet Key Exchange Protocol Version 2 (IKEv2)#476289
• Key Management Considerations for the TCP MD5 Signature Option#193185
• E3C: A Tool for Evaluating Communication and Computation Costs in Authentication and Key Exchange Protocol#1117191
• ECMA-415 — NFC-SEC test methods (December 2016)#600215
• The Lightweight User Datagram Protocol (UDP-Lite)#142020