Lattice-Based Digital Signature Schemes And Their Applications

Diffie-Hellman first introduced the concept of digital signature in1976. As an alterna-tive to handwritten signatures, it satisfies verifiability, non-repudiation and integrity. After decades of development, it has become an important branch of cryptography and corner-stone for many e-commerce and e-government applications. However, with the increasing needs of applications, some specific scenarios require signatures with additional features. We choose some types of signatures with additional features as our research objects, such as blind signatures, group signature, linearly homomorphic signature, algebra signature. On the other hand, security of the most of existing signatures are based on traditional hard problems, such as DLP, IFP. Shor shows that these problems are unsafe under a quantum computer. Lattice-based cryptography(LBC) can quantum attacks effectively. Hence, we construct signature schemes based on lattice assumptions. Achievements of this paper are list as follows:We do an in-depth research on HIBBS. Firstly, a generic construction and security model of HIBBS are defined. Then we present a framework of how to convert a regular signature into a blind one. According to the framework, we implement a concrete blind technique called Matrix-Vector-Blind (MVB). By using MVB, we propose two HIBBS, which are security in ROM and SM respectively. Security proofs of the new schemes are based on the SIS assumption. Compared with previous schemes, the new schemes only need a round of data exchange between user and signer. Furthermore, a smaller key size and shorter signature are achieved in the new schemes. Due to the inherent advantages of LBC, computational overhead of the new schemes are lower than previous schemes.We propose a new lattice-based group signature scheme. The only one lattice-based group signature(GKV10) was proposed by Gordon et al. in ASIACRYPTO10’. However, there are two shortcomings in GKV10:(1) Group members need be fixed in the setup phase. To enroll a new group member, all of the keys need to be updated;(2) Key size of GKV10is linear with the group size, and private key for each member is a matrix. Targeted above problems, a new scheme is proposed in this paper. Compared with GKV10, the new scheme with a much smaller key size, which is independent with group size. Private key for each signer is a vector. a new party called "issuer" is introduced in the new scheme. By interacting with the issuer, any user can be added to the group dynamically. We propose a secure lattice-base network coding scheme from a homomorphic sig-nature scheme. Firstly, we improve Boneh et al.’s linearly homomorphic lattice-based sig-natures by following ways:(1) By adopting the technic of "Basis Delegation in Fixed Di-mension", we reduce the dimension of lattice used in original scheme, and it leads to a half-length signature and better computational efficiency.(2) We extend the coefficients of the authentication vectors to field of Fp, and it makes the improved signatures much more flexible and a wilder applying.(3) Although security of the new signatures is also based on k-SIS, we achieve a tight reduction by optimizing the proof. With the improved homomor-phic signature scheme, we propose a secure lattice-base network coding scheme to prevent pollution attacks. Finally, we analysis the security and efficiency of our new scheme, and it shows that our scheme is better than existing schemes both in security and efficiency.We attack some existing identity-base signature schemes. We construct three attack al-gorithms to attack schemes of Li-Jiang and Gu-Jia-Jiang. With these algorithms, an attacker can forge a valid signature on any message on behalf of any user in polynomial time only by choosing random parameters without knowing the signing key of the user. We also construct three attack algorithms to attack scheme of Yu-Zheng. With these algorithms, an attacker can forge valid both regular signature on behalf of the original signer and proxy signature of any proxy signer on any message without knowing the signing key of these signers. Finally, we analyze the root cause of attacks and gave some suggestions for modifications.we propose an algebraic signatures based PDP from ideal lattice assumptions(L-AS-PDP). Provable data possession in the cloud storage protocol is currently a hot research topic. we propose the first algebraic signatures based provable data possession protocol from ideal lattice assumptions. We prove that L-AS-PDP guarantees data possession in standard model if Shortest Polynomial Problem(SPP) is hard. We analysis the proposed scheme theoretically, and compare it with similar schemes. Experimental result shows that the time cost of preprocessing and verifying of L-AS-PDP is about14%to17%compared with that of E-PDP, which is with the highest efficiency in previous schemes. The time cost of the server is about5times lower than that of E-PDP.