跳到正文
原文

实例编码能否实现隐私学习?

Is Private Learning Possible with Instance Encoding?

arXiv· arXiv:2011.05315· Nicholas Carlini, Samuel Deng, Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, Shuang Song, Abhradeep Thakurta, Florian Tramer·本站收录· 23 天前· 原文发表攻击

论文速读

攻击

据论文 PDF 整理(AI 生成),以原文为准

作者形式化实例编码隐私并证明不可能性结果,对 InstaHide 提出重建攻击,恢复 100 张挑战图像。

威胁模型攻击者获得编码后的数据集 S̃(及方案使用的公开数据 P),无法访问原始数据 S;目标是从 S̃ 中区分或重建原始训练样本。

问题
能否先把训练数据编码再交给普通学习器,从而在不牺牲精度的情况下获得隐私?作者研究这类实例编码方案的理论极限,并检验代表方案 InstaHide 是否真正隐私。
方法
作者形式化实例编码及其隐私定义,证明针对区分攻击的不可能性定理;对 InstaHide 设计三阶段重建攻击:取绝对值去符号、用神经网络聚类同源编码、解线性方程组恢复原图。
实验与结果
攻击在 CIFAR-10、CIFAR-100 和 InstaHide Challenge 上重建出高保真原图,包括挑战全部 100 张图;单编码攻击在 100 个编码中 69% 恢复全部 3 张公开混合图;作者称增大 MixUp-k 反而使攻击更好。
局限与可以继续做的
作者指出单编码攻击需假设攻击者知道私有数据分布和公开数据集 P,且因挑战未发布公开图像而无法用于挑战;像素级精确恢复在数学上不可能,仅利用实现缺陷(PRNG)才能达到。
实验设置InstaHide · CIFAR-10、CIFAR-100 等 · distinguishing advantage、reconstruction fidelity 等
威胁模型
攻击者获得编码后的数据集 S̃(及方案使用的公开数据 P),无法访问原始数据 S;目标是从 S̃ 中区分或重建原始训练样本。对 InstaHide 的单编码攻击还假设攻击者知道私有数据分布和公开数据集 P。
被测模型
InstaHide
基准
CIFAR-10CIFAR-100InstaHide ChallengeImageNet (32x32)STL-10
指标
distinguishing advantagereconstruction fidelitySSIM相似度网络分类准确率
AI 导读作者研究能否借助实例编码让非隐私学习算法获得隐私性,并针对 InstaHide 给出实际攻击。论文为实例编码及其隐私定义建立两种攻击模型,先在较强模型下给出不可能结果,再在较弱模型下展示对 InstaHide 的实际攻击;InstaHide 是 Huang、Song、Li 和 Arora 在 ICML'20 提出的方案。

作者研究能否借助实例编码让非隐私学习算法获得隐私性,并针对 InstaHide 给出实际攻击。论文为实例编码及其隐私定义建立两种攻击模型,先在较强模型下给出不可能结果,再在较弱模型下展示对 InstaHide 的实际攻击;InstaHide 是 Huang、Song、Li 和 Arora 在 ICML'20 提出的方案。

相关热点

0 个事件 · 1 条新闻提到

提到这篇论文的新闻

  • Nicholas Carlini Writing引用了论文编号或链接
    InstaHide 获贝尔实验室奖二等奖引发争议
    We showed this in a recent paper (and if you're reading this within the next few days, we'll be giving a talk on this paper at the PPML workshop at NeurIPS).

深度解读

6个问题,点开问题读完整回答

  1. 这篇论文试图解决什么问题?

    实例编码能否在不牺牲精度下提供隐私?作者给出否定的理论结果并攻破 InstaHide。

    核心问题:能否设计一种实例编码函数,让非私有学习算法在编码数据上训练出精确模型,同时原始数据对攻击者保持隐藏?

    • 问题场景:神经网络越来越多地在敏感用户数据上训练(如医学影像、邮件文本)。现有隐私方案要么需要可信中心方,要么依赖多方安全计算等密码学技术(计算通信开销大),要么用差分隐私(精度代价高)。作者问:是否存在其他方式,在不牺牲性能或精度的情况下实现隐私学习?
    • 现有方法的不足:作者称,近期提出的实例编码方案(如 InstaHide)缺乏严格的隐私定义,依赖启发式安全论证。
    • 核心观察:如果编码后的数据仍能训练出精确模型,那么编码本身就泄露了足以区分不同数据集或不同实例的信息;区分攻击比重建攻击更难防御。
    • 论文贡献:形式化实例编码及其隐私(两个攻击模型);证明对区分攻击的不可能性结果(Theorem 1、2);对 InstaHide 提出实际重建攻击,恢复其挑战中全部 100 张私有图像。
    • 威胁模型:
      • 攻击者目标:从编码数据集 S̃ 中学习关于原始数据集 S 的敏感信息,最强形式是完全重建训练样本(Definition 6)。
      • 攻击者知识:可以访问编码数据集 S̃;若编码方案使用公开数据 P,攻击者也可访问 P;无法访问原始数据 S。
      • 攻击者能力:多项式时间;对 InstaHide 的单编码攻击还假设知道私有数据分布和公开数据集 P。
      • 受害系统:使用实例编码(如 InstaHide)保护训练数据隐私的学习协议。
  2. 有哪些相关研究?

    相关工作涵盖私有学习样本复杂度下界、成员推理与模型反演攻击、以及密码学隐私训练方案。

    私有学习的样本复杂度下界

    • Duchi 等(2014)、Hardt 与 Talwar(2010)、Bun 与 Zhandry(2016)——用 packing 论证给出参数/概率估计的紧界。Bun 等(2018)证明差分隐私回答大量计数查询的样本复杂度下界。Bassily 等(2014)、Beimel 等(2014)证明差分隐私 PAC 学习的样本复杂度下界。作者称 Theorem 1 可视为私有 PAC 学习样本复杂度的(维度无关)下界,且其两个数据集标签一致、与概念函数相容,更贴近现实场景。

    针对机器学习模型的隐私攻击

    • Shokri 等(2017)等——成员推理攻击;Fredrikson 等(2014, 2015)、Wu 等(2016)——模型反演攻击;Dinur 与 Nissim(2003)、Dwork 等(2015, 2017)等——重建攻击。作者称本文对 InstaHide 的攻击属于重建攻击的一种。

    可证明隐私的训练方案

    • Mohassel 与 Zhang(2017)、Bonawitz 等(2016)等——多方安全计算;Gentry(2009)、Hesamifard 等(2017)——全同态加密;Dwork 等(2006)、Abadi 等(2016)——差分隐私。作者称这些方案能提供可证明的隐私保证,但性能和精度代价高。

    基于编码的隐私方案

    • Huang 等(ICML 2020)——InstaHide,将多张图像线性混合并随机翻转像素符号,获 2020 年 Bell Labs Prize 第二名;Raynal 等(2020)——图像混淆;Liu 等(ECCV 2020)——DataMix 隐私推理。作者称这些方案依赖启发式安全论证,本文的攻击很可能也能击败类似构造。

    定位:作者称本文形式化了实例编码的自然(密码学意义)隐私概念并证明其不可能性,再以重建攻击直接反驳 InstaHide 的启发式隐私论证。

  3. 论文如何解决这个问题?

    先形式化实例编码与隐私定义并证明区分攻击的不可能性,再对 InstaHide 设计三阶段重建攻击。

    整体思路分两部分:理论上,为实例编码定义密码学风格的不可区分性隐私概念,证明任何保持效用的编码都无法抵抗区分攻击;实践上,利用 InstaHide 编码的可区分性,先聚类同源编码再解线性系统重建原图。

    问题形式化与隐私定义

    • 数据集编码机制(Definition 1):编码函数 E 将数据集 S 映射为编码数据集 S̃;若对实例和标签分别编码则称为可分解(decomposable),若每个编码只依赖至多 r 个样本则称为 r-local。InstaHide 是可分解且局部的特例。
    • 效用定义:原始数据精度(Definition 2)要求模型在原始分布上风险有界;编码精度(Definition 3)要求模型能从编码 x̃ 预测其中某个原始实例 x 的标签 c(x)。
    • 隐私定义:数据集区分攻击(Definition 4)要求攻击者区分两个仅差一个同标签样本的数据集的编码,优势为 p − 1/2;实例区分攻击(Definition 5)只给攻击者单个编码;实例恢复攻击(Definition 6)要求攻击者输出与某训练样本距离不超过 γ 的点。

    理论不可能性结果

    • Theorem 1(数据集编码的极限):若协议在原始数据上精度至少 51%,则对任何非平凡概念类,攻击者可选出概念 c 和两个仅差一个(同标签)样本的数据集 S1、S2,以概率 1/2 + Ω(1/n) 区分其编码。
    • Theorem 2(实例编码的极限):若概念类足够丰富(含 m 个平衡且相互独立的概念),且协议编码精度为 1/2 + δ,则攻击者可以至少 0.99 − O((1−2δ)/(1−2/√m)) 的概率区分两个随机实例的编码。
    • Theorem 5(单一概念的变体):若编码在单一概念上达到平衡编码精度,则要么存在高效区分攻击,要么能从中提取出精度任意接近 1 的分类器;作者称这对精度有上界的学习任务构成隐私-效用权衡的障碍。

    对 InstaHide 的重建攻击

    • 攻击流程(Figure 2):1) 对所有编码取绝对值,消除符号翻转;2) 训练神经网络判断两个编码是否共享原始图像,构建相似度图并聚类出每个原图对应的编码集合;3) 给定聚类结果和混合系数 λ,通过梯度下降求解欠定非线性方程组,重建原图。
    • 相似度网络:Wide ResNet-28,输入为两个编码在通道维拼接(32×32×6),用 Adam(学习率 0.1、权重衰减 5·10⁻⁴)训练 10⁶ 步;训练数据用 32×32 ImageNet 作公开集、CIFAR-10/100 与 STL-10 训练集作私有图;留出验证准确率 91%。第二阶段用 4 个参考编码训练新网络,准确率升至 96%。
    • 聚类与指派:贪心扩展得到候选集合后用 k-means(k = |X|)聚类;再用 min cost max flow 将每个编码指派给恰好 2 个集合、每个集合恰好 N 个编码,恢复映射 φ′。
    • 图像恢复:混合系数 λ 可从编码标签直接读出(同类混合时猜测均分);求解 M · abs(A′) + σ = abs(B) 的最小二乘问题,用梯度下降最小化 |σ|22;作者称因系统欠定,像素级精确恢复在数学上不可能,但可获得高相似度重建。最后用 73 参数微型网络做颜色饱和度校正。

    单编码攻击(N = 1)

    • 假设攻击者知道私有数据分布和公开数据集 P;先训练 GAN 学习 abs(x) ↦ x 的“重新着色”映射以恢复符号掩码 σ,再对公开数据集做 SSIM 相似度搜索,逐个减去最相似的公开图像(猜测混合权重 λ = 1/k),恢复私有图像。
  4. 论文做了哪些实验?

    在 CIFAR-10、CIFAR-100 和 InstaHide Challenge 上重建全部 100 张原图,并评测单编码与大 k 设置。

    实验设置

    • 被攻击方案:InstaHide(Huang 等,ICML 2020),使用其作者开源代码构造编码数据集;挑战版本为最强配置 k = 6。
    • 数据集:CIFAR-10、CIFAR-100(各取测试集前 100 张为私有图,编码为 5,000 张);InstaHide Challenge(5,000 个编码对应 100 张未知分布的私有图,N = 50);相似度网络训练用 32×32 ImageNet 作公开集、CIFAR-10/100 与 STL-10 训练集作私有图。
    • 攻击模型:Wide ResNet-28 相似度网络(验证准确率 91%);第二阶段集合相似度网络(96%);GAN 用于单编码攻击的重新着色;73 参数网络用于颜色校正。
    • 指标:重建质量以视觉保真度展示(Figure 1、3、4 及附录 C 全部图像);单编码攻击报告恢复公开混合图的比例;理论部分报告区分优势。
    • 计算量:CIFAR 攻击总计 2 GPU 小时 + 2 CPU 小时;挑战攻击 1 小时内完成;PRNG 状态提取 120 CPU 小时(100 核并行约 1 小时)。
    • 重复次数与统计检验:论文未报告。

    主结果

    表格较宽,可左右滑动

    设置私有图数编码数结果出处
    CIFAR-10(k = 6)1005,000重建 100 张,视觉高保真Figure 3a、Figure 5
    CIFAR-100(k = 6)1005,000重建 100 张,视觉高保真Figure 3b、Figure 6
    InstaHide Challenge(k = 6, N = 50)1005,000重建全部 100 张Figure 1、Figure 7
    Challenge(PRNG 实现缺陷攻击)1005,000像素级精确重建Figure 8、附录 B
    • 作者称攻击“极其有效”,重建与原图几乎视觉一致;挑战的 ground truth 通过对 InstaHide 实现中 PRNG 的密码分析攻击获得(附录 B)。
    • 作者称攻击无超参数(除图像尺寸外),同一配置在 CIFAR-10、CIFAR-100 和挑战上都有效。
    • Figure 1 上行(PRNG 攻击所得 ground truth)与下行(通用攻击重建)在文字层面只能确认作者称两者高度一致,具体图像内容无法从文本判断。

    单编码攻击(N = 1)

    • 测了什么:每个私有图只发布一个编码(k = 4),私有图为 CIFAR-10 测试集前 100 张,公开集为剩余 9,900 张。
    • 结果:在 100 个编码中,69% 恢复全部 3 张公开混合图,85% 至少恢复 2/3 张;作者称 GAN 重新着色在多数情况下恢复大部分掩码 σ,成功时私有图被近乎完美提取(Figure 4)。
    • 作者解读:若 InstaHide 在只发布单个编码时仍要提供安全性,则其安全性必须部分依赖“公开”混合数据 P 的保密性。

    更大 MixUp-k 的分析

    • 测了什么:分析 k 增大对主攻击的影响(理论分析,无新实验数字)。
    • 结果与作者解读:作者称 k 增大反而使攻击更好——因为把公开图噪声 σ 近似为高斯噪声的假设随 k 增大而更准确,k → ∞ 时公开图平均后噪声趋于零;即使 k > 100,InstaHide 在同一攻击下仍然被攻破。

    其他消融与分析

    • 相似度网络参考编码数:超过 4 个后收益递减(Section 4.3.4)。
    • 贪心聚类参数 M = N/4 在实践中有效(Section 4.3.3)。
    • 若 InstaHide 随机选择集合大小而非恰好 N,初步实验显示攻击成功率不变(Section 4.4)。
    • PRNG 攻击:穷举 2³² 种子,每个候选验证约 0.1 毫秒;若 InstaHide 只发布 abs(e),该攻击不可行(附录 B)。
  5. 有什么可以进一步探索的点?

    作者讨论了单编码攻击的假设与像素级恢复的不可能性,并呼吁方案给出可证伪的隐私声明。

    作者指出的局限与后续方向

    • 单编码攻击的假设:攻击假设攻击者知道私有数据分布与公开数据集 P;作者称这一假设较强,且因挑战未发布公开图像,该攻击无法用于 InstaHide Challenge(Section 4.8.1)。
    • 像素级恢复不可能:由于方程组欠定,作者称像素级精确恢复原图在数学上不可能,重建只能做到与原图高相似(Section 4.2)。
    • Theorem 1 的改进空间:作者称或许可以通过纳入数据维度来改进 Theorem 1,但维度无关本身是优点(Section 1.3)。
    • 对其他方案的扩展:作者称类似的启发式构造还出现在其他隐私训练与推理方案中,这些方案很可能能被类似攻击击败(Section 5)。
    • 对防御方的建议:作者称提出的方案应提供精确、可证伪的隐私声明,而非启发式安全论证(Section 5)。

    实验覆盖范围

    • 被攻击的方案只有 InstaHide 一个;数据集为 CIFAR-10、CIFAR-100 和 InstaHide Challenge,图像均为 32×32。
    • 主攻击评测的设置:k = 6、N = 50(挑战)或 5,000 编码对应 100 张原图(CIFAR);单编码攻击评测 k = 4、N = 1。
    • 重建质量主要以图像展示呈现,论文未报告重建的定量相似度指标(如 SSIM 数值)或每个数据集的重建成功率。
    • 论文未报告攻击的重复次数、统计显著性检验或人工评估。
    • 理论结果针对区分攻击;作者明确指出其结果并不排除针对实例恢复攻击的隐私可能性(Section 2.2.1)。
  6. 总结一下论文的主要内容

    实例编码无法同时保持效用与不可区分性隐私;对 InstaHide 的重建攻击恢复了全部 100 张挑战图像。

    一篇理论结合实践的攻击论文,研究“先编码训练数据、再用普通学习器训练”能否在不牺牲精度的情况下提供隐私。

    • 问题:现有隐私训练方案(MPC、差分隐私)代价高,实例编码方案(如 InstaHide)声称能低成本保护隐私,但缺乏严格隐私定义。
    • 理论结果:作者形式化实例编码与两种区分攻击模型,证明任何在原始数据上精度至少 51% 的编码协议,都存在以 1/2 + Ω(1/n) 概率区分两个仅差一个同标签样本的数据集的攻击(Theorem 1);对丰富概念类,实例编码的区分优势可达 0.99 − O((1−2δ)/(1−2/√m))(Theorem 2)。
    • 对 InstaHide 的攻击:三阶段重建——取绝对值消除符号翻转、用 Wide ResNet-28 相似度网络(91% 验证准确率)聚类同源编码、解最小二乘系统重建原图;在 CIFAR-10、CIFAR-100 和 InstaHide Challenge(k = 6,5,000 编码对 100 原图)上重建全部 100 张图像,作者称重建与原图几乎视觉一致。
    • 安全参数分析:单编码攻击(假设知道公开数据集 P)在 100 个编码中 69% 恢复全部 3 张公开混合图、85% 至少恢复 2/3;作者称增大 MixUp-k 反而让攻击更好,因为高斯噪声近似更准确。
    • 实现缺陷:附录 B 报告 InstaHide 实现使用 Mersenne Twister PRNG,穷举 2³² 种子(120 CPU 小时)可提取状态并像素级精确重建;作者称该缺陷可轻易修复,并非 InstaHide 的根本问题。
    • 作者结论:任何能训练出精确模型的编码方案都无法提供类似 MPC 的不可区分性保证;作者呼吁未来的隐私方案给出精确、可证伪的隐私声明。

相关论文

共同使用 STL-10
共同使用 CIFAR-100
再看 3 篇
共同使用 CIFAR-100
阅读原文arxiv.org