💻 computer science

Information-Theoretic Distributed Point Functions with Shorter Keys

本文提出了一种在群 $\mathbb{Z}_p$ 上全新的、具有完美安全性的1-私有信息论分布式点函数（ITDPF），该方案通过利用基于近期私有信息检索技术的份额转换，实现了比现有方案渐近更短的密钥。

原作者： Hang Deng, Liang Feng Zhang

发布于 2026-04-28

📖 1 分钟阅读☕ 轻松阅读

原作者： Hang Deng, Liang Feng Zhang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你拥有一张秘密藏宝图，它指向巨大网格（不妨设想为一个拥有数百万个街区的城市）上确切的一个特定位置。你想将这张地图的副本分发给一群朋友，以便他们能够共同找出宝藏的位置。然而，你有一条严格的规定：任何小团体（例如任意两人或更少）仅通过比较他们的副本都无法推断出位置。他们必须结合所有的碎片才能解开谜题。

这就是分布式点函数（DPF）的核心问题。它是一种密码学工具，将一个“点函数”（即在除一个特殊点外的所有地方均为零的函数）拆分为多个“份额”（密钥）。

旧方法 vs. 新方法

旧方法（沉重的背包）：
此前实现安全分发（特别是“信息论”安全，即即使面对拥有无限算力的超级计算机也是安全的）的方法，要求朋友们背负非常沉重的背包。这些背包里装着解开谜题所需的“密钥”。随着城市（数据）变大，这些背包呈指数级增长，使得系统变得缓慢且不切实际。

新方法（轻便的挎包）：
本文介绍了一种新方法，能够制造轻便得多的挎包。作者邓航和张良峰构建了一个系统，其密钥比任何先前完美安全的方法都要显著更短（更小），尤其是在数据变得巨大的情况下。

他们是如何做到的：“秘密配方”

作者并非从零开始发明新的魔法咒语，而是使用了一个巧妙的配方（称为 LKZ 框架），将一种类型的秘密共享工具转化为另一种。

原料（PIR）：他们使用的秘密酱料是一种最先进的工具，称为私有信息检索（PIR）。将 PIR 想象成一种向图书管理员询问特定书籍的方式，而图书管理员不知道你要问的是哪本书。Ghasemi、Kopparty 和 Sudan 最近的突破使得这种“询问”过程变得极其高效。
转换（魔法戏法）：作者找到了如何将这种新 PIR 的“询问”机制转化为他们 DPF 所需的“密钥拆分”机制。
- 类比：想象旧的 PIR 就像是用一份复杂的、长达 10 页的表格向图书管理员询问书籍。而新的 PIR 使用一个微小的、仅 2 个单词的代码。作者找到了一种方法，将这个微小的 2 个单词代码转化为藏宝图的秘密密钥，同时确保密钥保持微小。

结果：完美安全、微小的密钥

本文声称构建了一个具有以下特性的系统：

完美安全：即使黑客拥有无限的计算能力，如果他们窃取了一些密钥，也无法得知任何关于秘密位置的信息。
高效：“密钥”（每个服务器持有的数据）是渐近更短的。用通俗的话说：随着数据量的增长，密钥的大小增长得比以前慢得多。
灵活：它适用于任何素数大小（一种特定类型的数学群），涵盖了广泛的实际需求。

局限（代价）

作者诚实地说明了权衡之处：

“单服务器”规则：目前，这种特定的构造仅保证一个服务器在与其他服务器合谋时无法得知秘密。如果你想防范两个或三个服务器合谋，系统的规模将呈爆炸式增长（需要指数级更多的服务器），这在目前效率太低而无法实用。
特定数学：它在特定类型的数学群（素数阶群）中效果最好，尽管作者建议未来可以将其扩展到更复杂的群。

总结

简而言之，这篇论文就像是一位工程师，找到了一种方法，将一座庞大、笨重的安全金库缩小为一个口袋大小的保险箱，同时没有损失任何强度。他们通过从另一个领域（私有信息检索）借用一种高效的“开锁”技术，并将其改编用于在服务器之间拆分秘密，从而实现了这一目标。其结果是一个在数学上坚不可摧且比任何先前系统都快得多的系统。

以下是 Hang Deng 和 Liang Feng Zhang 所著论文《具有更短密钥的信息论分布式点函数》的详细技术总结。

1. 问题陈述

本文探讨了**信息论分布式点函数（ITDPFs）**的构建。

定义： 一个 $(t, n)$ -ITDPF 允许将一个点函数 $f_{\alpha, \beta}(x)$ （该函数在输入 $\alpha$ 处输出 $\beta$ ，在其他地方输出 0）分割为 $n$ 个密钥。任意 $\le t$ 个服务器的子集对函数信息一无所知（完美安全），而所有 $n$ 个服务器评估值的总和则重构出函数值。
挑战： DPF 效率的主要衡量指标是密钥大小（秘密密钥的最大尺寸）。现有的针对输出群 $G = \mathbb{Z}_p$ $G = Z_{p}$ （其中 $p$ $p$ 为任意素数）的完美安全 ITDPF 存在密钥大小次优的问题。
- 先前的工作（如 Boyle 等人、Li 等人）实现的密钥大小指数涉及形如 $\nu_r(N) = (\log N)^{1/r}(\log \log N)^{1-1/r}$ 的函数。
- 目标是在保持完美安全并支持任意素数 $p$ 的同时，降低渐近密钥大小。

2. 方法论

作者提出了一种基于LKZ 框架（Li, Kopparty 和 Zhang）结合最先进的**私有信息检索（PIR）**技术的新型构建方案。

A. LKZ 框架

该框架通过**份额转换（Share Conversion）**将秘密共享方案（SSS）转换为 ITDPF。

份额转换： 它要求将 $(t, n)$ -阈值 SSS（ $L_1$ ）的份额转换为加法 SSS（ $L_2$ ）的份额，使得转换后份额的总和揭示出与原始秘密的特定关系。
双线性表示： 点函数被表示为转换后份额的双线性函数。
关键洞察： 所得 ITDPF 的密钥大小与用于生成份额转换的底层 PIR 方案的通信复杂度成正比。

B. 利用 GKS 基于导数的 PIR

核心技术创新在于利用 Ghasemi、Kopparty 和 Sudan（GKS，STOC 2025）最近提出的1-隐私 $n_r$ -服务器 PIR方案。

GKS 机制： 与仅查询多项式求值的先前 PIR 方案不同，GKS 同时查询多项式的求值和 Hasse 导数。
数学基础：
- 在有限域上使用 $S$ -匹配族和 $S$ -解码多项式。
- 引入了带重数的 0-插值性质。通过请求导数，该方案可以使用更少的服务器或更小的参数来插值稀疏多项式的常数项。
- 具体而言，GKS 针对 $n_r$ 个服务器实现了 $2^{O(\nu_{r+1}(N))}$ 的通信复杂度，其中 $n_r$ 取决于模数素因子的数量。

C. 提出的构建步骤

设置：
- 选择模数 $M = m \cdot p$ （不同素数的乘积）。
- 构建一个 $S_M$ -匹配族和一个重数为 2 的 $S_M$ -解码多项式（由导数查询启用）。
份额转换（$Conv$）：
- 服务器持有源自随机向量 $w$ 和目标索引 $\alpha$ 的份额 $c_\ell$ 。
- 给定输入 $x$ ，服务器计算限制在乘法线上的“核心多项式” $D_x(Z)$ 。
- 利用链式法则，服务器在特定点 $b_\ell$ 处计算 $D_x(Z)$ 的一阶 Hasse 导数。
- 服务器输出一个转换后的份额，该份额涉及求值 $D_x(b_\ell)$ 和导数项，并由插值系数 $a_{\ell, k}$ 加权。
DPF 生成：
- 生成器创建 $2n_r$ 个密钥。每个密钥由一对组成：输出值的加法份额和源自底层基于 PIR 的 SSS 的份额。
- 评估算法计算密钥分量的内积，以恢复 $f_{\alpha, \beta}(x)$ 的加法份额。

3. 主要贡献

新颖的份额转换： 作者直接从 GKS 基于导数的 PIR 推导出了新的份额转换函数。这是将基于导数的 PIR 应用于构建 ITDPF 的首次尝试。
改进的密钥大小： 他们构建了一个具有输出群 $\mathbb{Z}_p$ $Z_{p}$ 的完美安全 $(1, 2n_r)$ $(1, 2 n_{r})$ -ITDPF。
- 密钥大小： $O(2^{c_2(r) \cdot \nu_{r+1}(N)} \cdot \log p)$ 。
- 改进： 这渐近地小于之前最好的完美安全 ITDPF（例如 Li 等人的 $2^{O(\nu_r(N))}$ ），有效地将指数从 $\nu_r(N)$ 降低到了 $\nu_{r+1}(N)$ 。
完美安全： 该构建保持了完美安全（针对计算能力无界对手的信息论安全），不同于某些为了效率而牺牲安全的统计替代方案。
通用性： 该方案适用于作为输出群模数的任意素数 $p$ ，这是对某些先前构建方案的重要推广。

4. 结果

理论界限： 本文证明了所提出的方案满足 LKZ 框架的正确性和完美安全要求。
比较（表 I）：
- 与**[10] 中的定理 10**（Li 等人）相比，后者密钥大小为 $O(2^{c_1(r) \cdot \nu_r(N)})$ ，新方案实现了 $O(2^{c_2(r) \cdot \nu_{r+1}(N)})$ 。由于 $\nu_{r+1}(N) < \nu_r(N)$ ，新密钥在渐近意义上严格更短。
- 与**[2] 中的定理 1**（Boyle 等人）相比，新方案并不逊色，并为大 $N$ 提供了更好的渐近扩展性。
参数： 所需的服务器数量为 $2n_r$ ，其中 $n_r$ 由 PIR 构建中素因子的数量定义（例如 $n_1=2, n_2=3, \dots$ ）。

5. 意义

MPC 和 PIR 中的效率： DPF 是安全多方计算（MPC）和私有信息检索（PIR）的基本构建模块。减少密钥大小直接转化为这些协议中更低的通信开销和存储需求。
连接 PIR 与 DPF： 这项工作展示了 PIR 最新进展（特别是基于导数的方法）与 DPF 构建之间的强大协同作用。它表明 PIR 通信复杂度的改进可以直接转化为更高效的 DPF。
未来方向：
- 当前的构建仅限于1-隐私 DPF（针对 1 个合谋服务器的安全），因为底层的 GKS PIR 是 1-隐私的。在不导致服务器数量指数级膨胀的情况下将其扩展到 $t > 1$ 的 $t$ -隐私 DPF 是一个未解决的挑战。
- 将输出群从素数阶 $\mathbb{Z}_p$ 扩展到任意阿贝尔群被确定为未来的工作方向。

总之，本文通过利用最新的基于导数的 PIR 技术，在完美安全 ITDPF 的效率方面取得了突破，为素数阶输出群实现了已知最短的秘密密钥。