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
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
Public key cryptography plays a pivotal role in maintaining digital security and privacy, with its foundations built on the hardness of certain mathematical problems. However, the emergence of quantum computing threatens the security of current cryptographic systems, making the adoption of post-quantum cryptography (PQC) an urgent necessity. Digital signature schemes are essential components in secure communications, providing authentication, non-repudiation, and data integrity. This paper examines the state of post-quantum digital signature schemes across various cryptographic approaches, including lattice-based, code-based, multivariate polynomial-based, hash-based, symmetric-key-based, and isogeny-based systems, alongside advancements in Multi-Party Computation in the Head (MPC-in-the-head) schemes. The paper then explores application-specific signatures such as blind, undeniable, threshold, chameleon, aggregate, and ring signatures, explaining their main use cases and the existing post-quantum cryptographic classifications that support these constructions individually. Software implementations of selected prominent PQC digital signature schemes were carried out, and their performance was systematically analysed using metrics such as bandwidth consumption, latency, and computational efficiency. These results provide key observations regarding the suitability of different schemes for both resource-constrained and high-performance environments. Subsequently, a detailed literature review of implementations on embedded and hardware platforms is presented, focusing on ARM-based devices and FPGA accelerators to evaluate deployment feasibility beyond general-purpose processors. Based on the software and implementation-level findings, a comparative analysis across software, embedded, and hardware platforms is conducted to highlight architectural influences on performance, scalability, and practicality. Furthermore the cryptanalytic attacks on post-quantum digital signature schemes across various PQC classifications are examined in this paper, taking into account both classical and quantum adversarial models. To evaluate realistic security constraints, implementation-oriented vulnerabilities such as side-channel and fault-based attacks are also examined. In addition, the applicability of post-quantum digital signature schemes within TLS, IoT, and related practical deployment scenarios is analysed. The study also discusses possible directions for further investigation, focusing on the requirement for effective and expandable PQC systems that can satisfy changing cybersecurity requirements. In order to protect sensitive data in the digital era, this study emphasizes the need for implementing quantum-secure systems by fusing theoretical understandings with real-world applications.
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.
Alongside the growth of technology is the increasing demand for security of data and communication channels. As attacking power grows, devices become smaller and data expands, the security needs to be stronger yet less resource-consuming than ever before. Public key cryptography (PKC) is used in the majority of today's communications systems. The security of public-key cryptographic schemes, such as RSA and elliptic curve cryptography (ECC), is based on underlying mathematical problems such as factoring large integers or solving the discrete log problem. However, the discovery of Shor's Algorithm in 1994 insinuates that these schemes will be insecure when a full-scale quantum computer is developed, as these problems will be solvable in polynomial time. Therefore attention has moved towards post-quantum, or quantum-safe, cryptography (QSC). In 2016, the National Institute of Standards and Technology (NIST) announced the beginning of their efforts to migrate to QSC, a standardisation process which has involved the cryptographic community worldwide. There are five main types of QSC being considered for standardisation; lattice-based, code-based, multivariate-based, hash-based and isogeny-based. Lattice-based cryptography (LBC) offers a promising alternative to today's classical approaches. Hard problems based on lattices are believed to be unsolvable, even by a quantum-computer, in a feasible amount of time. In 1995, Ajtai showed that the average case complexity of these problems is at least as hard as solving the problems in the worst case. Furthermore, lattice-based schemes are the only remaining contender in the NIST process to provide the important primitives of encryption, key encapsulation and digital signature schemes (DSSs). A well-recognised open problem surrounding quantum-safe cryptography is its increase in bandwidth and computational complexity in comparison to existing cryptography. However, in comparison to other quantum-safe schemes, LBC has been shown to be relatively efficient. In this thesis, novel software designs of lattice-based schemes are presented and shown to be competitive with existing PKC. Additionally, physical attacks are considered and countermeasures are incorporated into the designs. DSSs are required for authentication, integrity and non-repudiation of data. This thesis provides an evaluation of three leading signature schemes, BLISS-B, Dilithium and \textsc{Falcon}, which vary in terms of their key features, such as the sampling processes used, and the structure of the lattices. Physical attacks on the three schemes are considered and the effect on performance of appropriate attack countermeasures is evaluated. A novel fault attack on the NIST candidate \textsc{Falcon} is also proposed. A further advantage of LBC is the ability to support cryptographic primitives with extended capabilities to facilitate certificate management and compute on encrypted data. The complexity of today's technology advances mean applications require more sophisticated primitives, which contrastingly are required to run on even smaller platforms. This thesis presents novel quantum-safe advanced cryptographic schemes, specifically lattice-based identity-based encryption (IBE) and hierarchical identity-based encryption (HIBE). IBE removes the need for certificate management, as a user's public key depends on their public identity. IBE is currently used in vital applications such as emergency services communication and so the development of a high-performance quantum-safe alternative is imperative. This thesis also introduces the first scalable HIBE scheme based on lattices. The first HIBE scheme based on structured lattices, Latte, was proposed by the National Centre for Cyber Security (NCSC) in 2017. However, the public key and ciphertext sizes increased with each delegation and hence it was not feasible to scale the algorithm. Skinny Latte, proposed in this thesis, remedies this issue by fixing the dimension of the lattice, thereby making public key and ciphertext sizes constant. This research also shows that it is practical for real-world deployment. Overall, this thesis demonstrates that lattice-based cryptography is practical for real-world applications. It considers both theoretical and physical attacks, and presents novel designs of advanced quantum-safe cryptographic primitives, which have only yet been realised by lattices.
Classical cryptography has been around for a long time in the documented human history, but most classical ciphers were broken and even solved by hand. Shannon introduced the notion of perfect secrecy that formally defines confidentiality in the information-theoretic sense, which is only possible in the restricted scenarios where the message is no longer than the encryption key. The invention of public-key cryptography (the Diffie-Hellman key exchange protocol in 1976 and the RSA crypto-system in 1977) marks the birth of modern cryptography, allowing parties to exchange messages securely without sharing any secrets in advance. Furthermore, it provides computational security based on the conjectured hardness of mathematical problems such as factorization and the discrete logarithm. Public-key cryptography has found numerous applications in the Internet, financial and banking industry, and blockchains, and it plays a crucial role in protecting information security and asset safety. Unfortunately, in the 1990s, Shor proposed efficient quantum algorithms that solve number-theoretic problems, including factorization and discrete logarithms in polynomial time. Once a quantum computer of a particular scale becomes a reality, it will cause a devastating blow to the existing public-key infrastructure. To deal with such a ‘quantum crisis’, academia and industry are looking into the design, analysis and standardization of cryptographic algorithms that can resist quantum computers referred to as post-quantum cryptography (PQC). The National Institute of Standards and Technology (NIST) has been soliciting proposals for the post-quantum public-key algorithms since 2016. More recently, the Chinese Association for Cryptologic Research (CACR) held a competition on designing cryptographic algorithms whose public-key cryptography track focused on post-quantum cryptographic algorithms. Lattice-based cryptography is considered by most to be the mainstream technical route of post-quantum cryptography, which is reflected in the number of proposals (and their percentage of the total) received in the NIST PQC process. To reflect the status quo of post-quantum cryptography, we invite leading experts in this area to contribute three technical perspectives that aim to help readers understand the algorithms, the underlying basic techniques and different technical routes to achieve quantum resistance. The first perspective, presented by Lu and Zhang, introduces public-key cryptographic algorithms whose quantum security is reducible from the conjectured quantum hardness of lattice problems. In particular, they mainly focus on public-key encryption (PKE) and the key encapsulation mechanism (KEM), which are essential building blocks for securing the confidentiality of communication without pre-shared secrets. Both types of crypto-systems are solicited by the NIST PQC standardization and the CACR algorithm design competition. This perspective gives a comprehensive survey on practical lattice-based PKEs/KEMs, and their best-known quantum and classical attacks. Another important post-quantum crypto-system is digital signature, which ensures that three goals of information security are met other than confidentiality, namely, integrity, authentication and non-repudiation. The second perspective is on lattice-based signature by Lyubashevsky. In this perspective, he surveys different techniques in building lattice-based post-quantum crypto-systems, discusses the challenges in overcoming performance issues and gives us state-of-the-art digital signature schemes. In addition to ensuring the ‘static’ security of information in storage and transmission, advanced cryptographic algorithms and protocols can guarantee information security during the computation process (possibly among multiple parties), referred to as privacy-preserving computation. Cryptographic techniques involved in privacy-preserving computation include secure multi-party computation, zero-knowledge proof and fully homomorphic encryption. There is a pressing need to migrate them to the post-quantum era. The third perspective, by Yu and Xie, presents practical instantiations of these algorithms and discusses possible ways to migrate them to their quantum-resistant counterparts. To summarize, post-quantum cryptography has received widespread attention and made significant progress in recent years. Some post-quantum cryptographic algorithms, such as the lattice-based candidate, also have other advantages (e.g., computational efficiency and full homomorphism) over their classical counterparts. Lattice-based cryptography is an emerging field with high theoretical value and wide application, and we encourage young researchers to enter and explore this new and exciting field.
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.
Basic security requirements such as confidentiality, user authentication and data integrity, are assured by using public-key cryptography (PKC). In particular, public-key signature schemes provide non-repudiation, integrity of transmitted messages and authentication. The presence of a large scale quantum computer would be a real threat to break the most widely used public-key cryptographic algorithms in practice, RSA, DSA, ECDSA signature schemes and Diffie-Hellman key exchange. Thus, all security protocols and applications where these public-key cryptographic algorithms are used are vulnerable to quantum-computer attacks. There are five directions of cryptographic primitives secure against a quantum computer: multivariate quadratic equation-based, hash-based, lattice-based, code-based and supersingular isogeny-based cryptography. These primitives could serve as replacements for current public-key cryptographic algorithms to prepare for post-quantum era. It is important to prioritize the fields to be replaced by post-quantum cryptography (PQC) since it is hard to replace the currently deployed PKC with PQC at the same time. The fields directly connected to human life such as vehicular communications should be the primary targets of PQC applications. This survey is dedicated to providing guidelines for adapting the most suitable post-quantum candidates to the requirements of various devices and suggesting efficient and physically secure implementations that can be built into existing embedded applications as easily as traditional PKC. It focuses on the five types of post-quantum signature schemes and investigates their theoretical backgrounds, structures, state-of-the-art constructions and implementation aspects on various platforms raging from resource constrained IoT devices to powerful servers connected to the devices for secure communications in post-quantum era. It offers appropriate solutions to find tradeoffs between key sizes, signature lengths, performance, and security for practical applications.