Client-Aided Deep Neural Network on Fully Homomorphic Encryption without Bootstrapping and Attack Algorithm for a Keystore-based Key Generation

Abstract

n this dissertation, two main contributions are given as: i) Client-aided deep neural network on fully homomorphic encryption(FHE) without bootstrapping using commu- nication cost in the client-server model. ii) attack algorithm for a keystore-based secure key generation and management First, client-aided privacy-preserving machine learning on fully homomorphic en- cryption without bootstrapping is proposed. Bootstrapping which is the heaviest com- putation in homomorphic encryption consumes almost 70% of the total computation in homomorphic encryption. In order to avoid this problem, multi-party computa- tion(MPC) based privacy-preserving machine learning(PPML) was introduced. How- ever, this method cannot use pre-trained parameters due to the hardness to use exact Rectified Linear Unit (ReLU) in PPML. Recently, using minimax approximate poly- nomials for sign functions for HE-PPML[2, 3, 4], MPC-PPML without bootstrapping can be implemented with communication cost in the client-server model. Since HE- friendly networks do not use non-arithmetic functions like ReLU or max pooling, their inferences are light and fast. However, low classification accuracy and training the data are very difficult, and thus using pre-trained parameters is a very significant issue in the PPML. Thus I propose a method that improves DELPHI [7] algorithm to inference with pre-trained parameters on homomorphic encryption. In terms of the computation time and communication cost the proposed method has better performance compared to DELPHI, the previous work of MPC-based inference schemes. Second, a new attack algorithm is proposed for a secure key generation and man- agement method introduced by Yang and Wu. It was previously claimed that the key generation method of Yang and Wu[46] using a keystore seed was information- theoretically secure and could solve the long-term key storage problem in cloud sys- tems, thanks to the huge number of secure keys that the keystore seed can generate. i Their key generation method, however, is considered to be broken if an attacker can recover the keystore seed. In this dissertation, I propose an attack algorithm to recon- struct the keystore seed of the Yang–Wu key generation method from a small number of collected keys. For example, when t = 5 and l = 27, it was previously claimed that more than 253 secure keys could be generated, but the proposed attack algorithm can reconstruct the keystore seed based on only 84 collected keys. Hence it turns out that the Yang–Wu key generation method is not information-theoretically secure when the attacker can gather multiple keys and a critical amount of information about the keystore seed is leaked.

이 학위 논문에서는 다음 두 가지의 연구가 이루어졌다: i) 정보보호 머신러닝에 서 통신 환경을 사용하여 bootstrapping을 대체한 암호문 새로고침 방법 ii) 키 스토어 시드 기반 비밀 키 생성의 문제점 및 공격 방식. 첫 번째로, 동형암호를 이용한 정보보호 머신러닝의 가장 큰 문제점인 bootstrap- ping 시간이 매우 크다는 단점을 해결하기 위해 통신 환경을 이용하였다. 랜덤한 값 을 더해서 유저에게 보내준 후 유저가 복호화 및 재 암호화를 통해 암호문의 레벨을 올려주어 bootstrapping 효과를 대체할 수 있고, 기존 연구들에 비해 시간 및 통신량 측면에서도 좋은 성능을 유지하면서 pre-trained 네트워크에서도 사용가능한 것을 확인하였다. 또한 중요한 파라미터인 정확도 측면에서도 기존 결과와 유사한 값을 유지하면서 다른 문제점 없이 성능 개선을 하였음을 확인하였다. 두 번째로, 키 스토어 시드 기반 비밀 키 생성 방법의 문제점과 그에 대한 선형 공격을 제기한다. 확률적으로 작은 개수의 키가 모였을 때에도 공격이 가능한 것을 확인하여 그에 맞는 수식적인 문제도 제기하였다. 마지막으로 그 선형 공격을 막을 수 있는 방식을 제공하며 기존의 문제점에 대한 해결책도 제시하였다.