ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2019, Vol. 56 ›› Issue (3): 496-507.doi: 10.7544/issn1000-1239.2019.20170443

Previous Articles     Next Articles

Leveled Fully Homomorphic Encryption Against Adaptive Key Recovery Attacks

Li Zengpeng1,2, Ma Chunguang1, Zhao Minghao3   

  1. 1(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001); 2(College of Computer Science and Technology, Qingdao University, Qingdao, Shandong 266071); 3(School of Software, Tsinghua University, Beijing 100084)
  • Online:2019-03-01

Abstract: A major open problem is to protect leveled homomorphic encryption from adaptive attacks that allow an adversary to learn the private key. In order to achieve the goal of preventing key recovery attacks on fully homomorphic encryption (FHE), Li Zengpeng et al (PROVSEC’16) proposed an multiple secret keys fully homomorphic encryption scheme under the learning with errors (LWE) assumption to prevent key recovery attacks on FHE, which did not use the notion of “valid ciphertexts” of Loftus et al (SAC’11). However, utilizing the information of noise, the attacks can still recover the information of the secret key. Li Zengpeng et al.’s scheme cannot provide an efficient method to protect the secret key. In this paper, Inspired by the work of Li Zengpeng et al (EPRINT’16), we first give a new method of key recovery attacks to Li Zengpeng et al.’s scheme; then, we propose a new FHE scheme with multiple secret keys which differs from EPRINT’16, and prove our new scheme against key recovery attacks. Our main idea is to adopt the dual version of encryption algorithm and generate a “one-time” secret key every time, so that even if an attacker can learn some bits of the one-time private key from each decryption query and cannot obtain some bits of noise, the scheme still does not allow them to compute a valid private key.

Key words: adaptive key recovery attacks, lattice-based cryptography, learning with errors, fully homomorphic encryption, multiple secret keys

CLC Number: