Public key encryption with searchable keywords based on Jacobi symbols

Public-key encryption schemes with searchable keywords are useful to delegate searching capabilities on encrypted data to a third party, who does not hold the entire secret key, but only an appropriate token which allows searching operations but preserves data privacy. Such notion was previously proved to imply identity-based public-key encryption [51 and to be equivalent to anonymous (or key-private) identity-based encryption which are useful for fully-private communication. So far all presented public-key encryption with keyword search (PEKS) schemes were based on bilinear forms and finding a PEKS that is not based on bilinear forms has been an open problem since the notion of PEKS was first introduced in [5]. We construct a public-key encryption scheme with keyword search based on a variant of the quadratic residuosity problem. We obtain our scheme using a non-trivial transformation of Cocks' identity-based encryption scheme [9]. Thus we show that the primitive of PEKS can be based on additional intractability assumptions which is a conventional desiderata about all cryptographic primitives.