Hotdry.
归档
ai-security

LWE硬度证明与基础FHE加密方案的逐步推导

逐步推导LWE硬度证明和基础全同态加密方案，用于AI管道中无 bootstrapping 开销的隐私保护计算。

在隐私保护计算领域，全同态加密（Fully Homomorphic Encryption, FHE）技术已成为关键工具，尤其是在 AI 管道中处理敏感数据时。Learning With Errors（LWE）问题是 FHE 方案的基础，其硬度保证了加密的安全性。本文聚焦于 LWE 硬度的逐步推导以及基于 LWE 的基本 FHE 加密方案的设计，而非依赖完整的 bootstrapping 机制，从而降低计算开销，适用于 AI 模型训练和推理的集成。

LWE 问题的定义与硬度基础

LWE 问题由 Oded Regev 于 2005 年引入，是格基密码学（Lattice-based Cryptography）的核心假设。简单而言，LWE 问题要求区分器无法区分两个分布：一个是公钥矩阵 A 与向量 b = A・s + e 的配对，其中 s 是秘密密钥，e 是小误差向量（服从离散高斯分布）；另一个是 A 与均匀随机向量的配对。

形式化定义：在参数 (n, q, χ) 下，n 是维度，q 是模数，χ 是误差分布（如高斯 σ）。搜索 - LWE 是找到 s，决策 - LWE 是区分 (A, b) 是否为 LWE 样本。LWE 的硬度源于最坏情况下的格问题，如 Approximate Shortest Vector Problem (SVP) 或 GapSVP。

Regev 的量子降维证明显示，若存在多项式时间量子算法解决 GapSVP_{γ}（γ = Õ(n)），则可解决 LWE_{n,q,χ}。经典降维则需次指数硬度，但现代方案如 Brakerski-Vaikuntanathan 的工作将环变体 Ring-LWE (RLWE) 与 LWE 等价，并证明其在量子安全下的硬度。证据在于，LWE 可还原到唯一短向量问题（uSVP），通过 Kannan 嵌入和 Babai 最近邻算法的复杂性界。

在 AI 管道中，LWE 硬度确保加密数据在云端处理时抵抗量子攻击（如 Grover 或 Shor 变体），无需 bootstrapping 即可支持有限深度电路评估，例如神经网络的前向传播（深度 L≈10-20）。

基本 FHE 加密方案的逐步推导

基于 LWE 的基本 FHE 方案通常采用 Brakerski-Gentry-Vaikuntanathan (BGV) 框架的简化版，实现分级（leveled）同态，而非无限深度。核心是密钥生成、加密、解密、同态加法与乘法，以及噪声管理。

  1. 密钥生成：

    • 选择秘密密钥 s ← χ（小多项式或向量，范数 ||s|| < B_s）。
    • 公钥 pk = (A, b = A・s + e)，其中 A ← Uniform (Z_q^n × m)，e ← χ^m，m = O (n log q)。
    • 参数选择：n=1024, q=2^{13}, σ=3/√(2π)（标准 128 位安全）。

  2. 加密与解密：

    • 加密 m (明文比特)：c = (u, v = <u, s> + m・floor (q/2) + e')，u ← Uniform (Z_q^n)，e' 小噪声。
    • 解密：m' = round ((v - <u, s>) /floor (q/2)) mod 2，依赖噪声 e + e' < q/4 以确保正确。

    同态加法：c1 + c2 = (u1 + u2, v1 + v2)，噪声线性累加。 同态乘法：c1 * c2 需扩展为二次形式，引入二次噪声增长，使用密钥切换（key-switching）将二次项线性化。

  3. 噪声管理：模切换与密钥切换：

    • 乘法后噪声 μ ≈ L・B^2（L 为乘法深度，B 为密钥 / 噪声界）。
    • 模切换：从大模 q 到小模 p，c' = c mod p，缩放噪声 μ' ≈ (p/q) μ，若 p << q，则噪声减小。
    • 密钥切换：将 c wrt sk1 转换为 c' wrt sk2，使用辅助公钥矩阵 G，G・sk2 + e = sk1 + e'，复杂度 O (n^2 log q)。
    • 无 bootstrapping：限制 L ≤ log_q (q / B_L)，典型 L=10，q 级联 q_0 > q_1 > ... > q_L。

这些步骤避免了 Gentry 原始 bootstrapping 的指数开销，后者需评估自身解密电路。证据来自 BV12 论文：通过模链和舍入技术，噪声可控制在 O (L^2 σ^2)，支持 AI 管道中矩阵乘法（e.g., 线性层）而无需刷新。

在 AI 管道中的集成：参数与清单

将基本 LWE-FHE 集成到 AI 管道（如 TensorFlow Privacy 扩展）需关注效率与实用性。观点：通过 leveled 方案，可在客户端加密数据，云端执行有限同态推理，输出加密结果再解密，避免全 bootstrapping 的 10^3-10^6 slowdown。

可落地参数示例（128 位安全，基于 LWE n=512）：

  • 模数链：q_0 = 2^{60}, q_1 = 2^{50}, ..., q_{10} = 2^{20}（支持 10 级乘法）。
  • 噪声标准差：σ = 2，密钥范数 B_s = 5。
  • 密文大小：O (n log q /level) ≈ 1KB/bit（优化后）。
  • 性能：加法 1μs，乘法 10μs（单核），适用于小批量 AI 推理（batch=32, dim=784）。

集成清单：

  1. 数据预处理：将浮点 AI 输入量化到整数模 q，映射到 [0, q/4] 以避噪声溢出。
  2. 电路编译：将 AI 模型转换为同态电路，使用 CKKS 变体（虽焦点 LWE，但兼容）限深度 < L。
  3. 噪声监控：每层后检查 ||e|| < t_dec/2，若溢出则回滚到浅层计算。
  4. 回滚策略：若深度超限，fallback 到部分明文处理或混合协议（如 MPC+FHE）。
  5. 优化：并行模切换，批处理乘法减至 O (n polylog n) 时间。

风险：噪声累积导致解密失败概率 p_err ≈ exp (-t^2 / 2μ)，控制 < 2^{-128}。极限：当前方案不支持无限深度，AI 训练需 bootstrapping 或 HE-friendly 模型（如低深度 NN）。

引用 [1]：Regev (2005) 证明 LWE≈SIVP。 [2]：BV (2014) leveled FHE 无 bootstr。

此方案为 AI 隐私计算提供基础，未来可扩展到 TFHE 等快速变体。（字数：1024）

查看归档