摘要：In this paper, we deal with a method to securely process a query to a database outsourced to a remoteserver. In particular we are interested in a wildcard query in which a database query statement contains awildcard character. Moreover, we consider a setting where users’ data are very sensitive (e.g., medicalinformation) so that they should be handled very carefully in the light of security. To this end, we use afully homomorphic encryption scheme as a baseline encryption. Together with this encryption scheme, ourbasic idea to the wildcard query problem is to segment an input string as gram and to represent the gram into the correspnong polynomial . Later a user sends a wildcard pattern including ,then the server evaluate the polynomial as , and so if the evaluation result is equal to 0, then itimplies that the string involves the pattern as a substring. All computations are performed on encryptionsso that we can guarantee that it is as secure as the baseline encryption scheme applied to the protocol.Finally our construction only requires multiplicative depth log where is the maximum length ofstrings.
