Truth, Justice, and Secrecy: Cake Cutting Under Privacy Constraints¶

会议: AAAI 2026
arXiv: 2511.09882
代码: 无
领域: AI安全 / 公平分配
关键词: 蛋糕切割, 隐私保护, 策略防操纵, 多方安全计算, 秘密共享

一句话总结¶

本文提出首个隐私保护的蛋糕切割协议 PP_CC_puv，将 Chen 等人的策略防操纵公平分配算法改造为基于秘密共享和安全多方计算（MPC）的隐私保护版本，在保持无嫉妒性、Pareto 最优和策略防操纵性的同时，确保参与者的偏好信息不被泄露。

研究背景与动机¶

领域现状：蛋糕切割（Cake Cutting）是公平分配理论的经典问题，将连续资源（建模为 \([0,1]\) 区间）公平分配给多个参与者。Chen 等人（2010/2013）提出了针对分段均匀估值的确定性策略防操纵算法 CC_puv，同时保证无嫉妒分配。

现有痛点：策略防操纵性只保证参与者没有动力撒谎，但不能阻止他们因隐私顾虑而隐瞒真实偏好。例如电信公司竞标频谱时不愿暴露未来发展计划，广告分配中不愿暴露营销策略，雇员分配排班时不愿暴露个人偏好。即使算法本身是策略防操纵的，中间计算过程可能泄露偏好信息。

核心矛盾：参与者需要向算法报告真实偏好才能获得公平分配，但算法执行过程（如图结构、流计算）会暴露这些隐私信息，导致理性但注重隐私的参与者不愿如实报告。

本文目标 设计一个蛋糕切割协议，同时满足：(1) 无嫉妒性；(2) 策略防操纵性；(3) Pareto 最优性；(4) 参与者偏好的隐私保护。

切入角度：利用秘密共享和安全多方计算（MPC）技术替换原算法中的集中式计算。关键挑战不是简单套用现成密码学工具，而是需要重新设计算法结构——例如将原算法中每轮变化的图替换为固定图结构。

核心 idea：用秘密共享隐藏参与者偏好和中间计算结果，用安全多方计算执行原算法中的排序、最大流等操作，实现首个同时具备隐私保护、无嫉妒和策略防操纵的蛋糕切割协议。

方法详解¶

整体框架¶

PP_CC_puv 协议忠实模拟了原始 CC_puv 算法的逻辑，但所有计算都在秘密共享上进行。流程分为四个阶段：(1) 参与者秘密共享各自的分段均匀估值函数；(2) 将蛋糕划分为区间集合 \(\mathcal{W}\) 并编码偏好为二进制向量；(3) 迭代地选择平均需求最小的参与者子集并分配对应区间；(4) 最终将区间分配给参与者。

关键设计¶

秘密共享偏好函数（SharingPrivateValuations）:
- 功能：将每个参与者的分段均匀估值函数安全地分发为秘密共享
- 核心思路：每个参与者 \(A_i\) 的估值由 \(\ell_i\) 个区间的端点描述。首先安全计算 \(\ell = \max_i \ell_i\)，然后所有参与者统一填充为 \(\ell\) 个区间（短的用空区间 \([1,1)\) 补齐），避免泄露区间数量。将实数端点离散化为整数（乘以 \(Q = 10^d\)），然后用 Shamir 秘密共享分发所有端点。阈值设为 \(t = \lfloor(n+1)/2\rfloor\)，需要诚实多数
- 设计动机：统一区间数量（padding）是防止信息泄露的关键——如果不同参与者共享不同长度的数据，区间数量本身就是隐私信息
固定图结构的遗忘流计算（AssignCakeToSelectedAgents）:
- 功能：在不暴露图结构的情况下执行最大流计算来分配区间
- 核心思路：原算法 CC_puv 每轮构造不同的图来计算最大流，图结构直接反映了参与者偏好。PP_CC_puv 用固定的全图替代动态图——边的容量通过秘密共享的密码学计算得到，非活跃的边容量被设为零。所有操作都在秘密共享上完成：排序、比较、乘法、除法等都使用对应的 MPC 子协议
- 设计动机：动态图的拓扑结构会泄露哪些参与者想要哪些区间；固定图结构确保了结构本身不携带隐私信息
迭代分配的遗忘选择（IterativeAllocation）:
- 功能：在不暴露已服务参与者和剩余区间的情况下选择下一批分配对象
- 核心思路：维护秘密共享的标志位 IntervalAvailable(k) 和 AgentServed(i)。每轮遗忘地计算每个参与者子集的平均需求 \(\text{avg}(S', X) = \text{Len}(D(S', X)) / |S'|\)，选择最小的子集。关键在于"遗忘"——协议不知道哪些参与者已被服务、哪些区间已被分配
- 设计动机：如果暴露迭代过程中参与者的退出顺序，就能推测其偏好强度

损失函数 / 训练策略¶

本文是密码学协议而非机器学习方法，不涉及训练。安全性保证：信息论级别的隐私保护（不依赖计算困难性假设），在诚实多数模型下，任何少于半数参与者的联盟都无法获得任何额外信息。计算开销为 \(O(1)\) 乘法常数，通信开销至多 \(O(n^2)\)。

实验关键数据¶

主实验¶

本文为理论贡献，主要通过定理证明而非实验验证。核心理论保证：

性质	CC_puv (原算法)	PP_CC_puv (本文)
无嫉妒性	✓	✓
策略防操纵	✓	✓
Pareto 最优	✓	✓
隐私保护	✗	✓ (信息论安全)
需要中央协调者	是	否 (参与者自行执行)
计算开销	基线	\(O(1)\) 额外乘法开销
通信开销	基线	\(O(n^2)\) 额外通信

消融实验¶

技术选择	效果	说明
动态图 → 固定图	防止图结构泄露	核心算法重构
区间数 padding	防止估值复杂度泄露	必要的隐私保护
安全排序替代明文排序	隐藏区间分割结果	\(O(m \log m)\) 安全比较
安全除法子协议	精确计算份额	新设计的 MPC 原语

关键发现¶

原算法的最大隐私泄露点不是最终分配结果，而是中间的图结构和迭代选择顺序
计算开销的常数因子增长很小，主要成本在通信——每轮 MPC 需要 \(O(n)\) 次消息交换
协议消除了对可信第三方的依赖，参与者可以自行执行

亮点与洞察¶

首创性：据作者所知这是首个隐私保护的蛋糕切割协议，填补了公平分配 × 隐私保护交叉领域的空白
固定图替换动态图：针对最大流算法的隐私泄露点，用固定全图 + 密码学容量控制的方式实现了结构遗忘，这一技巧可推广到其他基于图的分配算法
理论完整性：同时保持了无嫉妒、策略防操纵和 Pareto 最优三个性质，没有用隐私换取公平性

局限与展望¶

估值类型受限：仅适用于分段均匀估值（piecewise uniform），不支持分段线性或一般连续估值函数
诚实多数假设：需要超过半数参与者诚实，在高对抗性环境中可能不成立
通信开销：\(O(n^2)\) 的额外通信在参与者数量很大时可能成为瓶颈
实际效率未评估：论文缺乏协议实际运行时间的实验数据
自然的扩展方向是将隐私保护技术推广到更一般的蛋糕切割算法（如处理一般估值函数的算法）

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首个隐私保护蛋糕切割协议，开辟新研究方向
实验充分度: ⭐⭐⭐ 纯理论贡献，缺乏实际运行效率评估
写作质量: ⭐⭐⭐⭐ 协议描述清晰严谨，但密码学细节对非专业读者门槛较高
价值: ⭐⭐⭐⭐ 公平分配中的隐私保护是重要实际需求，理论贡献完整

Truth, Justice, and Secrecy: Cake Cutting Under Privacy Constraints¶

会议: AAAI 2026
arXiv: 2511.09882
代码: 无
领域: AI安全 / 公平分配
关键词: 蛋糕切割, 隐私保护, 安全多方计算, 无嫉妒分配, 策略防操纵

一句话总结¶

提出首个隐私保护的蛋糕切割协议 PP_CC_puv，基于秘密共享和安全多方计算（MPC）技术改造 Chen et al. 的策略防操纵算法，在保持无嫉妒、Pareto 最优和策略防操纵性质的同时防止任何参与方获知他人偏好信息。

研究背景与动机¶

领域现状：蛋糕切割问题是公平分配理论的经典问题——如何将连续资源（建模为 \([0,1]\) 区间）公平分配给 \(n\) 个代理。过去二十年在公平性方面取得了很大进展，Chen et al. (2010) 提出了同时满足无嫉妒（envy-free）和策略防操纵（strategyproof）的确定性算法 CC_puv（适用于分段均匀估值函数）。

现有痛点：策略防操纵只能解决"说谎无利可图"的问题，但代理可能出于隐私顾虑不愿如实报告偏好——即使不说谎比说谎好，他们也害怕暴露偏好。例如：电信公司竞拍频谱时，公开偏好会暴露未来战略方向；广告时间分配中，偏好可能泄露产品上市计划；数据保护法规也可能限制偏好公开。

核心矛盾：现有算法要求代理向中央协调者或其他参与方公开估值函数，但公开偏好可能带来隐私风险。策略防操纵和隐私保护是两个正交的需求维度。

本文目标 设计一个同时满足公平性（envy-free）、效率性（Pareto-optimal）、策略防操纵（strategyproof）和隐私保护（privacy-preserving）的蛋糕切割协议。

切入角度：将 CC_puv 算法的集中式计算替换为基于 Shamir 秘密共享和安全多方计算的分布式协议，使代理可以在不暴露偏好的情况下完成分配。

核心 idea：用密码学的秘密共享和安全多方计算技术将已有的策略防操纵蛋糕切割算法"私有化"，使代理既没动机说谎也不会暴露偏好。

方法详解¶

整体框架¶

协议 PP_CC_puv 忠实模拟原始 CC_puv 算法的逻辑，但所有计算都在秘密共享的数值上进行。整体分为五个阶段：（1）代理秘密共享各自的分段均匀估值函数；（2）将蛋糕分割成区间集合 \(\mathcal{W}\)；（3）用二值向量编码哪些区间被哪些代理"渴望"；（4）迭代地选择具有最小平均需求的代理子集并分配；（5）最终将区间分配结果（以秘密共享形式）揭示给各代理。

关键设计¶

估值函数的秘密共享（SharingPrivateValuations）:
- 功能：将每个代理的分段均匀估值函数转为 \((t,n)\)-秘密共享
- 核心思路：每个代理的估值由 \(\ell\) 个区间端点 \((a_{i,j}, b_{i,j})\) 描述。首先代理协商一个足够大的整数 \(Q = 10^d\) 将实数端点离散化为整数（无损），然后每个代理将 \(2\ell\) 个端点用 Shamir 的 \((t,n)\)-门限秘密共享分发。为防止作弊，协议包含完整性检查机制。共享门限设为 \(t = \lfloor(n+1)/2\rfloor\)，保证诚实多数即可保护秘密
- 设计动机：直接使用标准密码学会泄露区间数量等侧信道信息；通过将所有代理填充到相同数量 \(\ell\) 的区间并用空区间 \([1,1)\) 补齐，消除了这一泄露通道
固定图结构的遗忘式最大流（AssignCakeToSelectedAgents）:
- 功能：在不泄露图结构的情况下完成区间到代理的公平分配
- 核心思路：原始 CC_puv 在每轮迭代中构建不同的有向图并求最大流。但动态图的结构会泄露哪些代理渴望哪些区间。PP_CC_puv 用一个固定的全量图替代动态图，边权通过密码学计算得出：不相关的边权值设为 0 的秘密共享，分配通过 MPC 进行。这样协议对图结构保持"遗忘"（oblivious）
- 设计动机：确保协议执行过程中不会因图结构变化而泄露代理偏好与区间之间的关联
安全基本运算的组合:
- 功能：提供完整的安全计算原语集合以支持协议运行
- 核心思路：在秘密共享上实现仿射组合（零通信开销）、乘法（DN07 协议）、比较（\([[1_{u<v}]]\)）、相等测试（\([[1_{u=0}]]\)）、最小值、OR 运算和除法。这些原语按需组合实现排序、区间编码、需求计算等高层操作
- 设计动机：所有中间值——代理需求、区间选择、流计算——都以秘密共享形式存在，任何单一方无法获取明文信息

损失函数 / 训练策略¶

本文为理论密码学协议，无训练过程。计算开销为：原始算法复杂度的 \(\mathcal{O}(1)\) 倍计算开销 + 最多 \(\mathcal{O}(n^2)\) 额外通信代价。安全性基于信息论保证（非计算假设），在半诚实模型下成立，需要诚实多数。

实验关键数据¶

主实验¶

本文为理论工作，实验以形式化证明为主。核心结果是定理证明：

性质	CC_puv (原)	PP_CC_puv (本文)	说明
无嫉妒 (Envy-free)	✓	✓	完整保持
Pareto 最优	✓	✓	完整保持
策略防操纵	✓	✓	完整保持
隐私保护	✗	✓	新增——信息论安全
去中心化	✗	✓	新增——无需可信第三方

消融实验¶

协议组件	计算开销	通信开销	安全保证
秘密共享估值	\(\mathcal{O}(n\ell)\)	\(\mathcal{O}(n^2\ell)\)	隐藏估值+区间数
安全排序(分割区间)	\(\mathcal{O}(m \log m)\) MPC轮	\(\mathcal{O}(m^2)\)	隐藏端点排列
遗忘式最大流	\(\mathcal{O}(1)\) 相对原算法	\(\mathcal{O}(n^2)\) 每轮	隐藏图结构
最终分配揭示	\(\mathcal{O}(m)\)	\(\mathcal{O}(nm)\)	可选全公开/仅自己

关键发现¶

隐私保护不需要牺牲公平性或效率性——所有原算法的保证完整保留
最大的技术挑战是将动态图替换为固定图以防止结构泄露，这需要根本性的算法重构而非简单的"插入加密"
通信复杂度主要瓶颈在安全排序和最大流计算环节
协议支持两种揭示模式：全局可见（所有人看到完整分配）和受限可见（每人仅看到自己的份额）

亮点与洞察¶

首个隐私保护蛋糕切割协议：打通了公平分配理论与密码学之间的桥梁，将"不想说谎"和"不怕暴露"合二为一
固定图遗忘式最大流：用固定结构图+密码学边权替代动态图，避免结构泄露。这一技巧可推广到任何需要在秘密数据上执行图算法的场景
去中心化副产品：隐私协议的一个意外好处是消除了对中央协调者的需求，代理可自行执行协议——适用于没有可信基础设施的临时场景

局限与展望¶

仅处理分段均匀估值函数（piecewise uniform），尚不支持更一般的分段线性或任意估值函数
安全模型假设半诚实（semi-honest）——代理遵循协议但尝试推断他人信息。恶意对手模型下需要额外保障
需要诚实多数假设（>50% 诚实参与方），不满足时安全性失效
通信复杂度 \(\mathcal{O}(n^2)\) 在大规模参与方时可能成为瓶颈
作者指出将技术扩展到通用蛋糕切割算法（如支持任意估值函数的 Aziz-Mackenzie 协议）是自然方向

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首个隐私保护蛋糕切割协议，理论贡献突出
实验充分度: ⭐⭐⭐ 理论工作以证明为主，无实际运行时间对比
写作质量: ⭐⭐⭐⭐ 密码学和公平分配理论都讲解清楚，适合跨领域读者
价值: ⭐⭐⭐⭐ 在隐私日趋重要的时代，为公平分配理论开辟了新方向

Truth, Justice, and Secrecy: Cake Cutting Under Privacy Constraints¶

一句话总结¶

研究背景与动机¶

方法详解¶

整体框架¶

关键设计¶

损失函数 / 训练策略¶

实验关键数据¶

主实验¶

消融实验¶

关键发现¶

亮点与洞察¶

局限与展望¶

相关工作与启发¶

评分¶

Truth, Justice, and Secrecy: Cake Cutting Under Privacy Constraints¶

一句话总结¶

研究背景与动机¶

方法详解¶

整体框架¶

关键设计¶

损失函数 / 训练策略¶

实验关键数据¶

主实验¶

消融实验¶

关键发现¶

亮点与洞察¶

局限与展望¶

相关工作与启发¶

评分¶

Truth, Justice, and Secrecy: Cake Cutting Under Privacy Constraints¶

一句话总结¶

研究背景与动机¶

方法详解¶

整体框架¶

关键设计¶

损失函数 / 训练策略¶

实验关键数据¶

主实验¶

消融实验¶

关键发现¶

亮点与洞察¶

局限与展望¶

相关工作与启发¶

评分¶

Truth, Justice, and Secrecy: Cake Cutting Under Privacy Constraints¶

一句话总结¶

研究背景与动机¶

方法详解¶

整体框架¶

关键设计¶

损失函数 / 训练策略¶

实验关键数据¶

主实验¶

消融实验¶

关键发现¶

亮点与洞察¶

局限与展望¶

相关工作与启发¶

评分¶

相关论文¶