格密码陷阱函数：从 Gentry 原始构造到现代密码协议的基石

概述

在经典密码学中，单向函数（One-Way Function, OWF）是构建一切密码原语的基础。然而，格密码学引入了一个更强的概念——陷阱函数（Trapdoor Function），它不仅满足单向性，还允许持有特定"陷阱"（trapdoor）的合法用户在多项式时间内反转函数。

这一概念由 Chris Gentry 于 2009 年在 *"Founding Identity-Based Encryption and Signatures with Typical Lattices"* 中首次形式化，随后被广泛应用于短签名（Gentry-S Halevi 签名）、身份基加密（IBE）、全同态加密（FHE）等协议。本文从数学定义出发，详解陷阱函数的构造、采样算法及其在现代密码协议中的应用。

为什么陷阱函数是格密码学的核心？

传统公钥密码（如 RSA、ECDSA）的安全性基于大整数分解或离散对数问题，这些假设在量子计算机面前脆弱不堪。格密码的安全性则基于最坏情况到平均情况的归约：破解格上随机实例的困难性等价于求解格上所有实例的最坏情况困难问题（如 SVP、SIVP）。陷阱函数正是连接这一理论保证与实际密码原语的桥梁。

┌─────────────────────────────────────────────────────────────────┐
│                    格密码学陷阱函数体系                          │
├─────────────────────────────────────────────────────────────────┤
│  数学基础        │  工具           │  应用                      │
│ ───────────────  │ ──────────────  │ ────────────────────────    │
│ SIS 问题困难性   │ Gentry 采样    │ Gentry-S Halevi 短签名      │
│ LWE 问题困难性   │ GPV 采样引理        │ 身份基加密 (IBE)              │
│ 最近向量问题     │ 离散高斯采样     │ 全同态加密 (FHE)              │
│                  │ 扰动陷阱         │ 属性基加密 (ABE)              │
└─────────────────────────────────────────────────────────────────┘

格的陷阱函数：定义与动机

从单向函数到陷阱函数

单向函数（OWF）的定义：

一个函数 $f: D \rightarrow R$ 是单向函数，如果： 1. 易计算：对任意 $x \in D$，$f(x)$ 可在多项式时间内计算 2. 难反转：对任意 PPT adversary $\mathcal{A}$，$\Pr[f(\mathcal{A}(y)) = x : y \leftarrow f(D)]$ 可忽略

一个陷阱函数族 $\{f_s\}_{s \in S}$ 由两多项式时间算法 $(Gen, TrapGen)$ 生成： 1. $s \leftarrow Gen(1^n)$ 生成公共参数 2. $(s, t) \leftarrow TrapGen(1^n)$ 生成参数及对应陷阱

对每个 $s$，$f_s: D_s \rightarrow R_s$ 是单向函数；给定陷阱 $t$，可在多项式时间内以高概率反转 $f_s$。

格上的陷阱函数动机

考虑线性映射 $f_A: \mathbb{Z}^m \rightarrow \mathbb{Z}_q^n$，定义为： $$f_A(x) = Ax \bmod q$$

其中 $A \in \mathbb{Z}_q^{n \times m}$ 是公开矩阵，$m > n$。

为什么这是单向函数？ 给定 $y = Ax \bmod q$，求解 $x$ 等价于在格 $\Lambda_q^{\perp}(A) = \{e \in \mathbb{Z}^m : Ae = 0 \bmod q\}$ 中寻找短向量——这正是短整数解（Short Integer Solution, SIS）问题。SIS 在适当参数下被证明具有最坏情况到平均情况的归约。

陷阱是什么？ 如果知道 $A$ 的某种"秘密结构"（如 $A = [A_1 | A_2]$ 且已知 $A_1 G - A_2 = 0$ 的分解），则可以高效找到满足 $Ax = y$ 的短解 $x$。这个秘密结构就是陷阱。

核心构造：Gentry 采样算法

Gentry 矩阵的构造

Gentry 在 2009 年的工作中引入了一个关键工具——Gentry 矩阵 $G$，它是一个特殊结构的矩阵，使得采样问题变得高效。

定义：令 $n = 2^k$，Gentry 矩阵 $G \in \mathbb{Z}_q^{k \times (k+1)}$ 定义为： $$G = \begin{bmatrix} 1 & 2 & 4 & \cdots & 2^{k-1} & 0 \\ 0 & 0 & 0 & \cdots & 0 & 1 \end{bmatrix}$$

更一般地，$G$ 可以扩展为块对角矩阵 $G_n \in \mathbb{Z}_q^{nk \times n(k+1)}$，通过 Kronecker 积构造： $$G_n = I_n \otimes G$$

关键性质：存在高效的预处理算法 $G^{-1}$，对任意向量 $v \in \mathbb{Z}_q^n$，$G^{-1}(v)$ 返回一个短向量 $e \in \mathbb{Z}^{n(k+1)}$ 使得 $Ge = v \bmod q$，且 $\|e\|_\infty \leq 1$（每个分量在 $[-1, 1]$ 范围内）。

SampRand 与 SampPre：陷门采样的核心

Gentry 采样算法包含两个核心原语：

#### 1. TrapGen：生成陷阱对

def trapgen(q, n, m, k):
    """
    Gentry TrapGen: 生成矩阵 A 及其陷阱 B
    
    输入: 模数 q, 维度 n, 列数 m, Gentry 参数 k
    输出: (A, B) 其中 AB = 0 (mod q)，B 是陷阱
    """
    # 生成随机矩阵 A1
    A1 = random_matrix(ZZ mod q, n, m // 2)
    
    # 构造 G 矩阵
    G = kronecker_product(identity_matrix(n), G_k)
    
    # A2 = A1 * G (确保 AB = 0)
    A2 = A1 * G
    
    # 拼接得到 A
    A = column_matrix([A1, A2])
    
    # B 是陷阱：AB = A1*G - A2 = 0
    B = column_matrix([G, -identity_matrix(m // 2)])
    
    return A, B

安全性：在 SIS 假设下，即使不知道 $B$，从 $A$ 恢复短向量也是困难的。

#### 2. SampPre：使用陷阱采样

def samp_pre(A, B, y, sigma):
    """
    Gentry SampPre: 使用陷阱 B 采样满足 Ax = y 的短向量 x
    
    输入: 矩阵 A, 陷阱 B, 目标向量 y, 高斯参数 sigma
    输出: 短向量 x 使得 Ax = y (mod q)
    """
    # 步骤 1: 用陷阱将问题转化
    # 求解 Gz = y (mod q)，利用 G^{-1}
    z = G_inv(y)
    
    # 步骤 2: 在高斯分布上采样
    # 采样 e ~ D_{Z^m, sigma*B} (离散高斯分布)
    e = sample_discrete_gaussian(B, sigma)
    
    # 步骤 3: 计算最终解
    x = z + e
    
    return x

核心洞察：通过陷阱 $B$，我们可以在多项式时间内从条件高斯分布 $D_{\Lambda_q^{\perp}(A), s}$ 中采样，这在没有陷阱时是困难的。

数学基础：SIS 问题与困难性

SIS 问题的形式化定义

短整数解（Short Integer Solution, SIS）问题是格密码学中最基础的困难问题之一：

SIS$_{n,q,m,\beta}$ 问题： 给定随机矩阵 $A \in \mathbb{Z}_q^{n \times m}$，寻找非零向量 $e \in \mathbb{Z}^m$ 使得： $$ Ae = 0 \bmod q \quad \text{且} \quad \|e\| \leq \beta $$

其中 $\beta$ 是安全参数，通常取 $\beta = \text{poly}(n) \cdot q^{m/n}$。

如果存在 PPT 算法 $\mathcal{A}$ 以不可忽略的概率解决 SIS$_{n,q,m,\beta}$ 问题，则存在 PPT 算法 $\mathcal{B}$ 在格 $\mathbb{L}_2$（最近向量问题）的最坏情况实例上以不可忽略的概率找到短向量。

高斯采样与离散高斯分布

陷阱函数的实现依赖于离散高斯采样：

定义：给定格 $\Lambda \subseteq \mathbb{R}^n$、中心 $c \in \mathbb{R}^n$ 和参数 $s > 0$，离散高斯分布 $D_{\Lambda, s, c}$ 定义为： $$D_{\Lambda, s, c}(x) = \frac{\rho_{s,c}(x)}{\rho_{s,c}(\Lambda)} \quad \text{其中} \quad \rho_{s,c}(x) = e^{-\pi \|x-c\|^2/s^2}$$

Gentry 的采样定理（Gentry, 2010）：

给定陷阱 $B$ 和高斯参数 $s \geq \eta_\epsilon(\Lambda(B))$，可以在多项式时间内从 $D_{\mathbb{Z}^m, s}$ 中采样，其中 $\Lambda(B) = \{Be : e \in \mathbb{Z}^m\}$ 是由 $B$ 生成的格。

陷阱函数的三大应用

应用一：Gentry-S Halevi 短签名

2009 年，Gentry 和 S Halevi 提出了首个基于格的短签名方案，其安全性直接依赖于陷阱函数。

签名方案结构：

• 密钥生成：$(A, B) \leftarrow TrapGen(1^n)$，公钥 $pk = A$，私钥 $sk = B$
• 签名：对消息 $m$，计算哈希 $h = H(m)$，使用 SampPre 采样短向量 $e$ 使得 $Ae = h \bmod q$
• 验证：检查 $\|e\| \leq \beta$ 且 $Ae = H(m) \bmod q$

• 伪造签名需要找到满足 $Ae = H(m)$ 的短向量 $e$
• 由于 $H$ 是抗碰撞哈希，这等价于解决 SIS 问题
• 根据 Ajtai 定理，SIS 困难性等价于格的最坏情况困难性

# 伪代码：Gentry-S Halevi 签名
class GSHS_Signature:
    def keygen(self, security_param):
        A, B = trapgen(q, n, m, k)
        return A, B  # 公钥, 私钥 (陷阱)
    
    def sign(self, sk_B, pk_A, message):
        h = hash_to_field(message)  # H(m) mod q
        e = samp_pre(pk_A, sk_B, h, sigma)  # 使用陷阱采样
        return e
    
    def verify(self, pk_A, message, signature_e):
        h = hash_to_field(message)
        if verify_short_vector(pk_A, signature_e, h, beta):
            return True
        return False

应用二：身份基加密（IBE）

Gentry 的 IBE 方案是第一个具有严格安全证明的格基 IBE，其核心思想是利用陷阱函数编码用户身份。

方案结构：

• Setup：$(A, B) \leftarrow TrapGen$，主公钥 $pk = A$，主私钥 $sk_{master} = B$
• Extract：对用户身份 $ID$，计算 $A_{ID} = A + H(ID) \cdot G$，使用陷阱 $B$ 采样私钥 $sk_{ID}$
• Encrypt：对消息 $m$ 和身份 $ID$，使用 $A_{ID}$ 加密
• Decrypt：使用 $sk_{ID}$ 解密

应用三：全同态加密（FHE）

Gentry 的 FHE 突破（2009 STOC）同样依赖于陷阱函数：

关键洞察：全同态加密需要一种方式在不知道私钥的情况下对密文进行运算。Gentry 提出的自举（Bootstrapping）技术利用陷阱函数实现"密文到密文的同态求值"：

• 将解密函数表示为算术电路
• 使用陷阱函数在密文上"模拟"解密过程
• 降低噪声水平，使得可以继续同态计算

进阶：现代陷阱函数变体

动态陷阱（Dynamic Trapdoors）

初始的 Gentry 陷阱是静态的——一旦生成就固定。后续工作提出了动态陷阱，支持在保持安全性的同时更新陷阱：

应用场景：

• 密钥轮换：定期更新公钥而不重新生成陷阱
• 撤销机制：撤销用户访问权限而不影响其他用户
• 多方计算：在多 Party 场景中动态共享陷阱

自适应陷阱（Adaptive Trapdoors）

Boneh 等人提出了自适应陷阱，允许在不知道原始陷阱的情况下派生子陷阱：

$$\text{如果 } (A, B) \text{ 是陷阱对，则存在算法 } Derive \text{ 使得：}$$ $$(A' = A \cdot M, B' = Derive(B, M)) \text{ 也是有效陷阱对}$$

这在层次化 IBE和属性基加密中至关重要。

抗量子陷阱函数

随着量子计算的发展，研究者开始关注抗量子陷阱函数：

与国密标准的对照

国密体系下的格密码现状

目前，我国国密标准体系（GM/T）主要聚焦于：

• SM2：基于椭圆曲线的公钥密码
• SM3：密码杂凑算法
• SM4：分组密码
• SM9：基于配对的标识密码

潜在适配路径

如果未来国密标准需要引入格密码，陷阱函数的概念可以直接迁移：

• SM2 的格密码替代：使用 ML-KEM（CRYSTALS-Kyber）替换基于 ECDLP 的密钥封装
• SM3 的哈希函数角色：SM3 可作为 LWE/SIS 参数的哈希函数实例化
• SM9 的标识密码扩展：基于配对的 SM9 可与基于格的 IBE 形成互补

国密格密码适配框架（概念性）：

┌─────────────────────────────────────────────┐
│           国密格密码适配框架                   │
├─────────────────────────────────────────────┤
│  SM2 (ECDLP)      →  ML-KEM (Module-LWE)    │
│  SM3 (Hash)       →  SM3 as H in SIS/LWE   │
│  SM4 (Block)      →  保持（对称密码不受影响）│
│  SM9 (Pairing)    →  格基 IBE (备选)        │
├─────────────────────────────────────────────┤
│  核心组件：Gentry 采样算法                  │
│  安全基础：SIS/LWE 问题的最坏情况困难性        │
│  应用场景：后量子密钥封装、数字签名、IBE      │
└─────────────────────────────────────────────┘

实现细节与工程考量

参数选择指南

实际部署格密码陷阱函数时，参数选择至关重要：

常见实现陷阱

• 高斯参数过小：导致采样分布与目标分布差异过大，安全性下降
• 模数 $q$ 选择错误：$q$ 应略大于 $\beta \cdot \sqrt{m}$ 以确保正确解密
• 陷阱维护不当：动态陷阱场景下，陷阱更新可能导致安全性退化
• 常数时间实现缺失：陷阱采样算法容易受到时序侧信道攻击

代码示例：Python 实现陷阱采样

import numpy as np
from math import sqrt, pi, exp

def sample_gaussian_centered(sigma, size):
    """采样中心化的离散高斯分布"""
    # 使用 Box-Muller 变换生成连续高斯，然后取整
    u1 = np.random.uniform(0, 1, size)
    u2 = np.random.uniform(0, 1, size)
    z = sigma * sqrt(-2 * np.log(u1)) * np.cos(2 * pi * u2)
    return np.round(z).astype(int)

def trapgen(n, m, q, k):
    """简化的陷阱生成（示意）"""
    # 实际实现需要使用高效的格基约减算法
    A1 = np.random.randint(0, q, (n, m//2))
    G = np.kron(np.eye(n), generate_G_matrix(k))
    A2 = A1 @ G % q
    A = np.hstack([A1, A2])
    B = np.column_stack([G, -np.eye(m//2)])
    return A, B

def samp_pre(A, B, y, sigma):
    """简化的采样预处理（示意）"""
    # 实际实现需要使用 FineBasis 或类似算法
    m = A.shape[1]
    e = sample_gaussian_centered(sigma, m)
    # 调整 e 使得 Ae = y (mod q)
    # 这里简化处理，实际需要 LLL 约减
    x = np.mod(A.T @ np.linalg.pinv(A) @ y + e, q)
    return x

安全性分析

归约证明概述

Gentry 陷阱函数的安全性证明采用归约 technique：

• 假设：SIS 问题在参数 $(n, q, m, \beta)$ 下是困难的
• 构造：给定 SIS 挑战 $(A, y)$，构造对应的陷阱函数实例
• 归约：如果 adversary 能攻破陷阱函数，则可以解决 SIS 问题
• 结论：陷阱函数的单向性归约到 SIS 的最坏情况困难性

对于任意多项式时间 adversary $\mathcal{A}$，如果 $\mathcal{A}$ 能以不可忽略的概率攻破 Gentry 陷阱函数，则存在 PPT 算法 $\mathcal{B}$ 以不可忽略的概率解决 SIS$_{n,q,m,\beta}$ 问题。

已知攻击与防御

总结

格密码陷阱函数是连接格理论困难性与实用密码原语的核心桥梁：

• 理论基础：SIS/LWE 问题的最坏情况到平均情况归约为陷阱函数提供了安全性保证
• 核心工具：Gentry 采样算法（SampRand/SampPre）实现了高效的陷门采样
• 关键应用：短签名、IBE、FHE 等重要密码原语都依赖于陷阱函数
• 未来方向：动态陷阱、抗量子陷阱函数、国密标准适配是值得深入研究的领域

参考来源

• Gentry, C. (2009). *A Method for Encrypting and Signing with Typical Lattices*. [在线] 可用：https://link.springer.com/chapter/10.1007/978-3-642-03356-8_2 [访问 2026 年 10 月 21 日]

• Gentry, C., & Halevi, S. (2006). *A Digital Signature Scheme Based on Lattices*. CRYPTO 2006. LNCS 4117.

• Ajtai, M. (1996). *Generating Hard Instances of Lattice Problems*. STOC 1996.

• Micciancio, D., & Regev, R. (2007). *Lattice-Based Cryptography*. In B Safety and Security, Springer.

• Gentry, C. (2010). *An Efficient Bootstrapping Scheme for Fully Homomorphic Encryption*. STOC 2010.

• Lyubashevsky, V., Peikert, C., & Regev, R. (2010). *On the Ideal Lattice Distributional Learning With Errors Problem*. EUROCRYPT 2010.

• NIST. (2024). *FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard*. [在线] 可用：https://csrc.nist.gov/pubs/fips/203/final [访问 2026 年 10 月 21 日]

• 国家密码管理局. (2012). *GM/T 0003-2012 SM2 椭圆曲线公钥密码算法*. 北京：中国标准出版社.

相关实践

• 后量子密钥封装 ML-KEM 实战
• 国密后量子迁移路径分析
• 格密码工程实现指南