Digital signature schemes based on isogenies are among the most compact signatures achieving post-quantum security.Recent advances, especially those leveraging higher-dimensional isogenies, have also made such schemes practically efficient.However, comparatively little attention has been devoted to endowing these signatures with additional privacy-enhancing properties, such as the re-randomization of keys and the adaptation of signatures to new public keys.Although some results exist in the isogeny group action setting, these signatures suffer from a subexponential quantum attack which renders them rather inefficient.In this work, we initiate the first systematic study of privacy-enhancing isogeny-based signatures outside the group-action framework.We base our exploration on the notion of signatures with randomizable keys (SWRKs) developed by Celi et al. (FC'24), which aims to unify privacy notions related to key updatability and signature adaptation.In particular, we analyze which of their privacy notions can be achieved from the state-ofthe-art signatures SQIsign, PRISM and the hash-and-sign signature scheme derived from the Deuring verifiable unpredictable function (DeuringVUF).To this end, we naturally extend SQIsign to an SWRK scheme that allows key randomization, and enhance both PRISM and the DeuringVUF signature to additionally allow for message adaptation.We show that, due to the deterministic nature of the signatures, the DeuringVUF signature achieves perfect adaptability.We formally prove all three of our modifications achieve unlinkability against unbounded adversaries, and remain unforgeable under the same assumptions as the original schemes.Compared to the group-action-based schemes, however, these signatures provide less flexibility, making advanced functionalities in general harder to build.Exacerbating this, the lack of overarching frameworks often results in advanced constructions that tend to be somewhat ad-hoc and largely scheme-dependent.Contributions.In this work, we address these issues and present three novel isogeny-based signatures with randomizable keys.Our constructions build upon SQIsign [1], PRISM [5] and the signature obtained from the DeuringVUF [44, §5.2].We present our constructions in a unified framework, by abstracting away the heavy machinery of the Deuring correspondence, and relying on a set of high-level algorithms that are shared among the three signatures.Concretely, our contributions are the following.
Digital signature schemes based on isogenies are among the most compact signatures achieving post-quantum security.Recent advances, especially those leveraging higher-dimensional isogenies, have also made such schemes practically efficient.However, comparatively little attention has been devoted to endowing these signatures with additional privacy-enhancing properties, such as the re-randomization of keys and the adaptation of signatures to new public keys.Although some results exist in the isogeny group action setting, these signatures suffer from a subexponential quantum attack which renders them rather inefficient.In this work, we initiate the first systematic study of privacy-enhancing isogeny-based signatures outside the group-action framework.We base our exploration on the notion of signatures with randomizable keys (SWRKs) developed by Celi et al. (FC'24), which aims to unify privacy notions related to key updatability and signature adaptation.In particular, we analyze which of their privacy notions can be achieved from the state-ofthe-art signatures SQIsign, PRISM and the hash-and-sign signature scheme derived from the Deuring verifiable unpredictable function (DeuringVUF).To this end, we naturally extend SQIsign to an SWRK scheme that allows key randomization, and enhance both PRISM and the DeuringVUF signature to additionally allow for message adaptation.We show that, due to the deterministic nature of the signatures, the DeuringVUF signature achieves perfect adaptability.We formally prove all three of our modifications achieve unlinkability against unbounded adversaries, and remain unforgeable under the same assumptions as the original schemes.Compared to the group-action-based schemes, however, these signatures provide less flexibility, making advanced functionalities in general harder to build.Exacerbating this, the lack of overarching frameworks often results in advanced constructions that tend to be somewhat ad-hoc and largely scheme-dependent.Contributions.In this work, we address these issues and present three novel isogeny-based signatures with randomizable keys.Our constructions build upon SQIsign [1], PRISM [5] and the signature obtained from the DeuringVUF [44, §5.2].We present our constructions in a unified framework, by abstracting away the heavy machinery of the Deuring correspondence, and relying on a set of high-level algorithms that are shared among the three signatures.Concretely, our contributions are the following.
The potential development of large-scale quantum computers has raised serious concerns about the security of classical cryptographic systems.In response, the field of post-quantum cryptography has emerged to design cryptographic schemes that remain secure even against quantum adversaries.Isogeny-based cryptography is the most recent addition to post-quantum cryptography and started garnering attention in the 2010s.Digital signature schemes are a fundamental part of public key cryptography, providing authenticity, integrity, and non-repudiation for digital messages.They are essential for secure communication, software updates, electronic transactions, and virtually all systems requiring trust and verification.Although the traditional digital signature scheme consists only of a single prover and verifier, numerous variants have been developed over the years to address specific needs, such as multi-signatures, ring signatures, group signatures, and proxy signatures.These variants extend the functionality of traditional signatures to support more complex security models in real-world applications, such as contact tracing.As isogeny-based cryptography is a relatively young research field, many commonly used cryptographic primitives, such as variants of signature schemes, have not yet been fully developed or widely implemented.This leaves room for exploration and optimization in designing secure and efficient isogeny-based alternatives, while taking advantage of its strength with its small keys and signature compared to other post-quantum based constructions such as lattice.Multi-signature schemes have been extensively studied for decades and form a well-established area of research in cryptography.These schemes enable a group of users to collaboratively generate a single, compact signature on a shared message, ensuring that all designated parties have approved the content.Their efficiency and security properties make them particularly valuable in applications such as blockchain transactions and distributed systems.Active security in multi-signature schemes requires the signature to be unforgeable even in the worst-case scenario, where malicious signers would collude to generate a multi-signature in a group with a single honest signer.Our first contribution is to propose an actively secure isogeny-based multi-signature scheme.Proxy signature schemes have been the subject of extensive research over the years, offering cryptographic solutions for secure delegation of signing authority.These schemes allows an original signer to designate a proxy signer to generate signatures on their behalf, within the limitations imposed by the original signer.Such mechanisms are particularly useful in settings like secure communications, delegated access control, and corporate approval systems where it is essential for operations to continue even in the absence of the designated signer.Proxy I would like to express my deepest gratitude to everyone who has supported me throughout my Ph.D. journey.First and foremost, I am deeply grateful to my supervisor, Professor Atsuko Miyaji, for giving me a chance to experience the field of research as an exchange student before accepting me once again as a Ph.D student.Her invaluable support and guidance throughout the course of those 3 years as a Ph.D student enabled me to make it this far.Additionally, I am deeply grateful to the NEC Corporation for its C&C Fellowship, as well as the Jisedai Program.Their generous support eased my financial burdens, allowing to focus completely on my research.I am also deeply grateful to the professors, staff, and colleagues at Miyaji Lab, who were always there whenever I needed it.I want to especially thank Hide Miyaji, for welcoming me with open arms as soon as I arrived for the first time in Japan and supporting me throughout my Ph.D journey.I am also profoundly grateful to Mohamed Bourefis, my French comrade, who shares a very similar
Advances in quantum computing have heightened concerns about information security in the post-quantum era. While traditional cryptographic schemes rooted in number- theoretic assumptions (e.g., integer factorization, elliptic curve discrete logarithm, and discrete logarithm problems) remain foundational to modern security infrastructures, their vulnerabilities in quantum computing environments have become apparent. To address this, researchers have shifted focus toward quantum-resistant mathematical problems. Among these, isogeny-based cryptography has emerged as a strong candi- date within the five primary post-quantum cryptographic approaches, garnering sig- nificant academic interest. Recent progress in isogeny-based cryptographic schemes includes SIDH (though recent cryptanalysis by Castryck and Decru has compromised its security), CSIDH, and SQISign. Despite progress, the inherent structural characteristics of isogenies impose limitations on design flexibility compared to other post-quantum alternatives. The goal of the thesis is to develop isogeny-based cryptographic protocols with ad- vanced functionalities. We develop isogeny-based blind signatures based on techniques from CSIDH, CSI-FiSh, and other works. We also develop ring signature schemes us- ing SQISign. Finally, we develop a verifiable encryption scheme (based on CSIDH) and bit commitment scheme (based on the Charles–Goren–Lauter isogeny-based hash function). For both schemes, we give ways to prove to a verifier that the encrypted/ committed bits satisfy a given Boolean equation.
A novel post-quantum threshold oblivious signature scheme is presented. Oblivious signatures enable a requester to obtain a signature on a single selected message from a set of candidates without revealing the selection to the signer. Unlike blind signatures, the signer may be aware of the candidate set. To mitigate single-point failures the scheme employs Shamir’s secret sharing to distribute signing authority among multiple participants. To address quantum threats, it leverages isogeny-based cryptography founded on the Group Action Inverse Problem for post-quantum resilience. The construction adapts an existing isogeny-based oblivious signature by introducing a trusted dealer. The signing protocol is multi-party; verification confirms signature validity on the selected message without revealing secret information. Security reduces to the hardness of Group Action Inverse Problem and the security of the secret-sharing scheme in the semi-honest model, covering corrupted dealers, users, and coalitions of fewer than the threshold number of signers. The threshold design eliminates dependence on a single signer, preventing unauthorized signatures after key compromise. Theoretical contributions advance threshold cryptography with post-quantum primitives; practical applications include anonymous voting, secure transactions, and privacy-preserving distributed systems. Future directions include malicious adversary models and integrations with other post-quantum primitives.
Our modern world is dependent on online communications and transactions. To ensure privacy in these digital actions, it is extremely common to use protocols such as the Diffie-Hellman key exchange scheme. Unfortunately, these systems have been shown to be vulnerable to attacks from a quantum adversary. This means that an overhaul of the field of cryptography is needed in order to anticipate and mitigate this threat.Over the past years, the community has begun to answer this call by proposing and analyzing new techniques that are conjectured to be quantum safe. One such example is the study of cryptographic group actions. These mappings mimic some of the structure from the Diffie-Hellman protocol,but abstract it enough so that new mathematical operations can be employed that avoid quantum attacks. Currently, the main examples of group actions come from isogenies, codes, and lattices.In order for a protocol to be used in the real-world we would hope for it to be secure, fast, and requiring little storage. This means that in these early stages of research and development of cryptographic group actions, it is essential to begin to answer some of the questions surrounding security and efficiency. This thesis contributes to this effort by focusing on these aspects across different group actions that have been proposed for use in the literature.It is certainly true that each individual group action needs its own study of security. When designers are trying to achieve some advanced functionalities in a protocol, they may sometimes alter the underlying security assumptions.Each time this is done, the new assumptions need their own careful study as well. In this thesis we consider four different variants of group action security assumptions spanning the isogeny, tensor, linear code, and matrix code group actions. We analyze their security by either offering concrete attacks or giving a polynomial time reduction to a more well-studied assumption. This helps to indicate whether a problem is appropriate for use in cryptography, and what parameters to use if so.In addition to security, this thesis is also inscribed in the effort to study the efficiency of group actions by including three works studying the isogeny group action and related subroutines. They span the core isogeny problem for oriented elliptic curves, evaluating isogenies from a kernel generator, and supersingularity testing. With an effort from the community to improve overall runtimes, we can hope to get closer to reasonable speeds for real-life use.By studying the security and efficiency of cryptographic group actions, this thesis shines light on group actions as a promising framework for post-quantum cryptographic solutions.
Blind signatures are fundamental cryptographic primitives enabling privacy-preserving authentication and have seen renewed interest in the post-quantum literature. Existing efficient constructions predominantly rely on Fischlin’s generic paradigm instantiated over lattice assumptions, while blinding techniques for Σ-protocol-based blind signatures remain sparse beyond lattices. Moreover, achieving provable concurrent security under polynomially many sessions has been a longstanding open challenge for this approach in the post-quantum literature as evidenced by the recent attacks in EC’24 and PKC’24. This work broadens the landscape of post-quantum blind signatures by introducing novel techniques and proposing four frameworks based on general cryptographic group actions, without requiring commutativity. Our constructions admit instantiations under diverse post-quantum assumptions, including CSIDH (isogeny-based), LESS (code-based, NIST round-two), and more. These frameworks offer flexible trade-offs in assumptions (from interactive one-more to the standard inversion problem) and key/signature sizes, and culminate in a construction that achieves security under polynomially many concurrent sessions. This enables the first efficient blind signatures from isogenies and codes with provable concurrent security with 4.5 and 64.7 KB respectively. We also outline several directions for optimization and further instantiations for future work.
We propose and develop new schemes for post-quantum cryptography based on isogenies over elliptic curves. First we show that ordinary elliptic curves are have less than exponential security against quantum computers. These results were used as the motivation for De Feo, Jao and Pl\\^ut's construction of public key cryptosystems using supersingular elliptic curve isogenies. We extend their construction and show that isogenies between supersingular elliptic curves can be used as the underlying hard mathematical problem for other quantum-resistant schemes. For our second contribution, we propose is an undeniable signature scheme based on elliptic curve isogenies. We prove its security under certain reasonable number-theoretic computational assumptions for which no efficient quantum algorithms are known. This proposal represents only the second known quantum-resistant undeniable signature scheme, and the first such scheme secure under a number-theoretic complexity assumption. Finally, we also propose a security model for evaluating the security of authenticated encryption schemes in the post-quantum setting. Our model is based on a combination of the classical Bellare-Namprempre security model for authenticated encryption together with modifications from Boneh and Zhandry to handle message authentication against quantum adversaries. We give a generic construction based on Bellare-Namprempre for producing an authenticated encryption protocol from any quantum-resistant symmetric-key encryption scheme together with any digital signature scheme or MAC admitting any classical security reduction to a quantum-computationally hard problem. We apply the results and show how we can explicitly construct authenticated encryption schemes based on isogenies.