🔢 mathematics

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

This paper introduces MCSI, a two-message key exchange protocol built on the CSIDH class group action that utilizes authenticated encryption to blind ephemeral keys, thereby achieving implicit mutual authentication, hiding ephemeral elements from eavesdroppers, and significantly reducing computational overhead by allowing recipients to discard unauthenticated messages before expensive group action evaluations.

Original authors: Furkan Cifci (M.Emin Sarac High School), Osman Emre Donder (Bilkent University), Reyyan Cifci (King Fahd University of Petroleum and Minerals)

Published 2026-08-25✓ Author reviewed ⓘ

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Furkan Cifci (M.Emin Sarac High School), Osman Emre Donder (Bilkent University), Reyyan Cifci (King Fahd University of Petroleum and Minerals)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the race to secure the world's digital communications against future quantum computers, cryptographers are exploring a landscape built not on large numbers, but on the geometry of curves. Imagine a vast, flat field where every point represents a unique mathematical shape called an elliptic curve. In this field, there is a special rule that allows one shape to be transformed into another in a way that is easy to do if you know the secret path, but nearly impossible to reverse if you do not. This is the foundation of isogeny-based cryptography. Unlike other methods that rely on massive keys, this approach uses tiny keys, making it highly efficient for storage and transmission. However, a major vulnerability was discovered in a related system a few years ago, forcing researchers to rethink how these curves are used. The challenge has become finding a way to exchange secret keys using these tiny, geometric shapes without revealing any information that could be exploited by a powerful observer, all while ensuring that the two parties are truly who they claim to be.

A team of researchers has introduced a new protocol called MCSI, which stands for Masked Commutative Supersingular Isogeny Key Exchange. This system is designed to let two people, let's call them Alice and Bob, establish a shared secret key over an open network without an eavesdropper learning anything about the temporary values they use during the conversation. The innovation lies in how they hide these temporary values. In previous attempts, the temporary values were sent in plain sight, requiring the receiver to perform a complex and time-consuming mathematical operation to check if the message was valid. This created a security risk: a malicious attacker could flood a server with fake messages, forcing it to waste its computing power on useless calculations. MCSI solves this by wrapping the temporary value in a secure, authenticated envelope. Before the receiver even opens the envelope to check the math, it verifies a digital seal. If the seal is broken or missing, the message is discarded immediately, saving the receiver from doing the heavy lifting. This simple change protects the system from being overwhelmed by bad actors.

The researchers proved that this method works perfectly every time when both parties follow the rules, with zero errors in the final key. They also demonstrated that the temporary values inside the envelope remain hidden from anyone listening in, and that the digital seal effectively prevents an attacker from tampering with the message. Crucially, the security of the system does not rely on a mathematical assumption that has been shown to be false for this specific type of curve. Instead, it relies on the difficulty of solving a specific puzzle involving the arrangement of these curves, a problem that remains hard even for quantum computers. The team also showed that a common idea—adding a simple layer of random byte substitutions to the encrypted message to make it look more random—adds no real security at all, a finding that helps streamline future designs.

To ensure their theory held up in the real world, the team built the system twice, once in a high-level programming language and once in a low-level language used for fast software. They ran thousands of tests, comparing the results of both versions to ensure they matched perfectly. Their measurements revealed that the new protocol is a working reference implementation, with the time spent on the encryption and decryption layers being so small it is almost invisible compared to the time needed for the core mathematical operations. However, they also found a significant weakness in their own code. Because the time it takes to perform the core calculation depends on the secret key itself, an attacker who can measure the time of many different sessions could potentially guess parts of the secret key. The researchers were explicit about this flaw: their current implementation is not safe for real-world deployment until it is rewritten to run in constant time, meaning the duration of the calculation must be the same regardless of the secret key.

The paper also addressed a common misconception about which mathematical primes should be used for this system. Many experts have used specific large prime numbers for other types of encryption, assuming they would work here too. The researchers proved that one of the most famous primes, used in a standard curve called P-521, is completely unusable for this specific type of key exchange. They showed that the mathematical structure required for their system simply does not exist with that prime, forcing the use of a different, specially constructed number. This finding is vital for anyone trying to build such a system, as it prevents the use of a standard tool that would lead to a broken design.

While the protocol successfully hides the temporary values and prevents denial-of-service attacks, the authors are careful to state what they have not yet proven. They have not shown that the system remains secure if an attacker can reveal the temporary secrets used during a session, nor have they proven that the system is safe against an attacker who can actively interfere with the messages in more complex ways. Furthermore, the hiding of the temporary values is not forward secret; if an attacker steals a long-term secret key in the future, they could go back and strip the protection from old recorded messages to see the temporary values, though the final session key would likely remain safe. The researchers conclude that while MCSI is a solid specification with a working reference implementation, it is not yet ready for the public. The path forward requires building a version that runs in constant time to close the timing leak, and proving that the system can withstand more aggressive attacks. Until those steps are taken, the protocol described here is a specification with a working reference, and not something anyone should deploy.

Technical Summary: MCSI – A Masked Commutative Supersingular Isogeny Key Exchange

1. Problem Statement

The paper addresses the design of a post-quantum authenticated key exchange (AKE) protocol based on the Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) action. While CSIDH offers the smallest public keys among post-quantum families, standard unauthenticated exchanges over this group action suffer from two primary issues:

Denial of Service (DoS) Vulnerability: In a standard exchange, a responder must evaluate the expensive group action (taking tens of milliseconds) on a curve provided by the initiator before verifying the message's authenticity. An unauthenticated attacker can force the responder to perform this costly computation repeatedly.
Lack of Ephemeral Confidentiality: Standard CSIDH exchanges transmit the ephemeral public element (the curve) in the clear, allowing passive eavesdroppers to observe the intermediate state of the key exchange.

Furthermore, the paper clarifies a common misconception: unlike the SIDH branch of isogeny cryptography, the commutative CSIDH branch does not publish torsion point images. Therefore, "masking" in this context is not a countermeasure against torsion-point attacks (which broke SIDH) but a mechanism to hide the ephemeral public element and prevent DoS.

2. Methodology and Protocol Design

The authors propose MCSI (Masked Commutative Supersingular Isogeny), a two-message key exchange protocol that integrates the CSIDH group action with authenticated encryption.

Core Mechanism

Static Keys: Both parties possess long-term static key pairs $(a, pk_A)$ and $(b, pk_B)$ derived from the CSIDH class group action.
Static-Static Shared Value ( $Z_{ss}$ ): Before any session, parties compute a shared value $Z_{ss} = (ab) \star x_0$ using their static secrets and the peer's static public key. Due to the commutativity of the class group, both parties derive the same $Z_{ss}$ .
Blinding Layer: The static-static shared value $Z_{ss}$ is used to derive a symmetric key for Authenticated Encryption with Associated Data (AEAD).
Protocol Flow:
1. Initiator: Generates an ephemeral secret $u$ , computes the ephemeral public element $T_A = u \star x_0$ , and encrypts $T_A$ using the AEAD scheme keyed by $Z_{ss}$ . The ciphertext is sent.
2. Responder: Decrypts the message using the cached key derived from $Z_{ss}$ . If the authentication tag fails, the responder aborts immediately after a single hash/tag check, avoiding the expensive group action evaluation. If valid, the responder recovers $T_A$ , generates its own ephemeral secret $w$ , computes $T_B = w \star x_0$ , and encrypts $T_B$ to send back.
3. Key Derivation: Both parties compute the session key using a hash of the transcript and three shared values:
  - $Z_{ee} = (uw) \star x_0$ (Ephemeral-Ephemeral, providing forward secrecy).
  - $Z_{es} = (ub) \star x_0$ (Ephemeral-Static, providing authentication).
  - $Z_{se} = (aw) \star x_0$ (Static-Ephemeral, providing authentication).
  - $Z_{ss}$ (Static-Static, used for masking).

Design Rationale

The paper explicitly rejects deriving the blinding key from the session secret itself, as this creates a circular dependency. Instead, it relies on the pre-shared static-static value. The authors also prove that adding a public byte-substitution layer (S-box) to the ciphertext provides no additional security, justifying the use of standard AEAD without such modifications.

3. Key Contributions

The paper makes the following specific contributions:

Protocol Specification: A complete specification of MCSI over an abstract effective group action, instantiated with CSIDH. It includes a design argument proving that the blinding key must be derived from static secrets, not the session secret.
Correctness Proof: A theorem proving zero-error correctness, relying strictly on the commutativity of the class group, the group action axioms, and the uniqueness of the Montgomery curve representative.
Security Proofs: Three security theorems in the Random Oracle Model (ROM), all reducing to the Strong Parallelisation Assumption (GA-StCDH):
- Session Key Indistinguishability: The session key is indistinguishable from random against a passive adversary.
- Blinding Confidentiality: The ephemeral elements are hidden from passive observers.
- Transport Integrity: An adversary without static secrets cannot forge a message that the recipient accepts.
- Note: The proofs explicitly avoid the Decisional Group Action Assumption (GA-DDH), which is known to be false for CSIDH due to genus theory.
Parameter Analysis: A critical analysis of prime selection. The authors demonstrate that primes chosen for standard elliptic curve discrete logarithm problems (e.g., NIST P-521, where $p = 2^{521}-1$ ) are unusable for CSIDH because $p+1$ lacks the necessary smoothness (small prime factors) to generate an efficiently evaluable class group action.
Reference Implementation: A dual implementation in portable C and Python, cross-verified using known answer vectors.
Side-Channel Audit: A detailed measurement of the reference implementation's timing behavior, revealing that the unoptimized implementation leaks the private key's one-norm through execution time.

4. Results and Measurements

Performance and Overhead

Cost: The protocol requires four group action evaluations per party per session (plus one cached evaluation per peer for $Z_{ss}$ ). This is a factor of two higher than an unauthenticated CSIDH exchange, but the symmetric layer (AEAD) costs negligible time (~~4 $\mu$ s) compared to the group action (~~130 ms).
DoS Mitigation: The primary performance gain is in DoS resistance. An unauthenticated message is rejected after a tag check (~~2.4 $\mu$ s) rather than after a group action evaluation (~~130 ms), a speedup of roughly 50,000x.
Sizes: MCSI offers significantly smaller public keys than lattice-based (ML-KEM) or code-based (Classic McEliece) alternatives. For the 512-bit security level, the public key is 64 bytes, and the total session traffic is 192 bytes.

Implementation Findings

Timing Leaks: The reference implementation is not constant-time. The authors measured a strong correlation (Pearson 0.90) between the private key's one-norm and the execution time.
Leakage Severity: Two keys with one-norms differing by only 5 (out of a possible 370) can be distinguished with approximately 200 timing measurements.
Validation: The Validate function (checking if a curve is supersingular) was found to be free of secret-dependent control flow in the audit, though the group action evaluation itself leaks information by construction.

5. Significance and Limitations

The paper positions MCSI as a specification with a working reference implementation, explicitly not a deployment-ready solution.

Significance:

It demonstrates that authenticated key exchange over CSIDH is feasible with implicit mutual authentication and ephemeral confidentiality.
It provides a rigorous proof that the "masking" of ephemeral elements does not rely on the broken decisional assumption (GA-DDH).
It highlights the critical, often overlooked, constraint that primes for commutative isogeny schemes must be constructed specifically for smoothness, not chosen from existing ECC standards.

Explicit Limitations (What the paper does not prove):

Forward Secrecy of Blinding: If an adversary later obtains a static secret, they can recompute $Z_{ss}$ and strip the blinding from recorded transcripts to reveal the ephemeral elements.
Strong Security Models: The proofs do not cover the Canetti-Krawczyk (CK) or extended CK models (e.g., resistance to ephemeral key reveal or key compromise impersonation).
Active Adversaries: While transport integrity is proven, full session key security against an active adversary controlling message delivery is not established.
Implementation Security: The reference implementation is not constant-time and is vulnerable to timing attacks. The authors state that a constant-time implementation is a prerequisite for deployment.
Malicious Peers: The protocol does not include a Fujisaki-Okamoto transform to protect against a peer holding a valid static key but behaving maliciously.

In conclusion, MCSI provides a theoretically sound, efficient, and small-footprint design for post-quantum key exchange, but the authors emphasize that the current implementation requires significant hardening (specifically constant-time execution) before it can be considered secure for real-world use.