本科毕业设计项目 —— 首次独立完成的完整科研工程实现
本项目实现了基于CKKS全同态加密的隐私保护K近邻（KNN）分类算法。在典型的"数据不出域"场景中，查询方可以在不泄露查询内容、数据方不泄露原始数据、计算方不获取任何明文信息的前提下，完成KNN分类任务。
- 四方安全分离架构：查询方、数据方、计算方、解密方各司其职，无任何一方能同时获取查询向量与原始数据集
- 密态Top-K筛选：基于改进的Minimax复合多项式近似
sgn(x)函数，在密文域内完成距离排序与Top-K邻居提取 - 128-bit经典安全性：参数通过 HomomorphicEncryption.org 2023 标准验证
- 密文结果100%匹配明文基线：密态计算输出的Top-10邻居集合与明文KNN完全一致
| 角色 | 职责 | 可获取信息 |
|---|---|---|
| 查询方 | 生成CKKS密钥对，加密查询向量 | 仅拥有私钥和查询明文 |
| 数据方 | 使用公钥加密本地数据集 | 仅拥有原始数据和公钥 |
| 计算方 | 在密文域执行KNN全部运算 | 无任何明文信息 |
| 解密方 | 使用私钥解密Top-K结果 | 仅获得最终邻居索引 |
- 同态加密库: OpenFHE (CKKS方案，复数打包编码)
- 编程语言: C++17 (核心运算) + Python3 (数据预处理与参数生成)
- 构建工具: CMake 3.13+
- 并行加速: OpenMP
- 数学基础: Chebyshev多项式、Minimax逼近理论
CKKS-KNN/
├── src/ # C++ 源代码
│ ├── data_owner.cpp # 数据方：加密数据集
│ ├── query_owner.cpp # 查询方：生成密钥、加密查询
│ ├── compute_all.cpp # 计算方：密态KNN全流程
│ ├── decrypt_result.cpp # 解密方：解密Top-K结果
│ ├── verify_index.cpp # 验证：密文结果 vs 明文基线
│ ├── plaintext_knn.cpp # 明文基准KNN（对照实验）
│ ├── sgn_utils.h # sgn近似多项式系数与区间常量
│ └── paths.h # 项目路径常量（统一配置）
│
├── tests/
│ └── security_test.cpp # 128-bit安全性参数验证
│
├── data/ # 数据集（Wine，128条×16维）
│ ├── data.txt # 训练数据
│ ├── labels.txt # 类别标签
│ └── query.txt # 查询向量
│
├── keys/ # 密钥输出目录（空，运行时生成）
├── ciphertexts/ # 密文输出目录（空，运行时生成）
├── gen_data.py # 数据预处理脚本（Min-Max缩放、零填充）
├── sgn_approximation.py # 两阶段Minimax sgn近似参数生成
├── run.sh # 密态KNN一键运行脚本
├── run_security_test.sh # 安全性测试一键运行脚本
├── CMakeLists.txt # CMake构建配置
└── README.md # 本文件
注:
build/目录存放 CMake 编译产物（已被.gitignore排除）；keys/和ciphertexts/目录已预置.gitkeep保留空结构，运行时产生的.bin大文件被.gitignore忽略，不会提交到仓库。
- Linux (WSL2 / Ubuntu 20.04+)
- GCC 9+ 或 Clang 10+
- CMake 3.13+
- Python 3.8+
# 克隆 OpenFHE
git clone https://github.com/openfheorg/openfhe-development.git
cd openfhe-development
mkdir build && cd build
cmake .. -DCMAKE_INSTALL_PREFIX=/usr/local
make -j$(nproc)
sudo make install
sudo ldconfigpip install numpy scikit-learnpython gen_data.py输出示例：
=== Wine 明文基线（数据集固定，查询点可变）===
数据集大小: 128 (每类数量: 0:43, 1:46, 2:39)
查询点来自剩余 50 条中的索引 1 (类别 0)
查询点真实类别: 0
Top-10 索引: [2, 18, 5, 10, 22, 30, 35, 34, 11, 12]
KNN 预测类别: 0
mkdir build && cd build
cmake ..
make -j$(nproc)将生成以下可执行文件：
data_owner— 数据方加密query_owner— 查询方加密compute_all— 计算方密态运算decrypt_result— 解密结果verify_index— 结果验证plaintext_knn— 明文基准security_test— 安全性测试
一键运行（推荐）：
./run.sh # 自动进入 build/ 并依次执行4个步骤或手动分步运行：
cd build
./query_owner # Step 1: 生成密钥，加密查询
./data_owner # Step 2: 加密数据集
./compute_all # Step 3: 密态计算（距离→排名→Top-K）
./decrypt_result # Step 4: 解密Top-K结果
./verify_index # Step 5: 验证密文结果与明文一致性./run_security_test.sh在 AMD Ryzen 9 7945HX (16C/32T) 上：
| 步骤 | 耗时 | 说明 |
|---|---|---|
| 密钥生成 | ~2s | 深度33，环维度 N=65536 |
| 数据集加密 | ~5s | 128条×16维，复数打包 |
| 密态计算 | ~25s | 欧氏距离 → Index排名 → Top-K筛选 |
| 结果解密 | ~1s | 提取Top-10邻居索引 |
| 总计 | ~34s | 端到端全流程 |
Top-K 邻居样本ID集合: 2, 5, 10, 11, 12, 18, 22, 30, 34, 35
[验证] 明文基准 Top-10: 2, 18, 5, 10, 22, 30, 35, 34, 11, 12
[✓ 通过] 包含全部 10 个正确邻居
╔══════════════════════════════════════════════════════════════════════╗
║ CKKS-KNN 128-bit Classical Security Test ║
╚══════════════════════════════════════════════════════════════════════╝
Ring Dimension (N) = 65536
Multiplicative Depth = 33
Scaling Mod Size = 30 bits
Total Modulus log2(q) = 1071 bits
Secret Key Distribution = UNIFORM_TERNARY
128-bit Classic max log2(q) = 1762 bits
Actual: 1071 <= 1762
Result: PASS ✓
Margin: 39.22% margin
✓ 该项目满足 128-bit 经典安全性 (HEStd_128_classic)
| 参数 | 值 | 说明 |
|---|---|---|
| Ring Dimension (N) | 65536 | 决定安全性和槽位数 |
| Slot Count | 32768 | 单密文可打包复数槽位数 |
| Multiplicative Depth | 33 | 支持33层乘法深度 |
| Scaling Mod Size | 30 bits | CKKS缩放模数 |
| Batch Size | 16384 | 批处理大小 |
| Top-K | 10 | 选取最近邻数量 |
| Dataset | Wine | 128条样本，16维特征 |
本项目解决了同态加密中无法在密文域比较大小的难题，核心思路：
- 密态欧氏距离计算：利用SIMD批量打包，单次密文运算计算查询点与全部128条样本的欧氏距离
- Index排名：通过密文旋转与累加，将距离值转换为排名Index
- Top-K筛选：基于改进的 两阶段Minimax复合多项式 近似
sgn(x)，在密文域内构造Top-K指示函数，精确筛选前K个最近邻
详见 sgn_approximation.py 中的算法实现与参数生成逻辑。
- [CKKS17] Cheon, J. H., et al. "Homomorphic encryption for arithmetic of approximate numbers." ASIACRYPT 2017.
- [OpenFHE] Al Badawi, A., et al. "OpenFHE: Open-source fully homomorphic encryption library." WAHC 2022.
- [HE Standard] HomomorphicEncryption.org. "Homomorphic Encryption Standard." 2018.
- GitHub: @JYH1878
- 项目: 本科毕业设计 —— 隐私保护机器学习方向
本项目仅供学术交流与毕业设计展示使用。