🔢 mathematics

A Compact Post-quantum Strong Designated Verifier Signature Scheme from Isogenies

This paper proposes a new compact, post-quantum strong designated verifier signature scheme based on (abelian) cryptographic group actions and isogenies, ensuring that only the designated verifier can confirm a signature's authenticity.

Original authors: Farzin Renan, Wendi Gao, Jason T. LeGrow

Published 2026-09-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Farzin Renan, Wendi Gao, Jason T. LeGrow

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 or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital world, trust is usually a public affair. When you sign a document online, a digital signature acts as a seal that anyone with the right tools can verify. This transparency is the backbone of modern security, ensuring that a message truly came from its sender and has not been altered. However, there are situations where this public nature is a flaw rather than a feature. Imagine a private conversation between two people where one wants to prove their identity to the other, but must ensure that no third party can ever be convinced that the message came from them. If the recipient could prove the origin to a judge or a friend, the privacy of the exchange would be broken. This is the challenge of "designated verifier" signatures: creating a proof that is undeniable to the intended recipient but completely unconvincing to anyone else.

The difficulty deepens when we consider the future. The encryption methods that currently protect our data rely on mathematical problems that are hard for today's computers but could be solved easily by powerful quantum machines. As scientists race to build systems that can withstand these future threats, they are turning to a branch of mathematics involving the shapes of curves and the ways they can be transformed into one another. These transformations, known as isogenies, offer a new foundation for security that is believed to be safe from quantum attacks. The goal is to build a system that not only survives the quantum era but also preserves the delicate privacy of designated conversations.

A team of researchers has now introduced a new method for creating these private, quantum-safe signatures. They call their system CSI-SDVS, a scheme built on the properties of commutative supersingular isogenies. The core idea is to use the unique mathematical relationship between elliptic curves to create a signature that only the intended recipient can verify. In this system, the sender and the recipient each hold a secret key and a corresponding public key. When the sender wants to sign a message, they use their secret key and the recipient's public key to generate a unique code. The recipient can then use their own secret key to check if the code is valid. The brilliance of the design lies in its ability to simulate. The recipient can also use their secret key to generate a signature that looks exactly like one from the sender. Because the recipient can create a perfect fake, they cannot prove to a third party that a specific signature came from the sender rather than being created by themselves. This property, known as non-transferability, ensures that the conversation remains private even if the recipient tries to share the evidence.

The researchers demonstrated that their new scheme is not only secure against quantum computers but also highly efficient. In previous attempts to build similar systems, the digital keys and signatures were often enormous, requiring hundreds of kilobytes of data to store or transmit. This made them impractical for many real-world applications. The new design, however, is remarkably compact. Using a specific set of parameters known as CSIDH-512, the researchers achieved a system where the secret keys are 256 bits long, the public keys are 512 bits, and the signatures themselves are also just 512 bits. To put this in perspective, a standard digital signature in older systems might be the size of a small text file, whereas this new signature is roughly the size of a single line of text. This dramatic reduction in size makes the technology viable for use on devices with limited memory and bandwidth.

The team proved that their system meets all the rigorous security standards required for this type of cryptography. They showed that an attacker cannot forge a signature without the secret keys, and they proved that the identity of the signer remains hidden from anyone other than the designated verifier. These proofs rely on the assumption that solving certain mathematical problems related to the group actions of these curves is computationally impossible, even for a quantum computer. The researchers also explored a specific mathematical model to show that the security of their system could be tied to a slightly different, but equally hard, problem. This dual-layered approach strengthens the confidence in the system's robustness.

By combining the privacy of designated verification with the efficiency of isogeny-based cryptography, this work offers a practical solution for secure, private communication in a post-quantum world. It moves the field from theoretical possibilities to concrete, usable tools. The researchers have shown that it is possible to have a signature that is strong enough to be trusted by the recipient, yet weak enough to be denied to everyone else, all while keeping the data small enough to be used anywhere. This balance of privacy, security, and efficiency marks a significant step forward in preparing our digital infrastructure for the challenges of the future.

Technical Summary: A Compact Post-quantum Strong Designated Verifier Signature Scheme from Isogenies

Problem Statement

Digital signatures traditionally provide non-repudiation, meaning any party with access to a signer's public key can verify a signature's authenticity. While useful for many applications, this property is undesirable in scenarios requiring "off-the-record" communication, where a signer (Alice) wishes to authenticate a message to a specific recipient (Bob) without enabling Bob to prove to a third party that the message originated from Alice.

To address this, Strong Designated Verifier Signatures (SDVS) were introduced. An SDVS scheme ensures that only the designated verifier can verify the signature's authenticity. Crucially, it satisfies non-transferability: the designated verifier can simulate signatures that are computationally indistinguishable from real ones, preventing them from convincing a third party of the signature's validity. Furthermore, SDVS schemes must satisfy Privacy of Signer's Identity (PSI), ensuring that given a valid signature and multiple candidate public keys, no third party can determine which key was used to sign.

While SDVS schemes exist in classical cryptography (based on bilinear pairings or Schnorr signatures), they are vulnerable to quantum attacks via Shor's algorithm. Existing post-quantum proposals based on codes or lattices often suffer from large key and signature sizes (e.g., $O(\lambda^2)$ complexity) or have been shown to fail non-transferability properties. Recent isogeny-based proposals have faced security breaks (e.g., SIDH) or rely on assumptions that may not be as robust as desired.

Methodology

The authors propose CSI-SDVS, a new SDVS scheme based on the Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) group action. The construction leverages the algebraic structure of the ideal class group acting on the set of supersingular elliptic curves over a finite field $\mathbb{F}_p$ .

Core Components

Group Action Setup: The scheme operates within an effective group action $(G, X, *)$ , where $G$ is the ideal class group of an order in an imaginary quadratic field, and $X$ is the set of supersingular elliptic curves. The action is free and transitive.
Key Generation:
- The signer and verifier generate secret keys ( $sk_S, sk_V$ ) as random integers in $\mathbb{Z}_N$ (where $N$ is the class number).
- Public keys are generated by applying the group action to a base curve $E$ : $pk_S = [g^{sk_S}] * E$ and $pk_V = [g^{sk_V}] * E$ .
Signing and Simulation:
- Signing: To sign a message $m$ , the signer chooses a random $z \in \mathbb{Z}_N$ , computes $Y = [g^{z+sk_S}] * pk_V$ , and sets the signature $\sigma = (h, z)$ where $h = H(Y || m)$ .
- Simulation: The verifier, possessing $sk_V$ , can simulate a signature by choosing a random $z$ , computing $Y = [g^{z+sk_V}] * pk_S$ , and setting $\sigma = (h, z)$ with $h = H(Y || m)$ .
- Correctness: Due to the commutativity of the group action, $[g^{z+sk_S}] * pk_V = [g^{z+sk_S+sk_V}] * E = [g^{z+sk_V}] * pk_S$ . Thus, the value $Y$ computed by the signer and the simulator is identical, ensuring both produce valid signatures for the same hash input.
Verification: The verifier checks if $h = H([g^{z+sk_V}] * pk_S || m)$ .

Key Contributions

Compact Post-Quantum SDVS: The paper presents CSI-SDVS, an efficient SDVS scheme with $O(\lambda)$ complexity for keys and signatures. Using CSIDH-512 parameters, the scheme achieves:
- Secret Key: 256 bits.
- Public Key: 512 bits.
- Signature: 512 bits.
  This represents a significant improvement over prior lattice-based SDVS schemes which often have $O(\lambda^2)$ sizes, and isogeny-based schemes with larger public keys.
Security Proofs in ROM and AGAM:
- Non-Transferability (NT): Proven unconditionally, as the distributions of real and simulated signatures are identical.
- Strong Unforgeability (SUF-CMA) and PSI: Proven secure in the Random Oracle Model (ROM) under the Group Action Decisional Diffie-Hellman (GA-DDH) assumption.
- Tight Reductions: The authors further prove that in the Algebraic Group Action Model (AGAM), the SUF-CMA and PSI security of CSI-SDVS reduce tightly to the Group Action Inverse Problem (GAIP), a computational problem rather than a decisional one.
Security Analysis: The scheme is shown to satisfy all standard SDVS security definitions (NT, SUF-CMA, PSI) without relying on the broken SIDH protocol, utilizing the currently believed secure CSIDH group action.

Results

The paper provides formal security proofs demonstrating that:

The scheme is unconditionally non-transferable.
Under the GA-DDH assumption in the ROM, the scheme is strongly unforgeable and provides privacy of the signer's identity.
Under the GAIP assumption in the AGAM and ROM, the scheme achieves tight reductions for both SUF-CMA and PSI security.
Performance: Table 1 in the paper compares CSI-SDVS against prior works (Sun et al. [26] and Khuc et al. [12]). CSI-SDVS offers the smallest public key (512 bits) and signature (512 bits) among the compared post-quantum schemes, while maintaining a secret key size of 256 bits.

Significance

The authors position CSI-SDVS as a practical and secure solution for post-quantum designated verifier signatures. The significance lies in:

Efficiency: It achieves compact parameters suitable for resource-constrained environments, addressing the size limitations of previous lattice-based and isogeny-based proposals.
Robustness: By basing the security on the GAIP (a computational assumption) in the AGAM, the scheme avoids reliance on decisional assumptions which can sometimes be weaker or less intuitive in the group action setting.
Completeness: The work provides a full security analysis covering all three pillars of SDVS (non-transferability, unforgeability, and signer privacy) in a post-quantum setting, filling a gap left by previous schemes that either failed non-transferability or suffered from inefficiency.

The paper concludes that CSI-SDVS offers a balanced trade-off between security and efficiency, making it a viable candidate for applications requiring quantum-resistant, non-transferable authentication.