Research On Cryptographic Schemes Based On Lattice And Compressed Sensing

Cryptography, which is the art and science of transmitting information efficiently and securely, plays an important role in the field of information security and cyberspace security. The traditional cryptographic schemes based on some classical number theory problems will be confronted with serious threats because of the rapid development of quantum computing technology.As a typical representative of post quantum cryptography, lattice-based cryptography has received wide attention from domestic and foreign scholars in recent years. As an important part of cryptography, digital signature technology can meet the requirements of authentication, data integrity and non-repudiation in a network environment. Most of lattice-based. signature schemes are based on Small Integer Solution (SIS) problem or inhomogeneous small integer solution problem. From a linear algebra point of view, these two problems can be regarded as solving integer vector solutions with small norms of underdetermined linear equations. If we extend the problem of solving the underdetermined linear system in a discrete space to the problem in the real or complex field, it is very similar to the model of compressed sensing. The theory of compressed sensing, which implies the natural encryption process and does not need any additional steps of random coding, has been widely used in some cryptographic schemes, such as image encryption, identity authentication and secret sharing.Based on the basic theories of lattice and compressed sensing, this paper embarks from the underlying different types of underdetermined linear systems, and proposes several cryptographic schemes. The aim of this paper is to build a foundation for combining the common advantages of lattice theory and compressed sensing. From the perspective of security and efficiency, this paper introduces three lattice-based signature schemes in the standard model, including a short signature scheme with constant size public keys, a linear homomorphic signature scheme and a leveled fully homomorphic signature scheme. In addition, based on the properties of compression and encryption in compressed sensing, this paper presents a secret image sharing scheme and a cryptanalysis of coupled map lattice system. The main research results and innovations of this paper are described as follows:(1) We propose a lattice-based signature scheme with short signatures and constant-size public keys in the standard model. Each signature in this scheme contains a low-dimensional lattice vector, and the public key only contains three matrices plus a vector. To prove its security, we introduce a new hard lattice problem, called Variant Small Integer Solution (Variant SIS),and give the security reduction from SIS to Variant SIS. Then we define a family of hash functions based on the hardness of Variant_SIS and prove its two security properties, including one-wayness and collision-resistance.Compared to previous lattice-based constructions, the computational complexity and the communication overhead of our scheme are very low.(2) We present an efficient linearly homomorphic signature scheme based on lattice theory in the standard model, and this scheme can be used to provide security guarantee for multi-source network coding environment. To prove its security, we introduce a new sampling algorithm ProductSamp,which can generate a random lattice and its corresponding short trapdoor basis. We have shown the existential unforgeability of this scheme under chosen file attacks. The proposed linearly homomorphic signature scheme has many advantages, such as supporting multi-source network coding, low computational complexity and low communication overhead.(3) We propose a leveled fully homomorphic signature scheme in the standard model based on homomorphic chameleon hash function. We first present the definition of homomorphic chameleon hash function and give a specific method for constructing it. And then based on the collision-resistance property of this function, we introduce a leveled fully homomorphic signature scheme which can support any polynomial depth circuit. In our scheme, the size of evaluated homomorphic signatures grows polynomially in the depth of the circuit.(4) We present a scalable (k, n) secret image sharing scheme based on compressed sensing. The scalability means that the amount of information in the reconstructed image scales in proportion to the number of the participants.Natural images can be represented using only a few non-zero coefficients under a suitable basis or dictionary, and our scheme makes full use of this characteristic to reduce the size of the shadows. Our scheme has the property of flexibility, which means that the dealer can achieve a compromise between the size of each shadow and the quality of the reconstructed image according to different applications. In addition, our scheme has smooth scalability and noise-resilient capability. The comparison with similar works and the experimental results demonstrate the feasibility and superiority of our scheme.(5) We propose a cryptanalysis of chaotic coupled map lattice system based on compressed sensing. Coupled map lattices are often used to construct cryptographic schemes such as image encryption and hash function,and some parameters of these systems often play a key role in the above-mentioned cryptographic schemes. Specifically, we first transform the parameter analysis problem of coupled map lattice into the sparse recovery problem of underdetermined linear system. Then from a theoretical point of view, we have shown that the coefficient matrix generated by the system of coupled map lattice satisfies the restricted isometry property when the weighted matrix is sparse. Thus the number of observations required for perfect reconstruction is far less than the number of lattice elements in the coupled map lattice. The simulations mainly show the effects of the sparsity,the number of observations and the coupling parameter on the recovery rate.Another important and significant advantage is that, if the observed data are contaminated with some types of noises, our proposed approach is still effective.