# Blockchain-Assisted Verifiable and Multi-User Fuzzy Search Encryption Scheme
## 5 Proposed Scheme
### Trapdoor Generation
#### 5.2.3 Search Match  
_Search\((Index_{tree},T_{t})\)_: \(DO\)_ defines a reasonable search unit price \(\$search\), then sets \(\$pro\_DU\) as the deposit of \(DU\) stored temporarily in \(SC\) to prevent \(DU\) from quitting in the middle. \(\$All\) represents the total price that \(DU\) should pay for each search transaction and \(\$search\_price\) represents the overhead of calling the search algorithm. _gas_lim_ and  
Figure 4: The index tree.  
gas_price_ respectively represent the maximum gas consumption and gas unit price in the \(SC\), and the product of the two represents the maximum price that the \(SC\) is allowed to accept.  
\(SC\) obtains the user's search trapdoor and \(user\_id\) through the transaction. After authenticating whether the identity is correct, it checks whether the pre-deposit of \(DU\) satisfies the search transaction, if it does, a search match will be performed, otherwise, the transaction is canceled.  
The index tree will be traversed from top to bottom. Meanwhile, \(SC\) calculates \(T^{T}\cdot I_{i}\), which represents the correlation score \(Score\) of the node and search keywords, where \(T\cdot I_{i}=\left\{M_{1}{}^{-1}B_{i}t\cdot M_{1}^{T}B_{i}t+M_{2}{}^{-1}B_{i}^{ \prime\prime}\cdot M_{2}^{T}B_{i}^{\prime\prime}\right\}\). If the \(Score\) of the parent node vector and the search trapdoor is less than the threshold \(TH\), the traversal of the node's children is stopped. The entire index tree is traversed in this way.  
\(SC\) defines a list \(Sclist\), which consists of at most \(k_{n}\) records. Each entry contains a pair \(<Score_{F_{i}},value>\), where \(value=\left\{FID\big{|}|C_{K_{i}}\big{|}|MAC_{C_{i}}\right\}\), \(Score=\left\{T*I_{i}\right\}\). When traversing to the leaf node, \(SC\) stores the information of leaf node in \(Sclist\). After traversing the index tree, \(SC\) sorts and eliminates the \(k_{n}\) entries of \(Sclist\) based on \(Score_{F_{i}}\). Finally the \(k\) entries that match the user's search are obtained, then \(SC\) sends the \(value\) in \(RList\) to \(DU\), sends the \(FID\) and transaction information in \(value\) to the \(CS\). After receiving the message, \(CS\) packages the ciphertext set \(C\) and sends it to the \(DU\).  
\(SC\) uses GDFS (Greedy Depth-First Search) for searching, the notation and Algorithm 1 used are described as follows.  
\(Score_{nd}\): correlation score between index vector \(I_{i}\) of node \(nd\) and search vector \(T\).  
\(nd.hcld\): child nodes of node \(nd\) with high query relevance.  
```
Input: the index tree \(Index_{tree}\) Output: \(Sclist\)
1: if\(nd\) is not a leaf node then
2: if\(Score_{nd}\) > \(TH\) then
3: GDFS (\(nd.hcld\))
4: GDFS (\(nd.lcld\))
5: else
6: return
7: end if
8: else
9: if\(Score_{F_{i}}>TH\)&&\(Sclist\) is full
10: delete the lowest relevance node from \(Sclist\)
11: insert the new node \(<Score_{F_{i}},value>\) and sort all the node by \(Score_{F_{i}}\)
12: else if\(Score_{F_{i}}>TH\)&&\(Sclist\) is not full
13: insert the new node \(<Score,value>\) in \(Sclist\)
14: end if
15: return
16: end if
```  
**Algorithm 1** Search Matching Algorithm  
As the child nodes are overwritten by parent nodes, only part of the tree needs to search. As in Figure 4, the file collection \(D=\left\{F_{1},F_{2},\ldots,F_{7}\right\}\), the threshold \(TH\) is set to 1.5, and the trapdoor \(T=(0,1,0,1,0)\) is sent to \(SC\) by the user. Assume that 1 most relevant file for the search is selected.  
\(SC\) traverses the nodes from top to bottom and computes \(Score\) for each node. The children of \(L_{11}\) do not need to traverse due to \(Score_{Root}=2.5>TH\), \(Score_{L_{11}}=1<TH\), \(Score_{R_{12}}=2>TH\),\(Score_{R_{23}}=1.8>TH\), \(Score_{F_{5}}=1<TH\),\(Score_{F_{6}}=1.6>TH\) and \(Score_{F_{7}}=1.5>TH\). The information of \(F_{6}\) and \(F_{7}\) is finally added to \(Sclist\), \(SC\) ranks \(F_{6}\) and \(F_{7}\) in \(Sclist\) according to \(Score\), then \(F_{7}\) is eliminated.