Provably Secure Signature Scheme From Lattices

Modern Cryptography is based on mathematics tools, and lattice is an attractive choice. Lattice-based research has achieved a lot in the literature recently. It has been applied in variety of areas, including public-key crypto system, signature,IBE-based en-cryption, ABE-based encryption, as well as homomorphic encryption and fully Homo-morphic encryption.The origin of lattice-based cryptography is quantum computer, on which the security of the most of encryption schemes that based on the traditional difficult problems, such as large integer factoring problem (LIFP), discrete logarithm problem (DLP) and elliptic curve discrete logarithm problem (ECDLP), cannot be ensured. Since one single quantum can be in types of states instead of two just as bit has, the quantum computation model can solve the exponential problem in polynomial time.There are many reasons for Lattice-based cryptographic schemes’s attraction. First, theoretically, lattice cryptography is supported by strong worst-case security guarantees, which is stronger than average-case assumptions based on number theory. Furthermore, lattice cryptography can successfully against quantum attack under some appropriate hard problem assumptions. Moreover, part of the reduction inside belongs to quantum reduc-tion, which make lattice-based cryptography can resist quantum attack with some hard problem assumptions. Second, in practical, the most fundamental operation of lattice cryptography is just a modular integer matrix-vector multiplication. Furthermore, the modular is a small prime in general. Therefore, all the basic operations can be performed without the need of a "big-num" library for arbitrary precision arithmetic. Besides, Due to the feature of Lattice, it can be parallelized easily. In fact, lattice reduction and sampling have already been implemented on parallel platforms.We mainly focus on the lattice-based signature. In this work, we designed two kinds of signature schemes, then proved the security of them both in random oracle model and standard oracle model with variety of adversary advantages.First, just like the point of syndrome sharing, we employed lattice basis delegation technique to implement threshold signature, which is proved to be non-adaptive existen-tial unforgeable in the random oracles. Specifically, we used the lattice basis delegation algorithm. The responsibility is assigned to couples of parties. The threshold scheme is implemented by sharing the message to be signed with Shamir’s secret sharing algorithm. Moreover, this algorithm will not increase the dimension, so the signature sharing can be merged easily.Second, we consider another signature model. Differ to the former one, in this model the message is hashed to random lattice matrix rather than syndrome. By setting the syndrome be a random vector or zero vector, the signature can be obtained by sampling algorithm. The random oracle is avoided by admissible hash function. And the non-adaptive existential unforgeable feature is proved in the random oracles.Our contributions are mainly including;· The scheme is constructed by lattice. It is naturally resist quantum attack.· The threshold signature is implemented by combining message sharing with lattice delegation algorithm.· The admissile hash function is applied in our scheme to avoid random oracle.However, there are several weaknesses in this work. For instance, the trusted third party is not eliminated in the threshold signature scheme. Currently, the adversary view can’t be simulated without the trusted third party. Besides, the admissible hash function squared the dimension of public-key, so in some extent it’s impractical. This is caused by the struct of admissible hash function, the admissibility is got by increasing lattice’s dimension.