The Rényi divergence is a measure of closeness of two probabilitydistributions. We show that it can often be used as an alternativeto the statistical distance in security proofs for lattice-based cryptography.Using the Rényi divergence is particularly suited for security proofsof primitives in which the attacker is required to solve a search problem(e.g., forging a signature).We show that it may also be used in the case ofdistinguishing problems (e.g., semantic security of encryption schemes),when they enjoy a public sampleability property. The techniques lead tosecurity proofs for schemes with smaller parameters, and sometimes tosimpler security proofs than the existing ones.
The Rényi divergence is a measure of closeness of two probabilitydistributions. We show that it can often be used as an alternativeto the statistical distance in security proofs for lattice-based cryptography.Using the Rényi divergence is particularly suited for security proofsof primitives in which the attacker is required to solve a search problem(e.g., forging a signature).We show that it may also be used in the case ofdistinguishing problems (e.g., semantic security of encryption schemes),when they enjoy a public sampleability property. The techniques lead tosecurity proofs for schemes with smaller parameters, and sometimes tosimpler security proofs than the existing ones.
Threshold encryption schemes provide a common tool to secure a public-key encryption scheme against single point of failure attacks. Despite the success of lattices in building fully-homomorphic and presumably quantum-resistant encryption schemes, the task of thresholdizing those schemes remains challenging. The major bottleneck in the standard approach is the use of statistical noise flooding, leading to a significant efficiency loss and the need of stronger hardness assumptions. Recent works have replaced the heavy statistical noise flooding by a lighter one using the Rényi divergence. The new Rényi noise flooding both improves the efficiency and allows to use weaker hardness assumptions. However, arguing semantic security of lattice-based threshold schemes in the presence of Rényi noise flooding showed to be challenging. Chowdhury et al. (IACR ePrint'22) argued in the fully-homomorphic case that the Rényi divergence directly applies for semantic security by making use of an existing framework called public sampleability. In this work, we argue that their public sampleability framework was neither sufficient nor correctly used. To address both issues, we strengthen the framework and thoroughly apply it to prove semantic security of generic lattice-based threshold encryption constructions. We distinguish between the plain public-key and the fully-homomorphic settings, as different security notions are achieved. As a byproduct, this shows that the proof detour via one-way security made by Boudgoust and Scholl (Asiacrypt'23) was superfluous, now leading to tighter proofs in the standard model.
One essential quest in cryptography is the search for hard instances of a given computational problem that is known to be hard in the worst-case. In lattice cryptography we are in the unique situation that we have found a way of picking random instances which are at least as hard as well-studied lattice problems in the worst-case. At the same time, no attack running in subexponential time is known to break these problems, even for an adversary using quantum computers. Virtually all public-key schemes in use today are subject to such attacks, and the development of quantum computers is actively pursued, so it is prudent to investigate lattice-based alternatives. There are two fundamental open problems in lattice cryptography today and this thesis contributes to solving them. First, there exists a widely used efficiency improvement that allows for trapdoors whose asymptotic keysize and evaluation time are both quasilinear in the dimension of an associated lattice. This is accomplished by restricting oneself to lattices with special structure, so-called ideal lattices. This entails the use of newer security assumptions, but these have not been analyzed thoroughly so far. We start this work by comparing the class of ideal lattice problems with its general counterpart in terms of size. Affirming folklore, we find the number of restricted instances among all instances to be asymptotically negligible for those classes of lattices suggested for practical use. The second open problem is that while the connection to worst-case problems is well understood, the practical hardness of the related average-case problems is not. Specifically, there have been parameters suggested for practical usage, where current lattice basis reduction algorithms can solve these worst-case problems, but the related average-case problems, which these are reduced to and which represent the basis of practical security of the cryptosystems, are completely infeasible. In most cases, this lack of understanding has lead either to a very conservative choice of parameters, or none at all. This in turn makes it impossible for the resulting lattice schemes to compete with their counterparts based on other paradigms. We further the understanding of this practical security and at the same time improve the efficiency of several common related cryptographic schemes. Among other things, we find that for the SWIFFT compression function, solving certain problems closely related to finding collisions is easier than previously thought and we suggest efficient replacement parameters. We propose a novel zero-knowledge identification scheme that, to our knowledge, beats all competing post-quantum schemes, even those based on other paradigms. Possibly most important, we help to tighten the efficiency gap between lattice encryption schemes that are provably secure and the acclaimed ad-hoc encryption scheme NTRU. This is done by unifying many recent developments into a new provably secure design and providing a comprehensive analysis of practical security, which together results in a great leap of efficiency.
Rejection sampling technology is a core tool in the design of lattice-based signatures with ‘Fiat–Shamir with Aborts’ structure, and it is related to signing efficiency and signature, size as well as security. In the rejection sampling theorem proposed by Lyubashevsky, the masking vector of rejection sampling is chosen from discrete Gaussian distribution. However, in practical designs, the masking vector is more likely to be chosen from bounded uniform distribution due to better efficiency and simpler implementation. Besides, as one of the third-round candidate signatures in the NIST postquantum cryptography standardization process, the 3rd round version of CRYSTALS-Dilithium has proposed a new method to decrease the rejection probability in order to achieve better efficiency and smaller signature size by decreasing the number of nonzero coefficients of the challenge polynomial according to the security levels. However, it is seen that small entropies in this new method may lead to higher risk of forgery attack compared with former schemes proposed in its 2nd version. Thus, in this paper, we first analyze the complexity of forgery attack for small entropies and then introduce a new method to decrease the rejection probability without loss of security including the security against forgery attack. This method is achieved by introducing a new rejection sampling theorem with tighter bound by utilizing Rényi divergence where masking vector follows uniform distribution. By observing large gaps between the security claim and actual security bound in CRYSTALS-Dilithium, we propose two series of adapted parameters for CRYSTALS-Dilithium. The first set can improve the efficiency of the signing process in CRYSTALS-Dilithium by factors of 61.7 % and 41.7 % , according to the security levels, and ensure the security against known attacks, including forgery attack. And, the second set can reduce the signature size by a factor of 14.09 % with small improvements in efficiency at the same security level.
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. In 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. First, 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. In 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. In 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.