•2025年09月
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）