用全同态加密实现外包特征选择，保护数据隐私同时提升效率
Outsourced Privacy-Preserving Feature Selection Based on Fully Homomorphic Encryption
- 基于全同态加密设计外包特征选择方案，支持不可信第三方计算
- 时间复杂度从O(kn²)优化至O(kn log³ n)，空间复杂度降至O(kn)
- 适合需要隐私保护的多方数据协作场景，如医疗、金融领域
特征选择是从训练数据的特征集中提取有意义子集的技术。当数据规模较大时，合理特征选择可去除冗余特征，提升模型泛化能力、加速训练过程并增强模型可解释性。本文提出一种隐私保护的特征选择计算模型。当数据所有者与分析者为同一方时，无需隐藏私密信息；但当双方分离或存在多个所有者时，需构建隐私保护框架。尽管已有多种私有特征选择算法，但均需两方及以上计算且无法在完全不可信环境中保证安全。为此，我们首次提出基于全同态加密的外包特征选择算法。相比先前的两方算法，本方法将时间复杂度从O(kn²)降低至O(kn log³ n)，空间复杂度从O(kn²)降至O(kn)，其中k为特征数，n为样本数。我们实现了该算法，并与朴素方法进行对比实验，结果表明即使在小数据集上也具有显著效率优势。
原文摘要 · Abstract (English)
Feature selection is a technique that extracts a meaningful subset from a set of features in training data. When the training data is large-scale, appropriate feature selection enables the removal of redundant features, which can improve generalization performance, accelerate the training process, and enhance the interpretability of the model. This study proposes a privacy-preserving computation model for feature selection. Generally, when the data owner and analyst are the same, there is no need to conceal the private information. However, when they are different parties or when multiple owners exist, an appropriate privacy-preserving framework is required. Although various private feature selection algorithms, they all require two or more computing parties and do not guarantee security in environments where no external party can be fully trusted. To address this issue, we propose the first outsourcing algorithm for feature selection using fully homomorphic encryption. Compared to a prior two-party algorithm, our result improves the time and space complexity O(kn^2) to O(kn log^3 n) and O(kn), where k and n denote the number of features and data samples, respectively. We also implemented the proposed algorithm and conducted comparative experiments with the naive one. The experimental result shows the efficiency of our method even with small datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。