# Blockchain-Assisted Verifiable and Multi-User Fuzzy Search Encryption Scheme
## 7 Efficiency Analysis
### Complexity Theoretical Analysis  
In this section, the performance will be analyzed from three aspects: index tree generation, trapdoor generation, and search matching.  
* **Index tree generation.** The cost of file index generation includes the generation of a plaintext index vector for each file and the encryption of the plaintext index vector. Where the generation of the index is mainly linked to the number of keywords, the encryption of the plaintext vector mainly consists of the factorization operation of the vector and multiplication with a matrix of order \(l\times l\). The time overhead of single file index generation is \(O(l^{2})\). The \(Index_{tree}\) generates \((n-1)\) additional nodes at the internal nodes when the number of files is \(n\). Therefore, the cost of the \(Index_{tree}\) generation is a little higher than the other schemes, but it is generated by the \(DUI\) locally and upload to the smart contract only once.
* **Trapdoor Generation.** The cost of trapdoor generation mainly consists of generating an \(l\) bit plaintext trapdoor and performing matrix multiplication operations on the plaintext trapdoor, so the cost of trapdoor generation is \(O(l^{2})\).
* **Search Match.** The Search and Match includes traversing the \(Index_{tree}\), the calculation of the inner product of trapdoors and index vectors, and sorting the files to filter out rejections based on relevance. In this scheme, only the \(n_{k}\) most relevant ciphertext files are searched. These files and child nodes share the same access path, so the traversal of the \(Index_{tree}\) only touches a portion of \(n\) nodes i.e., on \(r(r<<n)\) paths from the root to the leaf nodes instead of traversing the child nodes repeatedly, hence the time complexity is \(O(r\log n)\).  
In Table 3, the efficiency is compared in terms of index generation, trapdoor generation, and search time. Here, \(n\) is the number of files, \(Q\) is the number of exact keywords, \(Z\) is the maximum number of fuzzy keywords, and \(l\) denotes the index length in the proposed scheme. In the scheme, \(l\) can be treated as a constant and \(n<<Q<<Z\).  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Scheme** & **Scheme [15]** & **Scheme [28]** & **Scheme [25]** & **Scheme [29]** & **Scheme [21]** & **Ours** \\ \hline Multi-Keyword & ✓ & ✓ & ✓ & ✓ & ✓ & ✓ \\ Dynamic Updates & ✓ & x & ✓ & x & ✓ & ✓ \\ Fuzzy Search & ✓ & x & x & ✓ & ✓ & ✓ \\ Integrity Verification & x & ✓ & ✓ & x & ✓ & ✓ \\ Correctness Verification & x & ✓ & ✓ & ✓ & ✓ & ✓ \\ Related Sorting & ✓ & ✓ & x & ✓ & ✓ & ✓ \\ \hline \hline \end{tabular}
\end{table}
Table 2: Functionality Comparison of Different Schemes.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Scheme** & **Scheme [30]** & **Scheme [31]** & **Scheme [21]** & **Ours** \\ \hline Index Generation & \(O(ZQ)\) & \(O(ZQ)\) & \(O(nl^{2})\) & \(O((2n-1)l^{2})\) \\ Trapdoor Generation & \(O(Z)\) & \(O(Z)\) & \(O(l^{2})\) & \(O(l^{2})\) \\ Search Cost & \(O(Z)\) & \(O(Z\log Q)\) & \(O(nl)\) & \(O(r\log n)\) \\ \hline \hline \end{tabular}
\end{table}
Table 3: Time Complexity of Different Schemes.