# MinHash-Based Fuzzy Keyword Search of Encrypted Data across Multiple Cloud Servers
## The Proposed Fuzzy Keyword Search Scheme Based on MinHash
### The Proposed Scheme  
The proposed scheme focuses on the construction of encrypted search based on the MinHash algorithm that is comprised of the following steps:  
1. Setup (k): The data owner inputs security parameter k and outputs a p-order cyclic group G based on g. Assume that there is a one-way hash function F(\(\cdot\)): [0,1]*\(\rightarrow\)[0,1]n, a homomorphic hash function H(\(\cdot\)) and a hash function Z(\(\cdot\)) for compression. Let En(\(\cdot\)) be a packet encryption algorithm for file encryption, Index(\(\cdot\)) be the key index for public key encryption and E'\({}_{sk}\)(\(\cdot\)) be the public key encryption algorithm for digital signature. The data owner randomly selects the master key s \(\in\ Z_{p}^{*}\) and an auxiliary key s' \(\in\ Z_{p}^{*}\), calculates h = g* and h' = g*' \(\sim\) g*', randomly selects a pseudo-random function f:[0,1]k \(\times\ Z_{p}^{*}\)\(\rightarrow\)\(Z_{p}^{*}\) as well as a random parameter t \(\in\) {0,1}k. The data owner could then get H(x):[0,1]*\(\rightarrow\)\(Z_{p}^{*}\) and H'(x):[0,1]*\(\rightarrow\)\(Z_{p}^{*}\), select a symmetric key K for packet encryption algorithm En(\(\cdot\)) and publish params = (G, g, p, f, H, H', h, En(\(\cdot\))) to complete the generation of the public parameters and keys. 2. Add-user (u\({}_{i}\)): The data owner generates u\({}_{i}\) = {a\({}_{1}\), a\({}_{2}\),..., a\({}_{x}\)} according to the user's access and sends the user table to the cloud servers S\({}_{1}\), S\({}_{2}\),..., S\({}_{N}\), where a\({}_{i}\) is the user's attribute. 3. The server determines whether the user has access to the file by comparing the attributes of the user and the attributes required to access the file, then sends (t, K, s') to u\({}_{i}\). 4. BuildIndexTree (h', W): The data owner extracts the set of keywords W = {w\({}_{1}\), w\({}_{2}\),..., w\({}_{n}\)} from the document set F = {f\({}_{1}\), f\({}_{2}\),..., f\({}_{m}\)}, uses the keyword fingerprint generation algorithm based on MinHash, obtains the fingerprint S\({}_{1}\) corresponding to each keyword w\({}_{i}\), that creates unique document identifiers for each document FID\({}_{i}\) (1 \(\leq\) j \(\leq\) m), where FID\({}_{w_{i}}\) represents the set of identifiers for all documents containing the keyword w\({}_{i}\). 5. Encrypt (K, s', t, D, W): The data owner enters the packet key K, the auxiliary key s', the random parameter t, file D and its keyword list W= {w\({}_{1}\), w\({}_{2}\),..., w\({}_{d}\)}, randomly selects r \(\in\)\(Z_{p}^{*}\), calculates g', h'' = (h')r and h', and sends h'' to the cloud server S. It should then calculate \(\delta_{i}\) = f[t,H(w\({}_{i}\))] and E(w\({}_{i}\)) according to Equation (5), make I = (g\({}^{r}\), h\({}^{r}\), E(w\({}_{1}\)), E(w\({}_{2}\)),..., E(w\({}_{d}\))), calculate C = En\({}_{K}\)(D) and sends I and the encrypted index structure to the cloud server S. The set of ciphertext documents C = (c\({}_{1}\), c\({}_{2}\),..., c\({}_{m}\)) are divided into N portions according to some rules and then sent to the cloud servers S\({}_{1}\), S\({}_{2}\),..., S\({}_{N}\). \[\text{E}({\text{w}_{i}})=\text{g}^{\text{r}(s^{\prime}+\delta_{i})},1\leq\text{ i}\leq\text{d}\] (5)
6. S-Encrypt(I): The server S executes the algorithm to re-encrypt the index I, enters index I and h'', calculates E'(w\({}_{i}\)) according to Equation (6) and I' = (g\({}^{r}\), h\({}^{r}\), E'(w\({}_{1}\)), E'(w\({}_{2}\)),..., E'(w\({}_{d}\))), calculates H'[E(w\({}_{1}\))], H'[E(w\({}_{2}\))],..., H'[E(w\({}_{d}\))] to replace the corresponding keywords, and sends the newly generated keyword index structure to the cloud server S\({}_{1}\), S\({}_{2}\),..., S\({}_{N}\).