PaperlayerView exact revision on arXiv

Source-linked AI summary

MCSI: A Masked Commutative Supersingular Isogeny Key Exchange with Blinded Ephemeral Keys

Furkan Cifci, Osman Emre Donder, Reyyan Cifci

arXiv:2608.22360v1cs.CRmath.NT

TL;DR

MCSI addresses the cost and exposure of direct CSIDH key exchange by encrypting ephemeral public elements under a static-static-derived key. The paper proves correctness and several security properties, evaluates implementations, and shows that parameter selection must be tailored to the class group action.

  • Problem

    Direct CSIDH key exchange makes responders perform expensive group-action evaluations on sender-chosen data, while post-quantum cryptography also needs alternatives to a single mathematical family.

  • Method

    MCSI uses authenticated encryption to transmit each ephemeral public element under a key derived from the static-static shared value, with validation of static and recovered elements.

  • Results

    The protocol is correct with zero error and its session-key, blinded-element confidentiality, and transport-integrity claims reduce to strong parallelisation in the random oracle model; standard elliptic-curve primes may admit no usable class group action.

  • Takeaways & Limitations

    MCSI provides a two-message CSIDH-based exchange whose security claims do not rely on the decisional group action assumption and whose parameters must be chosen for the action itself.

  • Takeaways & Limitations

    The blinding is not forward secret, security under ephemeral key reveal is not established, and the paper makes no claim of a specific NIST security category.

Abstract

from arXiv · show

We introduce MCSI, a two message key exchange we design over the CSIDH class group action, in which each party sends its ephemeral public element under an authenticated encryption keyed by the value the two static keys determine. The design gives implicit mutual authentication, hides the ephemeral element from an eavesdropper, and lets a recipient discard an unauthenticated message after one tag check rather than after an evaluation of the group action, which is four orders of magnitude more expensive. On the analytic side, we prove that our protocol is correct with zero error, and prove three statements in the random oracle model, all reducing to the strong parallelisation problem: indistinguishability of the session key against a passive adversary, confidentiality of the blinded ephemeral element, and integrity of the blinded transport. None uses the decisional group action assumption, which is false for class group actions of non-prime discriminant. We also show that a blinding key cannot come from the session secret it is meant to establish. To instantiate the design we select parameters and show that a prime chosen for elliptic curve discrete logarithms is unusable: for $p = 2^{521}-1$, the NIST P-521 prime, the action admits no efficiently evaluable generator. On the practical side, we build and test the design. We implement the protocol twice, in C and independently in Python, cross check the two, and measure what a session costs in field operations, time and memory. We also audit our code for secret dependent control flow: the field arithmetic and the symmetric layer show none, while the group action leaks the key by construction, and two hundred timings separate two keys whose one-norms differ by five out of 370. Finally, we state what we do not prove, among them security under ephemeral key reveal, forward secrecy of the blinding, and constant time execution.

1 Introduction

The paper motivates MCSI as a masked key exchange over CSIDH that addresses expensive unauthenticated work while avoiding assumptions broken for non-prime discriminants. It provides correctness, security analyses, parameter guidance, implementation measurements, and explicit scope boundaries.

  • Isogeny landscape: CSIDH avoids the SIDH torsion-disclosure attack by using a commutative class-group action over prime-field curves and publishing only one field element per public key.Its remaining concerns include costly action evaluation and disputed concrete quantum-security estimates.
  • Protocol design: MCSI encrypts each ephemeral public element under a cached static-static value, enabling implicit mutual authentication and rejection after one tag check without evaluating a group action.The masking layer also hides the ephemeral element from observers.
  • Protocol design: The design specifies an abstract group-action protocol and shows that its blinding key cannot be derived from the session secret it is intended to establish.The protocol uses authenticated encryption rather than a malleable bare keystream and validates recovered group-action elements.
  • Analysis: The paper proves zero-error correctness and three random-oracle security statements reducing to strong parallelisation, without using the decisional group-action assumption.That decisional assumption is false for the CSIDH instantiation because its discriminant is non-prime.
  • Parameters and implementation: For p = 2^521 - 1, the NIST P-521 prime, the class-group action has no efficiently evaluable generator because p + 1 is a power of two.The paper also reports cross-checked C and Python implementations, measured costs, and a timing audit, while claiming no constant-time execution or new hardness assumption.
  • Open scope: The paper explicitly leaves security under ephemeral-key reveal, forward secrecy of blinding, and constant-time execution unproved.It also avoids assigning a NIST security category, tying security to the underlying group action at each parameter set.

2 Preliminaries

The preliminaries distinguish the relevant elliptic-curve settings, define the class-group action and isogeny machinery, and state the authenticated-encryption and hardness framework used later. They emphasize that supersingularity over the prime field supplies the commutative structure, while Vélu evaluations require small-degree kernels.

  • Notation and models: The notation fixes p, finite fields, Frobenius, elliptic curves, torsion, imaginary-quadratic orders, class groups, ideals, and random-oracle hashing.Montgomery models provide a canonical one-field-element representative for protocol curves.
  • Supersingular curves: Supersingularity concerns p-torsion, whereas a nonzero discriminant only ensures that a Weierstrass equation defines a smooth curve.The paper’s example over F_101 is smooth but ordinary, showing why smoothness does not identify supersingular curves.
  • Supersingular curves: For a supersingular curve over F_p, equivalent characterisations include p dividing the Frobenius trace, trace zero, #E(F_p) = p + 1, and a quaternionic endomorphism ring.The starting curve E_0: y^2 = x^3 + x is supersingular whenever p ≡ 3 (mod 4).
  • Isogenies: An isogeny is a nonconstant elliptic-curve morphism preserving the point at infinity, with a dual whose composition with it is multiplication by its degree.Separable isogenies are determined by Galois-stable kernels and can be computed using Vélu’s formulae.
  • Isogenies: Vélu’s formulae apply only away from kernel points and cost Θ(deg φ) field operations, so large-degree isogenies must be composed from many small-degree steps.The square-root Vélu algorithm reduces the asymptotic cost but does not remove degree dependence.
  • Endomorphism rings and class-group action: Over F_p, the rational endomorphism ring is an order in an imaginary quadratic field, unlike the noncommutative quaternionic endomorphism ring over the algebraic closure.The class group then acts freely and transitively on the relevant supersingular curves, supplying the commutative exchange structure.
  • Cryptographic framework: The protocol avoids the decisional group-action assumption because genus-theoretic characters break it for the CSIDH class group of discriminant -4p.Security arguments instead use hashed values in the random-oracle model and a computational assumption.
  • Cryptographic framework: The masking layer is modeled as authenticated encryption with associated data, providing ciphertext indistinguishability and ciphertext integrity notions for the protocol.Its inputs are a key, nonce, associated data, and message; decryption either recovers the message or rejects.

3 The MCSI protocol

MCSI builds a two-message exchange on a commutative class-group action, using static-key-derived authenticated encryption to mask ephemeral elements and reject unauthenticated inputs before expensive action evaluation.

  • Design rationale: MCSI uses a class-group action rather than an iterated isogeny walk, because iterated trajectories are undefined or noncommutative.The construction relies on the abelian class group acting on a torsor.
  • Design rationale: A blinding key derived from the session secret would be circular, so MCSI derives masking keys from the static-static shared value computed before the session.The shared value is computed once per peer and can be cached.
  • Design rationale: Static-key-derived masking makes MCSI implicitly authenticated, requires authentic static public-key distribution, and does not provide forward secrecy for the blinding.The session key remains dependent on ephemeral secrets.
  • The masking layer: Public byte substitutions add no security, while unauthenticated XOR masking is malleable; therefore MCSI uses authenticated encryption for the masked payload.Bit flips in a bare keystream layer produce corresponding payload changes.
  • The masking layer: MCSI encodes group-action elements, validates recovered elements, and derives two direction-specific masking keys from canonically ordered static public keys.Separate directional keys prevent cross-direction nonce collisions and reflection.
  • The protocol: A replayed first message can make a responder perform work, although transcript binding and fresh responder randomness prevent repeated session keys.Caching recently seen nonces is suggested to reject repeats.
  • The protocol: MCSI performs four group-action evaluations per session, versus two per party for unauthenticated Diffie–Hellman over the same action.The extra evaluations provide implicit mutual authentication and ephemeral-element blinding.

4 Correctness

MCSI correctness follows deterministically from commutativity, the group-action axioms, and unique element representations: honest parties recover each other’s ephemeral elements and derive the same key with zero error.

  • Correctness conditions: Correctness uses exactly commutativity, genuine group-action composition, and unique representations of elements of X.The unique representation ensures equal action results produce equal encodings.
  • Protocol execution: The cached context supplies static secrets, the static shared value, directional keys, and both public keys to every session procedure.The per-session algorithms then process encrypted messages and derive shared values.
  • Protocol execution: With unmodified messages and honest static keys, authenticated decryption recovers valid ephemeral elements, so neither party aborts.The associated data binds labels, public keys, and nonces.
  • Correctness proof: Commutativity makes the three ephemeral/static shared values agree, while transcript binding makes the final hash input identical.The common values are Z_ee, Z_es, and Z_se.
  • Correctness result: MCSI has correctness error zero when authenticated encryption is perfectly correct.The proof contains no probabilistic step.
  • Correctness boundaries: Non-unique restricted secret representations affect secret distributions, requiring statistical-distance accounting in the security analysis but not correctness.The action is evaluated on the represented class.

5 Security analysis

The security analysis proves three properties in the random oracle model, all reducing to strong parallelisation, while explicitly leaving ephemeral-reveal security unproved.

  • Security results: The proved properties are passive session-key indistinguishability, passive confidentiality of the blinded ephemeral element, and active integrity of the blinded transport.The analysis identifies security under ephemeral-secret or session-state reveal as outside its proved results.
  • Security results: All three proofs use the random oracle model and reduce to the strong parallelisation problem, not the decisional group-action assumption.The decisional assumption is false for the stated instantiation.

5.1 Security model

The security model gives the adversary passive transcript access with Execute, Reveal, and Test oracles, and restricts the proved claims to fresh sessions without corruption or reveal.

  • Adversary model: The model is Bellare–Rogaway style and deliberately restricts the adversary to passive transcript observation.The adversary does not deliver chosen messages to honest parties.
  • Oracles: Execute returns honest-session transcripts, Reveal returns session keys, and Test returns either the real key or a random string.The Test oracle is asked once.
  • Freshness: A tested session is fresh only if neither party was corrupted before completion and neither it nor its partner was revealed.Freshness excludes the corresponding Reveal and Corrupt cases.
  • Scope: The model omits chosen-message delivery and ephemeral-secret or intermediate-state exposure, so it does not establish full authenticated-protocol security.These restrictions are retained to delimit exactly what the proof covers.

5.2 Indistinguishability of the session key

The proof replaces the tested session key with a random string and bounds the distinguishing gap by detecting a critical random-oracle query through the strong parallelisation problem. A weaker post-corruption result covers passive adversaries, but active-session forward secrecy is not claimed.

  • Theorem 5.2 proves session-key indistinguishability against passive adversaries in the stated uncorrupted-session model.
  • The game sequence guesses a tested session, replaces its key with an independent random string, and isolates the bad event where the real key is queried.
  • The reduction simulates the modified game without knowing the challenge group elements and uses the decision oracle to detect the critical query.
  • The strong variant avoids an additional q_H guessing loss; ordinary GA-CDH yields the weaker bound q_s q_H · Adv_CDH.
  • After later corruption of both static secrets, the session key remains indistinguishable for passive sessions, but security against an active adversary is not claimed.

5.3 Confidentiality of the blinded ephemeral element

MCSI hides ephemeral payloads by encrypting them under static-static masking keys. The confidentiality proof replaces those keys with independent random strings and then reduces payload replacement to authenticated-encryption chosen-plaintext security.

  • A passive observer does not learn the ephemeral elements T_A and T_B, formalized by comparing real transcripts with transcripts carrying unrelated payloads.
  • Theorem 5.5 proves confidentiality through reductions to the strong parallelisation problem and the chosen-plaintext security of the masking scheme.
  • Replacing the two masking keys by independent uniform strings is justified because the static-static value is a GA-CDH value for the parties’ public keys.
  • With distinct nonces, replacing true payloads by uniform elements costs two chosen-plaintext distinguishing games, one per direction.
  • For 128-bit random nonces, nonce collisions are negligible for realistic q_s, but repeated nonces under a fixed masking key expose the XOR of two ephemeral elements.

5.4 Integrity of the blinded transport

The transport-integrity theorem bounds acceptance of adversarially delivered messages by reductions to the strong parallelisation problem and ciphertext integrity. Associated data and transcript hashing bind messages, identities, and sessions together.

  • Theorem 5.7 considers an adversary that observes honest sessions and delivers a chosen message to an uncorrupted recipient.
  • The bound reduces to the strong parallelisation assumption and the authenticated-encryption scheme’s ciphertext-integrity advantage, symmetrically in both directions.
  • A recipient accepts only when decryption succeeds, so an unproduced accepted message is a ciphertext forgery under the direction-specific masking key.
  • Only a holder of a static secret can compute the static-static value and produce a message that the peer accepts.
  • The second message’s associated data includes the first, while session-key derivation hashes the full transcript and both identities.

5.5 Resistance to known attacks

MCSI’s security arguments rely on computational rather than decisional assumptions, and its transmitted data avoid the torsion disclosures behind SIDH attacks. However, static-key adaptive attacks involving malicious legitimate peers and timing leakage remain outside the demonstrated protection.

  • The proofs reduce to the computational strong parallelisation assumption, while the decisional assumption is false for the relevant non-prime-discriminant class group actions.
  • Unlike SIDH, CSIDH transmits no torsion images; its public element is a complete curve-class description without torsion information.
  • MCSI blinding protects the identity of the ephemeral element, not against torsion-point key-recovery attacks.
  • Theorem 5.7 and validation block unauthenticated chosen-element attacks, but legitimate malicious peers remain outside the protection described for static-key protocols.
  • The implementation’s group action leaks key information through timing: correlation with key one-norm is 0.90, and 200 timings separate keys differing by five out of 370.

5.6 What we do not prove

The paper explicitly limits its claims across security models, forward secrecy, malicious peers, parameter confidence, and implementation security. These boundaries identify where the theorems, construction, and implementation do not suffice.

  • Security models: The security theorem does not cover ephemeral-secret revelation, session-state revelation, or key compromise impersonation in Canetti–Krawczyk-style models.Theorem 5.2 covers observed sessions and corruption of parties outside the tested session, but not these exposures.
  • Active attacks: The active-security result bounds accepted-message injection but does not establish session-key security under adversarial delivery, reordering, and interleaving.Theorem 5.7 rules out the most obvious active attacks, but its guarantee is narrower than full active security.
  • Forward secrecy: Later compromise of either static secret lets an adversary recompute Z_ss and remove transcript blinding, recovering ephemeral elements.Only the session key retains a weak guarantee under Theorem 5.4; no forward-secret blinding schedule is known here.
  • Malicious peers: A valid static-key holder can choose an adversarial ephemeral element within X, and the paper does not apply the Fujisaki–Okamoto transform needed to handle this case.Validation rejects elements outside X, but not malicious choices inside the valid set.
  • Parameter confidence: The paper makes no concrete quantum-security claim for its smallest parameter set because published estimates disagree substantially.It reports the disagreement rather than selecting one estimate.
  • Implementation security: The reference implementation is not constant time and provides no proved protection against power analysis, fault injection, or residual secrets in memory.The authors measure timing leakage but do not build a constant-time implementation or erase secrets.

6 Parameter selection

Parameter selection must make the class-group action efficiently evaluable, which requires suitable small odd factors of p+1 and enough exponent vectors to cover the class group. This criterion rules out NIST P-521 and leaves quantum security levels unsettled for the smallest set.

  • Prime selection: Efficient action evaluation requires p+1 to have many small odd prime factors, because each such factor supplies a cheaply computable kernel and Θ(ℓ)-cost Vélu evaluation.The relevant ideals are 𝔩=(ℓ, π−1) for odd primes ℓ dividing p+1.
  • Prime selection: Parameter primes of the selected form satisfy p≡3 (mod 8), making E₀: y^2=x^3+x supersingular and yielding one-field-element public keys.The construction uses distinct small odd primes ℓ_1,...,ℓ_n.
  • NIST P-521: For p=2^521−1, p+1=2^521, so only the 2-isogeny is efficiently available and no usable class-group generator results.If the class has full order, evaluation needs about 2^260 sequential steps; otherwise the reachable set is incomplete, so neither case is usable.
  • NIST P-521: Prime-selection criteria for elliptic-curve discrete logarithms and class-group actions are unrelated: the latter specifically requires smooth p+1.A prime suitable for P-521 therefore provides no evidence of suitability for MCSI; CSURF still needs the odd part of p+1.
  • Parameter construction: Private keys use exponent vectors in {−m,...,m}^n, with (2m+1)^n chosen to cover approximately √p classes, while action cost is at most mn small-degree isogenies.For CSIDH-512, n=74 and m=5 give approximately 2^256 vectors and at most 370 isogeny steps.
  • Sampling: Uniform sampling from an exponent box is not exactly uniform on the class group because distinct vectors can represent one class with unequal multiplicities.The security statements assume uniform secrets, while the original proposal justified the induced distribution heuristically.
  • Validation: Validation tests supersingularity and is mandatory for received static and ephemeral elements, but costs about 2.1 ms for CSIDH-512.This is roughly one twentieth of a group-action evaluation on the cited platform.
  • Larger parameters: The last parameter row uses m=1, forcing n≳1292 for a 4096-bit prime and making action evaluation correspondingly more expensive.The covering condition is 3^n≳√p, requiring roughly thirteen hundred small primes.

7 Implementation and measurements

The reference implementations quantify MCSI’s costs and expose a sharp contrast between its inexpensive symmetric layer and expensive class group actions. The audit finds no secret-dependent control flow in the field arithmetic or symmetric layer, but timing measurements reveal leakage from the group action and repeated static-key use.

  • Implementation: Two independently implemented versions, in C and Python, were cross-checked using known answer vectors and published hash-primitives test vectors.The implementations were also evaluated for measured costs and private-key-dependent timing.
  • Memory: 75 136 bytes of scratch space dominate working memory, while a complete session uses zero heap bytes, 7 680 bytes of stack, and about 100 kilobytes overall.The scratch space is fixed by the parameter set and supports inversion-free Vélu evaluation.
  • Symmetric-layer cost: 4.2 μs for authenticated encryption is negligible against 1132 ms for a session containing four such operations.The symmetric layer is about one part in 10^5 of a session; the main overhead relative to unauthenticated exchange is the factor of two in action evaluations.
  • DoS-resistance motivation: 2.4 μs rejects an invalid tag without a group action, versus 130 ms for the unauthenticated action path, a factor of about 50 000.The masking layer lets a responder stop after tag verification rather than evaluating the action on unauthenticated input.
  • Timing leakage: 0.90 Pearson correlation links running time to the group-action key’s one-norm, and one timing observation recovers about one bit about that norm.The implementation takes 0.13 ms for the all-zero key and 256 ms for the largest permitted key, a factor of about two thousand.
  • Timing leakage: Two hundred timings distinguish keys whose one-norms differ by five out of 370, while the symmetric layer remains below detection after two hundred thousand measurements per class.The fixed-key leakage is especially relevant because MCSI reuses the same static secret in PeerCtx and every session; the fixed-versus-random test is weaker than comparing fixed keys.

8 Related work

Related work places MCSI in the commutative CSIDH branch, distinguishes it from SIDH and prior authenticated exchanges, and explains its proof setting and design lineage.

  • SIDH’s published torsion images enabled key-recovery attacks, whereas CSIDH publishes no torsion data.
  • MCSI differs from prior authenticated CSIDH exchanges by hiding ephemeral curves rather than sending them in the clear.
  • Because the decisional assumption fails for class group actions of non-prime discriminant, the proofs use computational assumptions in the random oracle model.
  • The paper transfers the established static–ephemeral authenticated-encryption pattern to the CSIDH setting without claiming that pattern as novel.

9 Conclusion and open problems

The conclusion reports MCSI’s protocol, security, implementation, and parameter results, then identifies costs, unsupported security properties, and priorities for future work.

  • MCSI encrypts each ephemeral public element under a key derived from the static-static shared value and proves correctness with zero error.
  • Three random-oracle theorems establish passive session-key indistinguishability, blinded-element confidentiality, and blinded-transport integrity under strong parallelisation.
  • The protocol was implemented independently in portable C and Python, cross-checked with known-answer vectors, and evaluated for operation, time, memory, branching, and timing leakage.
  • The commutative class-group action, not generic isogeny composition, supplies the commutativity required for the paper’s correctness theorem.
  • The blinding key must predate the session, requiring static keys and authentic public-key distribution while providing no forward secrecy for the blinding.
  • The NIST P-521 prime admits no usable class group action, so parameters must be chosen specifically for the commutative isogeny action.
  • The main open problems are security under ephemeral-key reveal, forward-secret blinding, and a constant-time implementation.
Loading 2608.22360v1…