In this thesis we give an analysis of the hierarchical identity-based broadcast encryption scheme proposed by C. Yang, Zheng, Wang, Lu and Y. Yang. The interest in this scheme is due to the fact that it is one of the few of its kind to be Post-Quantum, and relies on the hardness of the LWE, i.e. on lattice-based problems. For the first time we give a detailed description of the scheme and we present a full introduction to the mathematical and cryptographic background needed to describe it. The main result of the thesis is the construction of an adaptor signature for CSI-FiSh that we called ORCAS. Cryptographic group actions are a promising technique that underlie several Post-Quantum digital signatures, including CSI-FiSh. Our proposal, ORCAS, which stands for One-Round "Cheating" Adaptor Signatures (so named because its pre-signing algorithm resembles how cheating signer might try to forge a Fiat-Shamir-based signature), is directly compatible with CSI-FiSh. While the signatures are produced in a different manner and follow a slightly different distribution, they can still be verified by a blockchain which supports only CSI-FiSh.
In this thesis we give an analysis of the hierarchical identity-based broadcast encryption scheme proposed by C. Yang, Zheng, Wang, Lu and Y. Yang. The interest in this scheme is due to the fact that it is one of the few of its kind to be Post-Quantum, and relies on the hardness of the LWE, i.e. on lattice-based problems. For the first time we give a detailed description of the scheme and we present a full introduction to the mathematical and cryptographic background needed to describe it. The main result of the thesis is the construction of an adaptor signature for CSI-FiSh that we called ORCAS. Cryptographic group actions are a promising technique that underlie several Post-Quantum digital signatures, including CSI-FiSh. Our proposal, ORCAS, which stands for One-Round "Cheating" Adaptor Signatures (so named because its pre-signing algorithm resembles how cheating signer might try to forge a Fiat-Shamir-based signature), is directly compatible with CSI-FiSh. While the signatures are produced in a different manner and follow a slightly different distribution, they can still be verified by a blockchain which supports only CSI-FiSh.
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.
Digital signatures and encryption schemes constitute arguably an integral part of cryptographic schemes with the goal to meet the security needs of present and future private and business applications. However, almost all public key cryptosystems applied in practice are put at risk due to its vulnerability to quantum attacks as a result of Shor's quantum algorithm. The magnitude of economic and social impact is tremendous inherently asking for alternatives replacing classical schemes in case large-scale quantum computers are built. Lattice-based cryptography emerged as a powerful candidate attracting lots of attention not only due to its conjectured resistance against quantum attacks, but also because of its unique security guarantee to provide worst-case hardness of average-case instances. Hence, the requirement of imposing further assumptions on the hardness of randomly chosen instances disappears, resulting in more efficient instantiations of cryptographic schemes. The best known lattice attack algorithms run in exponential time. \nIn this thesis we contribute to a smooth transition into a world with practically efficient lattice-based cryptographic schemes. This is indeed accomplished by designing new algorithms and cryptographic schemes as well as improving existing ones. Our contributions are threefold. \nFirst, we construct new encryption schemes that fully exploit the error term in LWE instances. To this end, we introduce a novel computational problem that we call Augmented LWE (A-LWE), differing from the original LWE problem only in the way the error term is produced. In fact, we embed arbitrary data into the error term without changing the target distributions. Following this, we prove that A-LWE instances are indistinguishable from LWE samples. This allows to build powerful encryption schemes on top of the A-LWE problem that are simple in its representations and efficient in practice while encrypting huge amounts of data realizing message expansion factors close to 1. This improves, to our knowledge, upon all existing encryption schemes. Due to the versatility of the error term, we further add various security features such as CCA and RCCA security or even plug lattice-based signatures into parts of the error term, thus providing an additional mechanism to authenticate encrypted data. Based on the methodology to embed arbitrary data into the error term while keeping the target distributions, we realize a novel CDT-like discrete Gaussian sampler that beats the best known samplers such as Knuth-Yao or the standard CDT sampler in terms of running time. At run time the table size amounting to 44 elements is constant for every discrete Gaussian parameter and the total space requirements are exactly as large as for the standard CDT sampler. Further results include a very efficient inversion algorithm for ring elements in special classes of cyclotomic rings. In fact, by use of the NTT it is possible to efficiently check for invertibility and deduce a representation of the corresponding unit group. Moreover, we generalize the LWE inversion algorithm for the trapdoor candidate of Micciancio and Peikert from power of two moduli to arbitrary composed integers using a different approach. \nIn the second part of this thesis, we present an efficient trapdoor construction for ideal lattices and an associated description of the GPV signature scheme. Furthermore, we improve the signing step using a different representation of the involved perturbation matrix leading to enhanced memory usage and running times. Subsequently, we introduce an advanced compression algorithm for GPV signatures, which previously suffered from huge signature sizes as a result of the construction or due to the requirement of the security proof. We circumvent this problem by introducing the notion of public and secret randomness for signatures. In particular, we generate the public portion of a signature from a short uniform random seed without violating the previous conditions. This concept is subsequently transferred to the multi-signer setting which increases the efficiency of the compression scheme in presence of multiple signers. Finally in this part, we propose the first lattice-based sequential aggregate signature scheme that enables a group of signers to sequentially generate an aggregate signature of reduced storage size such that the verifier is still able to check that each signer indeed signed a message. This approach is realized based on lattice-based trapdoor functions and has many application areas such as wireless sensor networks. \nIn the final part of this thesis, we extend the theoretical foundations of lattices and propose new representations of lattice problems by use of Cauchy integrals. Considering lattice points as simple poles of some complex functions allows to operate on lattice points via Cauchy integrals and its generalizations. For instance, we can deduce for the one-dimensional and two-dimensional case simple expressions for the number of lattice points inside a domain using trigonometric or elliptic functions.
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.
Abstract Lattice-based digital signature has become one of the widely recognized post-quantum algorithms because of its simple algebraic operation, rich mathematical foundation and worst-case security, and also an important tool for constructing cryptography. This survey explores lattice-based digital signatures, a promising post-quantum resistant alternative to traditional schemes relying on factoring or discrete logarithm problems, which face increasing risks from quantum computing. The study covers conventional paradigms like Hash-and-Sign and Fiat-Shamir, as well as specialized applications including group, ring, blind, and proxy signatures. It analyzes the versatility and security strengths of lattice-based schemes, providing practical insights. Each chapter summarizes advancements in schemes, identifying emerging trends. We also pinpoint future directions to deploy lattice-based digital signatures including quantum cryptography.
Quantum computers are moving closer to reality, and with that comes a serious concern for today's public-key cryptography. Many of the encryption and digital signature systems we rely on now, such as RSA and ECC, may no longer be secure in the future. Because of this, researchers are actively looking for new methods that can protect digital communication in the post-quantum era. One of the most promising directions is lattice-based cryptography. This paper gives a simple and focused review of lattice-based signature schemes. It brings together the main ideas from the existing literature and explains how these schemes are built, why they are considered secure, and what makes them practical. The review mainly discusses schemes based on hard lattice problems such as SIS and LWE. To make the comparison clearer, a table is also included that compares different signature schemes in terms of key size, signature size, security level, and computational efficiency. Overall, this study shows why lattice-based signature schemes are becoming an important part of modern cryptographic research and why they may play a major role in securing digital systems against future quantum threats.
Lattice-based cryptography is a branch of cryptography exploiting the presumed hardness of some well-known problems on lattices. Its main advantages are its simplicity, efficiency, and apparent security against quantum computers. The principle of the security proofs in lattice-based cryptography is to show that attacking a given scheme is at least as hard as solving a particular problem, as the Learning with Errors problem (LWE) or the Small Integer Solution problem (SIS). Then, by showing that those two problems are at least as hard to solve than a hard problem on lattices, presumed polynomial time intractable, we conclude that the constructed scheme is secure.In this thesis, we improve the foundation of the security proofs and build new cryptographic schemes. We study the hardness of the SIS and LWE problems, and of some of their variants on integer rings of cyclotomic fields and on modules on those rings. We show that there is a classical hardness proof for the LWE problem (Regev's prior reduction was quantum), and that the module variants of SIS and LWE are also hard to solve. We also give two new lattice-based group signature schemes, with security based on SIS and LWE. One is the first lattice-based group signature with logarithmic signature size in the number of users. And the other construction allows another functionality, verifier-local revocation. Finally, we improve the size of some parameters in the work on cryptographic multilinear maps of Garg, Gentry and Halevi in 2013.