# A Privacy-Preserving Record Linkage Method Based on Secret Sharing and Blockchain
## 4 Methods
### Output and Audit Module
#### 4.4.4 Record Keeping and Provenance
Boolean secret share generation is also local, with computational complexity \(O(N_{i}\cdot m\cdot t)\), totaling \(\sum O(N_{i}\cdot m\cdot t)\); this step also involves uploading \(N_{i}\cdot t\) shares to IPFS (communication cost \(\text{Cost}_{\text{IPFS}}(N_{i}\cdot t\cdot m)\)) and recording CIDs on the blockchain (on-chain write cost \(\text{Cost}_{\text{BC}_{\text{evrite}}}(N_{i}\cdot t)\)). Mask generation is executed by smart contracts, with on-chain computational complexity approximately \(O(K\cdot m\cdot t)\), accompanied by IPFS uploads (cost \(\text{Cost}_{\text{IPFS}}(2\cdot K\cdot m\cdot t+t)\)) and on-chain CID recording (cost \(\text{Cost}_{\text{BC}_{\text{evrite}}}(2\cdot K\cdot m\cdot t+t)\)). The computational complexity of node selection on-chain is denoted as \(O(\text{BC}_{\text{select}}(N_{\text{nodes}}))\). In the data distribution phase, the smart contract processes \(M\) record pairs, involving grouping, node selection, permutation generation, and index creation, with on-chain computational complexity approximately \(O(M\cdot t\cdot(\text{VRF}+t))\), and requires writing \(M\cdot t^{2}\) index records to the blockchain (cost \(\text{Cost}_{\text{BC}_{\text{evrite}}}(M\cdot t^{2})\)). In the approximate matching module, processing is performed for \(M\) record pairs, each handled by \(t\) computing nodes in parallel. For each pair, data retrieval involves each node querying the blockchain (total cost \(O\big{(}t^{2}\cdot\text{Cost}_{\text{BC}_{\text{rand}}}(1)\big{)}\)) and downloading data from IPFS (total cost \(O\big{(}t^{2}\cdot 5\cdot\text{Cost}_{\text{IPFS}}(m)\big{)}\)). The total computational complexity for local difference computation and masking is \(O(t\cdot m)\). In the batch interaction phase, nodes exchange masked difference vectors via IPFS and blockchain, with total communication cost approximately \(O\big{(}t^{2}\cdot\text{Cost}_{\text{IPFS}}(m)+t\cdot\text{Cost}_{\text{BC}_ {\text{evrite}}}(1)\big{)}\). Reconstruction and B2A conversion are computational bottlenecks, with total computational complexity \(O\big{(}t^{2}\cdot m\big{)}\). The final Hamming distance partial sum has computational complexity \(O(t\cdot m)\), requiring result uploads to IPFS (total cost \(O(t\cdot\text{Cost}_{\text{IPFS}}(\text{scalar}))\)) and CID submission to the blockchain (total cost \(O\big{(}t\cdot\text{Cost}_{\text{BC}_{\text{evrite}}}(1)\big{)}\)). Thus, the total computational complexity for the approximate matching phase across all \(M\) pairs is approximately \(O\big{(}M\cdot t^{2}\cdot m\big{)}\), with IPFS communication complexity approximately \(O\big{(}M\cdot t^{2}\cdot\text{Cost}_{\text{IPFS}}(m)\big{)}\), and blockchain communication complexity approximately \(O\big{(}M\cdot t^{2}\cdot\text{Cost}_{\text{BC}_{\text{rand}}}(1)+M\cdot 2 \cdot t\cdot\text{Cost}_{\text{BC}_{\text{evrite}}}(1)\big{)}\). In the output and audit module, the computational complexity for participants aggregating results is \(O(M\cdot t)\), with communication costs approximately \(O\big{(}M\cdot\text{Cost}_{\text{BC}_{\text{rand}}}(t)+M\cdot t\cdot\text{Cost} _{\text{IPFS}}(\text{scalar})\big{)}\). The audit verification process involves recomputing \(s\cdot M\cdot t\) shares, with total audit computational complexity approximately \(O\big{(}s\cdot M\cdot t^{3}\cdot m\big{)}\), and



might still infer information from metadata (like CIDs or task assignment indices on the blockchain), network traffic, or IPFS access timings as side-channels. Further considering extreme scenarios where a majority of nodes are compromised:
* If a majority of computation nodes are compromised: On the privacy front, an attacker's chances of collecting all \(t\) shares for a record increase, but they still face the \(t!\) complexity from random permutation. In terms of result integrity, if most computation nodes in a specific task are malicious, they could collude to submit erroneous results, relying on verification node sampling audit as the main check.