Abstract
Private Decision Tree Evaluation (PDTE) allows the client to use a decision tree classification model on the server to classify their private data, without revealing the data or the classification results to the server. Recent advancements in PDTE have greatly enhanced its effectiveness in scenarios involving semi-honest security, offering a viable and secure alternative to traditional, less secure approaches for decision tree evaluation. However, this model of semi-honest security may not always align well with real-world problems. In this work, we present FSSTree, a malicious-secure three-party PDTE protocol using function secret sharing (FSS). FSSTree achieves its high performance against malicious adversaries via several innovative cryptographic designs. Especially, 1) we transform a comparison operation into a prefix parity query problem, allowing us to implement malicious-secure comparisons rapidly using lightweight and verifiable FSS. 2) Building upon this, we further propose a constant-round protocol for securely evaluating Conditional Oblivious Selection (COS). 3) We utilize these optimized protocols to enhance the PDTE processes, achieving a considerable decrease in both communication costs and the number of rounds. The experimental results show that FSSTree reduces the runtime in a WAN environment by up to \(22.3\times \) times and saves up to \(4.1 \times \) the communication cost compared to the state-of-the-art work.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Araki, T., Furukawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 805–817 (2016)
Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, pp. 535–548 (2013)
Bai, J., Song, X., Zhang, X., Wang, Q., Cui, S., Chang, E.C., Russello, G.: Mostree: malicious secure private decision tree evaluation with sublinear communication. In: Proceedings of the 39th Annual Computer Security Applications Conference, pp. 799–813 (2023)
Bost, R., Popa, R.A., Tu, S., Goldwasser, S.: Machine learning classification over encrypted data. In: NDSS Symposium 2015, pp. 1–14. Internet Society (2015)
Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 337–367. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_12
Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing: improvements and extensions. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 1292–1303 (2016)
Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptol. 13, 143–202 (2000)
de Castro, L., Polychroniadou, A.: Lightweight, maliciously secure verifiable function secret sharing. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13275, pp. 150–179. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-06944-4_6
Chida, K., et al.: Fast large-scale honest-majority MPC for malicious adversaries. J. Cryptol. 36(3), 15 (2023)
Damgård, I., Escudero, D., Frederiksen, T., Keller, M., Scholl, P., Volgushev, N.: New primitives for actively-secure mpc over rings with applications to private machine learning. In: 2019 IEEE Symposium on Security and Privacy (SP), pp. 1102–1120. IEEE (2019)
De Cock, M., et al.: Efficient and private scoring of decision trees, support vector machines and logistic regression models based on pre-computation. IEEE Trans. Dependable Secure Comput. 16(2), 217–230 (2017)
Fu, J., Cheng, K., Xia, Y., Song, A., Li, Q., Shen, Y.: Private decision tree evaluation with malicious security via function secret sharing. Technical report, Xidian University (2024). https://github.com/BlackFH/FSSTree/blob/main/FSSTree-full.pdf
Furukawa, J., Lindell, Y., Nof, A., Weinstein, O.: High-throughput secure three-party computation for malicious adversaries and an honest majority. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 225–255. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_8
Gupta, K., et al.: Sigma: secure GPT inference with function secret sharing. Cryptology ePrint Archive (2023)
Ishai, Y., Paskin, A.: Evaluating branching programs on encrypted data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 575–594. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70936-7_31
Ji, K., Zhang, B., Lu, T., Li, L., Ren, K.: UC secure private branching program and decision tree evaluation. IEEE Trans. Dependable Secure Comput. 20(4), 2836–2848 (2023)
Kiss, Á., Naderpour, M., Liu, J., Asokan, N., Schneider, T.: SoK: modular and efficient private decision tree evaluation. Proc. Priv. Enhanc. Technol. 2, 187–208 (2019)
Lindell, Y.: How to simulate it – a tutorial on the simulation proof technique. In: Lindell, Y. (ed.) Tutorials on the Foundations of Cryptography. ISC, pp. 277–346. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57048-8_6
Lindell, Y., Nof, A.: A framework for constructing fast MPC over arithmetic circuits with malicious adversaries and an honest-majority. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 259–276 (2017)
Liu, L., Su, J., Chen, R., Chen, J., Sun, G., Li, J.: Secure and fast decision tree evaluation on outsourced cloud data. In: Chen, X., Huang, X., Zhang, J. (eds.) ML4CS 2019. LNCS, vol. 11806, pp. 361–377. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30619-9_26
Ma, J.P., Tai, R.K., Zhao, Y., Chow, S.S.: Let’s stride blindfolded in a forest: sublinear multi-client decision trees evaluation. In: NDSS (2021)
Mohassel, P., Rindal, P.: ABY3: a mixed protocol framework for machine learning. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications security, pp. 35–52 (2018)
Rathee, D., et al.: CrypTFlow2: practical 2-party secure inference. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 325–342 (2020)
Storrier, K., Vadapalli, A., Lyons, A., Henry, R.: Grotto: screaming fast (2+ 1)-PC or z2n via (2, 2)-DPFs. In: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pp. 2143–2157 (2023)
Tai, R.K.H., Ma, J.P.K., Zhao, Y., Chow, S.S.M.: Privacy-preserving decision trees evaluation via linear functions. In: Foley, S.N., Gollmann, D., Snekkenes, E. (eds.) ESORICS 2017. LNCS, vol. 10493, pp. 494–512. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66399-9_27
Wagh, S., Tople, S., Benhamouda, F., Kushilevitz, E., Mittal, P., Rabin, T.: Falcon: honest-majority maliciously secure framework for private deep learning. Proc. Priv. Enhanc. Technol. 1, 188–208 (2021)
Wu, D.J., Feng, T., Naehrig, M., Lauter, K.: Privately evaluating decision trees and random forests. Proc. Priv. Enhanc. Technol. 4, 335–355 (2016)
Xu, G., et al.: VerifyML: obliviously checking model fairness resilient to malicious model holder. IEEE Trans. Dependable Secure Comput. (2023)
Zheng, Y., Duan, H., Wang, C.: Towards secure and efficient outsourcing of machine learning classification. In: Sako, K., Schneider, S., Ryan, P.Y.A. (eds.) ESORICS 2019. LNCS, vol. 11735, pp. 22–40. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-29959-0_2
Acknowledgement
We are grateful to the anonymous reviewers for their invaluable comments. Ke Cheng is the corresponding author. This research was supported by the National Key R&D Program of China (No. 2023YFB3107500), the National Natural Science Foundation of China (No. 62220106004), the Major Research Plan of the National Natural Science Foundation of China (No. 92267204), the Technology Innovation Leading Program of Shaanxi (No. 2022KXJ-093, 2023KXJ-033), Young Talent Fund of Association for Science and Technology in Shaanxi, China (No. 20240138), the Natural Science Basic Research Program of Shaanxi (Program No. 2024JC-YBQN-0701), the Innovation Capability Support Program of Shaanxi (No. 2023-CX-TD-02), the Shenzhen Science and Technology Program (No. CJGJZD20220517142005013), the Key R&D Program of Shandong Province of China (No. 2023CXPT056), and the Fundamental Research Funds for the Central Universities (No. XJSJ23040, ZDRC2202).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Security Proofs
A Security Proofs
We first prove the security of Verifiable Comparison Protocol \(\varPi _{\textsf {VCMP}}\), then we employ the universal composition (UC) theory [7] to prove that the other protocols satisfy the following definition.
Definition 4
(Three-party Secure Computation [3]). Let \(\mathcal {F}\) be the \(\textit{three-party}\) \(\textit{functionality}\). A protocol \(\varPi \) securely computes \(\mathcal {F}\) with abort in the presence of one malicious party, if for every party \(P_b\) corrupted by a probabilistic polynomial time (PPT) adversary \(\mathcal {A}\) in the real world there exists a PPT simulator S in the ideal world with F, such that
where \(x_b \in \{ 0, 1\}^*\) is the input provided by \(P_b\) for \(b \in \mathbb {Z}_3\), and \(z \in \{ 0, 1\}^*\) is the auxiliary information that includes the public input length information \(\{|x_b|\}_{b \in \mathbb {Z}_3}\). The protocol \(\varPi \) securely computes \(\mathcal {F}\) with abort in the presence of one malicious party with statistical error \(2^{-\lambda }\) if there exists a negligible function \(\mu (\cdot )\) such that the distinguishing probability of the adversary is less than \(2^{-\lambda } + \mu (\kappa )\).
1.1 A.1 Security Proof of Verifiable Comparison Protocol \(\varPi _{\textsf {VCMP}}\)
We prove that the verifiable comparison protocol \(\varPi _{\textsf {VCMP}}\) in Sect. 3.1 is secure by the following lemma.
Lemma 1
(Detection of Malicious Function Shares). The verifiable plaintext comparison protocol satisfies Definition 3.
Proof
We prove this lemma by contradiction. According to Lemma 2 and Lemma 3 in [8], when \(\textsf {VDPF.Verify}(\pi _0, \pi _1)\) outputs Accept, then the values \(y_0^{(x_i)} + y_1^{(x_i)}\) must be a subset of the truth table of the point function \(f^{\bullet }_{p, 1}\). Suppose there exists an input \(u \in \{x_i \}^\eta _{i=1}\) such that u does not satisfy Eq. 3. We categorize the discussion based on the values of u, when \(u > p\), based on the assumption, we have \(z_0^{(u)} + z_1^{(u)} = 0\). However, according to the definition of \(\varPi _{\textsf {VCMP}}\), we know that \(z_0^{(u)} + z_1^{(u)} = parity(p[0,u))\), since \(u > p\), it follows that \(parity(p[0,u)) = z_0^{(u)} + z_1^{(u)} = 1\). This contradicts the assumption that \(z_0^{(u)} + z_1^{(u)} = 0\). For the case where \(u \le p\), we can arrive at a similar conclusion, therefore the verifiable plaintext comparison protocol satisfies Definition 3.
1.2 A.2 Security Proof of Verifiable Conditional Oblivious Selection Protocol \(\varPi _{\textsf {cos}}\)
Theorem 1
\(\varPi _{\textsf {cos}}\) securely compute \(\mathcal {F}_{\textsf {cos}}\) in the \(\{\mathcal {F}_{\textsf {recon}}, \mathcal {F}^{[\![ \cdot ]\!]}_{\textsf {mul}}\}\)-hybrid model in the presence of a malicious adversary in the three-party honest-majority setting.
Proof
For any PPT adversary \(\mathcal {A}\), we construct a PPT simulator \(\mathcal {S}\) that can simulate the adversary’s view with accessing the functionality \(\mathcal {F}_{\textsf {cos}}\). In the cases where \(\mathcal {S}\) aborts or terminates the simulation, \(\mathcal {S}\) outputs whatever \(\mathcal {A}\) outputs.
Simulating Offline Phase. When the corrupted party \(P_b\) is the DPF key generator, \(\mathcal {S}\) acts as honest parties \(P_{b+1}\) and \(P_{b+2}\) and receives a pair of DPF keys from \(\mathcal {A}\). \(\mathcal {S}\) checks the keys and aborts if they are incorrect. If an honest party generates the keys, \(\mathcal {S}\) creates a pair of VDPF keys and samples a random share \(r_b \leftarrow \mathbb {Z}_{2^\ell }\), then sends \((k_b, r_b)\) to \(\mathcal {A}\). \(\mathcal {S}\) runs the VDPF verification protocol with \(\mathcal {A}\) and aborts if \(\mathcal {A}\) aborts in the verification. All other messages from honest parties to the corrupted one are randomly sampled by the simulator.
The above simulation is indistinguishable from real-world execution. If \(\mathcal {A}\) sends incorrect DPF keys, the real-world execution would abort due to VDPF check. In the ideal world, \(\mathcal {S}\) can directly check the keys, causing the ideal world to abort with indistinguishable probability. When the corrupted party is the DPF evaluator, \(\mathcal {S}\) honestly generates the DPF keys. If \(\mathcal {A}\) follows the VDPF key verification protocol, the check will pass; otherwise, it will abort. Thus, \(\mathcal {S}\) runs the check protocol with \(\mathcal {A}\) as in the real-world protocol, always aborting with indistinguishable probability.
Simulating Online Phase. If the protocol does not abort after the simulation stage, all DPF keys generated by \(\mathcal {A}\) in \(\mathcal {S}\) are correct. The only issue in the online phase is whether \(\mathcal {A}\) follows the protocol honestly and whether \(\mathcal {S}\) successfully extracts the error term. We assume that the shared messages \(\langle l \rangle \), \(\langle r \rangle \) and conditions \((\langle f \rangle , \langle t \rangle )\) are correctly shared/simulated initially, meaning the honest parties hold correct and consistent RSS shares.
For all local computations, \(\mathcal {S}\) is easy to simulate. \(\mathcal {S}\) only needs to simulate interactions between honest and corrupted parties and abort with indistinguishable probability. Only a few parts in the selection phase need interaction. First, securely reconstructing \(\delta \): since \(\langle \delta \rangle = \langle f \rangle - \langle t \rangle + \langle \alpha \rangle \) and \(\langle f \rangle \), \(\langle t \rangle \), and \(\langle \alpha \rangle \) are correct RSS sharings, \(\langle \delta \rangle \) is consistent. \(\mathcal {S}\) checks if \(\mathcal {A}\) sends the correct value using \(P_{b+2}\)’s share: 1) if \(\mathcal {A}\) sends an incorrect share, \(\mathcal {S}\) aborts; 2) if correct, \(\mathcal {S}\) samples a random \(\delta \in \mathbb {Z}_{2^\ell }\), computes shares for \(P_{b+1}\) and \(P_{b+2}\) from \(\delta \) and \(P_b\)’s RSS shares, and sends them to \(\mathcal {A}\). The parties then open \(\delta \) to \(\mathcal {A}\). Second, from \(\mathcal {F}_{\textsf {B2A}}\), which uses \(\mathcal {F}^{[\![ \cdot ]\!]}_{\textsf {mul}}\) with security proved in [28]. Lastly, re-sharing \([\![ \text {next} ]\!]\) from \((\begin{array}{c} 3 \\ 3 \end{array})\)-sharing to RSS-sharing. \(\mathcal {A}\) can add an error, and \(\mathcal {S}\) extracts it: \(\mathcal {S}\) gets \(next_i^*\) from the corrupted party to an honest party and updates \(P_{b+1}\)’s share. \(\mathcal {S}\) computes the correct \(next_i\) (knowing all shares to compute \(z_i\)), then computes \(res \leftarrow next_i - next_i^*\) and sends res to \(\mathcal {F}_{\textsf {cos}}\), completing the simulation.
Note that in simulating the open step of \(\delta \), \(\delta \) uses shares of honest parties, either simulated or computed from local data. These shares match those of the corrupted party, making the simulation indistinguishable from real execution. For the re-sharing phase, the simulation randomly samples \(P_{b+2}\)’s share and sends it to \(\mathcal {A}\). In the real protocol execution, this is generated by a PRF \(F\), so the simulation remains computationally indistinguishable due to the PRF’s security. Overall, the simulation is indistinguishable from real execution.
1.3 A.3 Security Proof of the FSSTree Evaluation Protocols \(\varPi _\textsf {FSSTree}\)
Theorem 2
\(\varPi _{\textsf {FSSTree}}\) securely compute \(\mathcal {F}_{\textsf {FSSTree}}\) in the \(\{\mathcal {F}_{\textsf {recon}}, \mathcal {F}_{\textsf {os}}, \mathcal {F}_{\textsf {coin}}, \mathcal {F}_{\textsf {rand}},\) \(\mathcal {F}_{\textsf {open}}, \mathcal {F}_{\textsf {cos}}, \mathcal {F}^{\langle \cdot \rangle }_{\textsf {mul}}, \mathcal {F}_{\textsf {CheckZero}}\}\)-hybrid model in the presence of a malicious adversary in the three-party honest-majority setting.
The proof of Theorem 2 is similar to the \(\varPi _\textsf {pdte}\) protocol in Mostree. Due to space limitations, please refer to the full version [12] for details.
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Fu, J., Cheng, K., Xia, Y., Song, A., Li, Q., Shen, Y. (2024). Private Decision Tree Evaluation with Malicious Security via Function Secret Sharing. In: Garcia-Alfaro, J., Kozik, R., Choraś, M., Katsikas, S. (eds) Computer Security – ESORICS 2024. ESORICS 2024. Lecture Notes in Computer Science, vol 14983. Springer, Cham. https://doi.org/10.1007/978-3-031-70890-9_16
Download citation
DOI: https://doi.org/10.1007/978-3-031-70890-9_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-70889-3
Online ISBN: 978-3-031-70890-9
eBook Packages: Computer ScienceComputer Science (R0)