Research On Lattice-Based Cryptosystems And The Basic Modules

Those cryptographic schemes whose security are based on the hardness offactorizing large integers or solving the discrete logarithms will be faced with greatthreat once the quantum computers are invented. It is a real demand to designschemes that can resist quantum attacks. Constructions from lattices can be one of thealternatives. Besides the resistance so far to cryptanalysis by quantum algorithms,lattice-based cryptosystems enjoy asymptotic efficiency, conceptual simplicity(usually requiring only linear operations on small integers) and worst-case security.We focus in this thesis on the discrete Gaussian distribution, the construction ofproxy signature and ID-based threshold ring signature schemes from lattices. DiscreteGaussian distributions are building blocks in the lattice-based cryptosystems. Threeapproximate implementations are provided, with one million simulations for each.Comparison is made from these simulations. As for proxy signatures, we found someflaws in the existing schemes and make an improvement in our own scheme whoseformal security is provided in the standard model. To construct an ID-based thresholdring signature scheme out of lattices, we employ the multlinear maps over the gradedencoding systems that are designed from ideal lattices. The original GCDHP problemis not suitable for our formal security proof. Instead, we propose a new problemvGCDHP that is proved to be an equivalent form of the GCDHP problem.Furthermore, we introduce the more general problem gGCDHP on which our securityis based directly.