累积全损但一陷门函数的构造与分析

# 累积全损但一陷门函数的构造与分析 ## 1 引言 在密码学领域，累积全损但一陷门函数（CALBO - TDFs）是一种重要的工具。对于函数 \(F_{ek}(\cdot, \text{tag})\)，除了一个特殊的单射标签 \(\text{tag}^*\) 外，对于任何标签 \(\text{tag}\) 它都是有损的。对于 \(\text{tag}^*\)，可以使用与 \(ek\) 相关的陷门 \(td\) 进行求逆。此外，这种有损性具有累积性，即对于有损标签 \(\text{tag}_i \neq \text{tag}^*\) 的多次评估 \(F_{ek}(x, \text{tag}_i)\) 总是泄露关于 \(x\) 的相同信息。最后，评估密钥需要在计算上隐藏特殊的单射标签，并且使用不同单射标签生成的评估密钥在计算上是不可区分的。 之前的工作中，CALBO - TDFs 的设计较为复杂，已知的实例依赖于不可区分混淆（iO）以及 DDH 或 LWE 假设。而本文提出了两种仅基于标准假设的 CALBO - TDFs 构造方法，避免了使用不可区分混淆。 ### 1.1 研究贡献 - **基于 LWE 假设的构造**：依赖于具有亚指数近似因子的 LWE 假设，将 LWE 问题归约为最坏情况的格问题。 - **基于 DCR 假设的构造**：依赖于 Paillier 的复合剩余假设（DCR）。 ### 1.2 技术概述 #### 基于 LWE 的宽松 CALBO - TDFs CALBOs（无陷门）可以被视为选择性安全的不可预测函数。我们对 Libert、Stehlé 和 Titiu 基于 LWE 的 PRF 进行升级。LWE 函数在适当的参数选择下可以提供有损函数甚至有损陷门函数。 PRF 将输入 \(x\) 映射到 \(\lfloor s^{\top}A(x) \rfloor_p\)，其中 \(s \in \mathbb{Z}^n\) 是秘密密钥，\(A(x) \in \mathbb{Z}_q^{n \times m}\) 是从公共矩阵派生的输入相关矩阵。通过选择足够大的 \(q/p\) 比率，可以证明所有评估查询揭示关于秘密密钥 \(s\) 的相同信息，满足 CALBO 设置中的累积有损性。 我们对该函数进行了两项修改： 1. 只需要选择性安全版本的 PRF，因此移除了可接受的哈希函数，直接计算 \(A(x)\)。 2. 扩展标签相关矩阵 \(A(x)\) 以确保在单射模式下的可逆性。 具体构造如下： - **设置算法**：给定单射标签 \(\text{tag}^* \in \{0, 1\}^t\)，生成有损矩阵 \(A = D^{\top} \cdot B + E \in \mathbb{Z}_q^{n \times m}\)，并通过一组 GSW 密文将 \((A, B)\) 嵌入评估密钥 \(ek\) 中。陷门 \(tk\) 包含 \(\{R_{i,b}\}_{i \in [t], b \in \{0, 1\}}\)。 - **评估算法**：对于输入 \(x\) 和标签 \(\text{tag}\)，计算 GSW 密文的乘积得到 \(A(\text{tag})\)，最终输出 \(\lfloor x^{\top} \cdot [A | A(\text{tag})] \rfloor_p\)。 在有损模式下，由于舍入操作引入的误差，累积有损性仅对固定输入成立。但这种宽松的累积有损性在应用中不会产生问题。 #### 基于 DCR 的 CALBO - TDFs 基于 Damgård - Jurik 同态加密方案，通过组合 Freeman 等人基于 DCR 的有损陷门置换的多个实例来构造。 - **评估密钥 \(ek\)**：包含 \((N, \zeta)\) 和 Damgård - Jurik 密文 \(g_{i,b}\)。 - **陷门 \(tk\)**：由 Damgård - Jurik 解密密钥组成。 对于输入 \(x \in \mathbb{Z}_{N^{\zeta + 1}}\) 和标签 \(\text{tag}\)，通过迭代计算得到输出 \(x_t\)。 在单射模式下（\(\text{tag} = \text{tag}^*\)），可以使用 \(tk\) 恢复输入 \(x\)。在有损模式下，当 \(\text{tag} \neq \text{tag}^*\) 时，函数会丢失关于输入的信息。 ### 1.3 相关工作 - **无陷门的 CALBO 函数**：Dodis 等人考虑了无陷门的累积全损但一（CALBO）函数，用于从依赖提取器的源中提取随机性。他们的构造在单射模式下不可逆。 - **目标有损函数**：Quach 等人引入了目标有损函数（TLFs）及其变体，这些函数在 Minicrypt 中可以实现。 - **有损代数滤波器（LAFs）**：用于构造具有循环选择密文安全性的公钥加密方案，与 CALBO 有相似的功能，但允许任意数量的单射和有损标签，且不支持单射标签上的高效求逆。 ## 2 背景知识 ### 2.1 符号定义 - \([n]\) 表示集合 \(\{1, 2, \ldots, n\}\)。 - \(\mathbb{Z}_q\) 表示模 \(q\) 的整数环。 - 对于 \(2 \leq p < q\) 和 \(x \in \mathbb{Z}_q\)，定义 \(\lfloor x \rfloor_p := \lfloor (p/q) \cdot x \rfloor \in \mathbb{Z}_p\)。 ### 2.2 累积全损但一陷门函数的定义 #### 定义 1（CALBO - TDF） 设 \(\lambda \in \mathbb{N}\) 是安全参数，\(\ell, \alpha : \mathbb{N} \to \mathbb{N}\) 是函数，\(T = \{T_{\lambda}\}_{\lambda \in \mathbb{N}}\) 是标签集合的族。一个关于标签族 \(T\) 的 \((\ell, \alpha)\) - 累积全损但一陷门函数族（CALBO - TDF）是一个三元组算法 \((\text{Sample}, \text{Eval}, \text{Invert})\)，其中第一个是概率性的，后两个是确定性的： - **Sample(\(1^{\lambda}, \text{tag}^*\))**：输入 \(1^{\lambda}\) 和 \(\text{tag}^* \in T_{\lambda}\)，采样并输出 \((ek, tk)\)。 - **Eval(\(ek, \text{tag}, x\))**：输入 \(x \in \{0, 1\}^{\ell(\lambda)}\)、评估密钥 \(ek\) 和标签 \(\text{tag}\)，输出某个图像集合 \(R\) 中的元素