In this paper, we present an efficient deterministic public key encryption scheme in the auxiliary-input setting from lattices. The public key size, ciphertext size and ciphertext expansion factor are improved compared with the scheme proposed by Brakerski and Segev. Our scheme is also secure even in the multi-user setting where related messages may be encrypted under multiple public keys. In addition, the security of our scheme is based on the hardness of the learning with errors (LWE) problem which remains hard even for quantum algorithms.
Furthermore, we consider deterministic identity-based public key encryption (D-IBE) in the auxiliary-input setting. The only known D-IBE scheme (without considering auxiliary inputs) in the standard model was proposed by Bellare et al. in EUROCRYPT'12. However, this scheme is only secure in the selective security setting, and Bellare et al. identified it as an open problem to construct adaptively secure D-IBE schemes. The second contribution of this work is to propose a D-IBE scheme from lattices that is adaptively secure.
Category / Keywords: public-key cryptography / deterministic (identity-based) public key encryption, auxiliary inputs, lattices Publication Info: Full version of the paper accepted by SCN2012 Date: received 14 Aug 2012 Contact author: xiexiang at is iscas ac cn Available formats: PDF | BibTeX Citation Version: 20120814:065646 (All versions of this report) Discussion forum: Show discussion | Start new discussion