Design And Analysis Of Special Lattice-based Encryption Scheme

With the advent of Shor's algorithm and Grover's algorithm,there have been a substan-tial amount of researches on quantum computing.Those public-key cryptosystems rely on classical number-theoretic problems,such as factoring or solving discrete logarithm,are no longer secure in the quantum setting.Cryptographers are seeking more secure public-key cryptosystems that can resist quantum computing attacks.As a typical representative of post-quantum cryptography,lattice-based cryptography enjoys apparent resistance to quan-tum attacks,very strong security proof based on worst-case hardness,and high asymptotic efficiency and parallelism.Moreover,lattice-based cryptography can be used to construct versatile and powerful cryptographic objects.For example,fully homomorphic encryption(FHE)which allows an untrusted third party to perform arbitrary computation on encrypted data,without learning anything about that data,and attribute-based encryption(ABE)that supports fine-grained access controlAlthough the researches on FHE and ABE have made a breakthrough in recent years,there are still many problems remain unsolved,such as large public/secret key size or ciphertext size,and low algorithm efficiency,which demand for further improvements.In this disserta-tion,these two special lattice-based encryption cases are analyzed and explored thoroughly,and the main results obtained are as follows.1.Two efficient Bootstrapping algorithms with large message space are presented.Boot-strapping,which demands the decryption circuit to be homomorphically evaluated,is not only the bottleneck in the efficiency of FHE,but also limits the size of the message space that the FHE scheme can handle.The message space is limited to the binary space,or the space for a small constant prime.It is less efficient to homomorphically evaluate the arith-metic circuits.To address this problem,this dissertation presents two efficient Bootstrapping algorithms of fully homomorphic encryption with large message space ZQ.(a)Bootstrapping algorithm 1:for the Bootstrapping algorithm presented in DGHV,an FHE scheme with binary message spaces Z2,we first use mod-Q arithmetic circuit to simulate the bit operations in its decryption.To reduce the number of simulating the bit XOR operations(which will take mod-Q multiplier gates),we use Lagrange interpolating polynomial to obtain the hamming wight of some vectors in bits,and then play the three-for-two trick over ZQ for the result.Finally the decryption circuit can be expressed as a polynomial of multiplication degree 108·?log3 ?,and the number of the multiplications in the decryption circuit is O(?log?),where ?=?/log?,? is the security parameter and Q>?.(b)Bootstrapping algorithm 2:The multiplier factor of the multiplicative degree of de-cryption circuit in algorithm 1 is too big,since 108 is relative larger than ?.In or-der to remove this big multiplier factor,we use depth-3 arithmetic circuit instead of three-for-two trick.Then,the multiplication degree of decryption circuit is reduced to(?2log2?)/2,and the number of the multiplications in the decryption circuit is O(?log2 ?),Where ?=?/?log and Q>?log2?/2.Here we emphasize that the complexity of decryption circuit is independent of the message space size Q as long as Q is large enough.Furthermore,an FHE over the integers with Boot-strapping for large prime message space is presented,called CLTQ.Compares to the FHE scheme over the integers with binary message space CLT2,CLTQ is hundreds or thousands of times faster in homomorphically evaluating the mod-Q arithmetic circuit,the factor is about 17?logQ/log.2.Three variants of ABE scheme GVW13 is proposed,and all these three variants can be broken by collusion.GVW13 scheme is the first ABE scheme for arbitrary polynomial arithmetic circuit.Its secret key is a series of the recoding keys in the two-to-one recoding algorithm.The secret key size is huge.We modify the recoding key matrices to reduce the storage space.If the recoding key matrix has certain features(e.g.matrix multiplication commutativity),the variants of GVW13 are vulnerable to collusion attacks by certain types of users.Specifically,the user,who has a circuit C,can not decrypt the ciphertext c labeled with attribute vector att,but can decrypt the ciphertext c*labeled with attribute vector att*,where attribute att*is the same as attribute att except the i-th scalar.If the connection between the i-th input and the final output of C is provided only on the right side of the gate,then this kind of users can collude to attack the variants of GVW13 scheme and recover the plaintext of the ciphertext c labeled with attribute att.