## Browse

Efficient Fully Homomorphic Encryption over the Integers
효율적인 정수 기반 동형 암호

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors
김진수
천정희
Major
자연과학대학 수리과학부
Issue Date
2015-02
Publisher
서울대학교 대학원
Keywords
fully homomorphic encryptionsomewhat homomorphic encryptionhybrid schemeapproximate GCD problem
Description
학위논문 (박사)-- 서울대학교 대학원 : 수리과학부, 2015. 2. 천정희.
Abstract
Fully homomorphic encryption allows a worker to perform additions and multiplications on encrypted plaintext values without decryption. The first construction of a fully homomorphic scheme (FHE) based on ideal lattices was described by Gentry in 2009. Since Gentry's breakthrough result, many improvements have been made, introducing new variants, improving efficiency, and providing new features.

The most FHE schemes still have very large ciphertexts (millions of bits for a single ciphertext). This presents a considerable bottleneck in practical deployments.
To improve the efficiency of FHE schemes, especially ciphertext size, we can consider the following two observations. One is to improve the ratio of plaintext and ciphertext by packing many messages in one ciphertext and the other is to reduce the size of FHE-ciphertext by combining FHE with existing public-key encryption.

In the dissertation, we study on construction of efficient FHE over the integers.
First, we propose a new variant DGHV fully homomorphic encryption to extend message space. Using Chinese remainder theorem, our scheme reduces the overheads (ratio of ciphertext computation and plaintext computation) from $\tilde{O}(\lambda^4)$ to $\tilde{O}(\lambda)$. We reduce the security of our Somewhat Homomorphic Encryption scheme to a decisional version of Approximate GCD problem (DACD).

To reduce the ciphertext size, we propose a hybrid scheme that combines public key encryption (PKE) and somewhat homomorphic encryption (SHE). In this model, messages are encrypted with a PKE and computations on encrypted data are carried out using SHE or FHE after homomorphic decryption. Our approach is suitable for cloud computing environments since it has small bandwidth, low storage requirement, and supports efficient computing on encrypted data.

We also give alternative approach to reduce the FHE ciphertext size.
Some of recent SHE schemes possess two properties, the public key compression and the key switching. By combining them, we propose a hybrid encryption scheme in which a block of messages is encrypted by symmetric version of the SHE and its secret key is encrypted by the (asymmetric) SHE. The ciphertext under the symmetric key encryption is compressed by using the public key compression technique and we convert the ciphertext into asymmetric encryption to enable homomorphic computations using key switching technique.
Language
English
URI
https://hdl.handle.net/10371/121292
Files in This Item:
Appears in Collections:
College of Natural Sciences (자연과학대학)Dept. of Mathematical Sciences (수리과학부)Theses (Ph.D. / Sc.D._수리과학부)