# Blockchain-Assisted Verifiable and Multi-User Fuzzy Search Encryption Scheme
## 6 Program Analysis
### Security Analysis  
Theorem 1: _The scheme is secure under the adaptive selection of keyword attacks when CS and external adversaries can only divulge what they are allowed to._  
Proof: For adversary \(\mathcal{A}\), a stateful simulator \(\mathcal{B}\) satisfies the condition \(|Pr[Real_{\mathcal{A}}(\lambda)]-Pr[Ideal_{\mathcal{A}\mathcal{B}}(\lambda)] |\leq negl^{*}(\lambda)\), where \(negl^{*}(\lambda)\) is a negligible probability. From the proof equivalence in the scheme in [27], the simulation-based game proofs are equivalent to indistinguishable game proofs. \(\mathcal{A}\) only needs to analyze the differentiation between \(\mathcal{B}\) to win the game, \(Pr[Ind_{\mathcal{A}}(\lambda)=1]-1/2\leq negl^{*}(\lambda)\) is used to prove the scheme is secure. \(\mathcal{B}\) simulates the process of generating ciphertexts, indexes, and trapdoors as follows. (1) Generate ciphertext \(C^{*}\) by simulation. According to \(\mathcal{L}_{1}(D)=\left\{\Big{|}D\Big{|},n,\{|F_{i}|,ind(F_{i})\}_{i\in[1,n]} \right\}\), \(B\) generates \(n\) ciphertexts of \(\Big{|}F_{i}\Big{|}_{i\in[1,n]}-\) bit uniformly at random to simulate the encrypted file set \(C^{*}=\{C_{1},C_{2},\ldots,C_{n}\}\), which is encrypted by AES. According to the semantic security of symmetric encryption, the ciphertext \(C\) generated by \(Rel_{\mathcal{A}}(\lambda)\) and the ciphertext \(C^{*}\) generated by \(Ideal_{\mathcal{A}}\), \(g(\lambda)\) are computationally indistinguishable, i.e., the advantage of the adversary's victory can be ignored, i.e., \(|Pr[Encrypt(F,K_{i})\to C]-Pr[Sim\to C^{*}]\mid\leq negl_{1}{}^{*}(\lambda)\). (2) Generate search trapdoor \(T^{*}\) by simulation. According to \(\mathcal{L}_{2}(D,W_{q}{}^{*})=\left\{P(W_{q}{}^{*}),T^{*}\right\}\), \(B\) maps each keyword in \(W_{q}{}^{*}=(w_{1},w_{2},\ldots,w_{q})\) to the bloom filter, its search trapdoor is denoted as \(T_{Q}=(T_{Q}t,T_{Q}^{\prime\prime})\), where \(T_{Q}t^{\prime}=(M_{1}{}^{-1}\cdot B_{Q}t)\), \(T_{Q}^{\prime\prime}=(M_{2}{}^{-1}\cdot B_{Q}^{\prime\prime})\), \(B_{Q}t^{\prime}=(t_{1}^{\prime},t_{2}^{\prime\prime},\ldots,t_{m}^{\prime})\), \(t_{j}^{\prime}=t_{j}^{\prime}/2+r^{\prime}\), and \(t_{j}^{\prime\prime}=t_{j}^{\prime\prime}/2-r^{\prime}\). The probability of \(\mathcal{B}\) simulating the search token \(T_{Q}\) is negligible when the \(KS\) is unknown. Due to the introduction of the random value \(r^{\prime}\) in the encrypted query and the pseudo-random nature of the key set \(KS\), the simulator \(\mathcal{B}\) randomly selects \(KS^{*}\) and \(r^{*}\) to construct the feasible search token with probability \(Pr[T_{Q}=T^{*}]\approx Pr[r^{\prime}=r^{*}]\approx Pr[KS=KS^{*}]\approx 1/2^{k} \leq neg_{2}{}^{*}(\lambda)\), thus the advantage of \(\mathcal{B}\) to simulate the feasible search trapdoor is negligible. (3) Simulated construction of index \(I^{*}\). In the process of generating the secure index based on the leakage function \(\mathcal{L}_{1}\), \(\mathcal{L}_{2}\), simulator \(\mathcal{B}\) picks a random value to replace the random number used in the real case. According to the secure \(KNN\) encryption algorithm, it is known that the secure \(KNN\) algorithm using random numbers is indistinguishable. Meanwhile, the matrix picked for the key set \(KS\) is a sufficiently large invertible matrix and \(KS\) is not artificially compromised. Thus, the advantage of winning for the polynomial adversary satisfies (3), which is negligible. \[\big{|}Pr[BuildIndex(SK,F_{i},KW_{F_{i}})\to I_{real}]-Pr[Sim\to I^{*}] \big{|}\leq negl_{3}{}^{*}(\lambda) \tag{3}\]  
Since the adversary wins this indistinguishability game by analyzing ciphertexts, indexes and search credentials, the advantages of the adversary in distinguishing between real ciphertexts and simulated ciphertexts, real indexes and simulated ciphertexts, and real search tokens and simulated search tokens, respectively, are denoted as \(Adv_{\mathcal{A}}(C,C^{*})\), \(Adv_{\mathcal{A}}(I_{real},I^{*})\) and \(Adv_{\mathcal{A}}(T_{\mathbb{Q}},T^{*})\). Then we get (4). \[