# A Privacy-Preserving Scheme for a Traffic Accident Risk Level Prediction System
## 4 Materials and Methods
### Our Security Approach
#### 4.3.3 Complexity Analysis  
In this subsection, we analyze the complexity of our proposal.  
Data Preprocessing  
We preprocessed the data by performing tasks such as filtering relevant columns. This process is performed in polynomial time, i.e., \(\mathcal{O}(n)\), where \(n\) is the number of elements or size of the input. There is no significant computational overhead at this stage.  
FHE Complexity  
Since our security approach uses FHE, one has to analyze the complexity of the following steps: Key Generation (Algorithm 1-line 2), Compiling (Algorithm 1-line 4), Encryption 1-line 5, and Inference (Algorithm 2-line 6).  
* Key Generation: For Homomorphic Encryption, the key generation process involves a polynomial operation depending on the security level (number of bits) [36]. Then, the complexity of this step is \(\mathcal{O}(b)\), where \(b\) is the number of bits used according to the security level.
* Compiling: The compilation process in FHE refers to preparing a model (such as a decision tree or neural network) to be used in encrypted form, specifically transforming it into a format where computations can be performed homomorphically [37]. The model compilation phase involves operations like quantization, ciphertext packing, and transformation of operations into homomorphic equivalents. This compilation task has a quadratic time complexity as encryption is applied to each element [36]. Then, the complexity of this step is \(\mathcal{O}(n^{2})\), where \(n\) is the number of elements or size of the input.
* Encryption: We use a privacy-preserving machine learning framework to implement our scheme (see Section 5.2.2). This framework uses TFHE (Torus Fully Homomorphic Encryption) [36] or similar lattice-based encryption schemes. The complexity of encrypting a message in TFHE is typically linear in the size of the plaintext (which is impacted by the quantization bit-width), and polynomial in the security parameter [37]. Then, for this framework, the encryption complexity is \(\mathcal{O}(n\times\lambda)\), where \(n\) is the number of bits in the quantized plaintext, i.e., size of the input (e.g., a 4-bit or 8-bit quantized value), and \(\lambda\) is the security parameter, which typically grows with the required level of encryption strength.
* Inference: In this framework, the complexity of FHE-based inference is the sum of the complexities of the individual operations required for the model and the complexity of the homomorphic operations. For decision trees, for instance, the complexity per prediction depends on the depth \(d\) of the tree, i.e., the complexity of the unencrypted model is \(\mathcal{O}(d)\). Next, in the encrypted model, since each comparison and decision involves homomorphic operations, the complexity of a single prediction is \(\mathcal{O}(d\times\lambda^{2})\), where \(d\) is the depth of the decision tree and \(\lambda^{2}\) represents the cost of each homomorphic operation. That is, the complexity is quadratic in the security parameter (\(\lambda^{2}\)) [37] and linear in the depth \(d\) of the tree or the complexity model that is being used.