格上随机喻示模型下带关键字检索的公钥加密体制

Public Key Encryption with Keyword Search from Lattices in Random Oracle Model

近年来,基于格的密码体制受到越来越多的关注。这类密码具有诸多潜在优势:抗量子攻击、并行性好、概念简单、安全性所基于的困难问题的随机实例难解性等价于格上公认困难问题最坏情况等。带关键字检索的公钥加密(PEKS)体制是一种具有关键字检索功能的加密机制:用PEKS加密的关键字w的密文和加密消息存储在服务器上,用户向服务器发送一个秘密值Tw,服务器可以搜索出所有包含该关键词w的加密消息,但无法知晓w本身的任何内容。提出了一种基于格的带关键字检索的公钥加密体制,并在随机喻示模型下,基于格上带错误的学习(Learning With Errors)问题的困难性假设证明了新体制的安全性。

Recently, lattice-based cryptography has acquired much attention. This kind of cryptography has many potential advantages： their resistance so far to cryptanalysis by quantum algorithms, their asymptotic efficiency and conceptual simplicity, and the guarantee that their random instances are as hard as the hardness of lattice problems in worst case. Public key encryption with keyword search （PEKS） is a mechanism for searching on encrypted data. The mechanism enables one to search encrypted keywords without compromising the security of the original data. Suppose Bob wants to send Alice a message m with keyword w. He encrypts m using a standard public key encryption and appends to the resulting cipher-text of PEKS cipher-text of keyword w. This kind of encrypted messages may be stored in a server. Alice can send a secret value Tw to a server that will enable the server to locate all encrypted messages containing the keyword w, but learn nothing else. A public key encryption with keyword search was proposed using lattices. The scheme could be proven secure with the hardness of the standard Learning With Errors （LWE） problem in the random oracle model.