Design Of Private Data Ranking Protocols And Reaction Attacks Against Fully Homomorphic Encryption

With the rapid development of cloud computing, the research of fully homomorphic encryption (FHE) quickly gains a lot of attention in cryptography community. FHE allows one to compute arbitrary functions over encrypted data without the decryption key, it can provide key theory and technology for ciphertexts processing and has a broad application prospect, but now it suffers series problems as inefficiency, complicacy in private data retrieval and security issues.In this dissertation, we aim at the design of private data ranking protocols and the study of reaction attack against FHE schemes. The main results list as follows:1. Private data ranking (PDR) protocols based on FHE are proposed. PDR can be immediately used in private data matching, which is the core step of private data retrieval. According to fact that FHE scheme concurrently has additive and multiple homomorphism, we realize the function of private data ranking through addition with carry in ciphertext domain. The number of ciphertext blocks exchanged in the protocol decreases obviously, compared to the former ones based on partial homomorphic encryption.2. An improved reaction attack against FHE schemes based on the hardness assumption of sparse subset sum problem is presented. Since the public key of such scheme contains the ciphertext of private key (a sparse0-1vector), the adversary is able to locate the "1"s in the private key by taking some operations for the ciphertext, and obtain the user’s private key in shorter time through access to the decryption oracle. The advantage of this attack is the full use of precomputation, which improves the attack’s efficiency.3. The feasibility of reaction attack to recover the private key of FHE schemes based on the hardness assumption of learning with errors (LWE) problem is studied. Making use of LWE to design FHE schemes is one focus of current research, but the large number of quasi-linear operations in these schemes may lead to the leakage of private key when suffering chosen ciphertext attack (CCA). Under the condition of access to the decryption oracle, we use the method of noise eliminating through dichotomy approximation in ciphertext domain and solving linear congruence equations set, and validate the availability of recovering the multi-dimensional private key by experiment.