InstaHide令人失望地获得贝尔实验室奖，第二名

[以下是我对机器学习隐私的一些最新研究的看法。这些是我的想法，并不代表其他人的想法。]

InstaHide（一种声称可以提供一种训练神经网络的方法，同时又保留了训练数据的隐私性的最新方法）刚刚获得了第二名的贝尔实验室奖（该奖项是“为解决信息和电信行业面临的一些最大挑战提供解决方案的奖项”。 ”）。这是一个严重的错误。

贝尔实验室将信息理论，晶体管，C编程语言和UNIX操作系统的基础推向世界。没有贝尔实验室，今天的世界肯定不会是现在。因此，当本周早些时候InstaHide被授予贝尔实验室奖第二名时，我感到非常失望和悲伤。

如果您未深入机器学习隐私研究社区，InstaHide是最近提出的在保留训练数据隐私的同时训练神经网络的建议。它（表面上）允许某人在大量敏感的训练数据上训练机器学习模型，然后发布该模型，而不必担心该模型会泄漏有关训练数据本身的任何信息。

不幸的是，事实证明InstaHide不提供任何隐私。对于隐私的任何合理定义，它不是私有的，并且鉴于InstaHide的输出，可以完全恢复输入到其中的输入。我们在最近的一篇论文中对此进行了展示（如果您在接下来的几天内阅读此书，我们将在NeurIPS的PPML研讨会上对该论文进行演讲）。

InstaHide之所以被授予这一奖项是一个严重的错误，因为InstaHide的想法和论文的方法论从根本上被误导了。向右绘制是我们能够执行的操作：给定一组编码图像，这些图像试图保留一些隐私概念，我们将恢复极高的保真度。

在编写攻击报告后，我正打算保留原样。但是在观看了颁奖典礼以及对颁奖典礼的回应之后，我感到不得不做出回应。 [a]不，我保证我不会痛苦，因为即使这篇论文被破坏并且没有任何安全性，它也被授予了奖项。我已经习惯了。 2013年，我打破了kBouncer防御程序，该防御程序获得了Microsoft Blue Hat的20万美元奖金。那时我没有抱怨，因为至少该攻击需要一些技术上的新颖性和有趣的研究，并且因为微软在攻击发布后没有颁发奖金。

该奖项之所以真正给我，是因为InstaHide确实是机器学习论文往往具有的所有弱点的最终体现，从专注于讲述好故事而不是掌握好的技术，到主张不是事实。 t可辩驳的。

虽然这篇论文是由多位作者撰写的，但我不应该将其归咎于本文的第一作者，即一位早期职业的博士生，他认真而精确地执行了这一想法。这篇论文写得非常好，实验是经过认真而严格的进行的。在上个月使用InstaHide实现工作之后，该代码是正确的，易于遵循的，并且其他研究人员在自己编写代码时也应努力做到这一点。本文中的数字清楚，并为权利要求提供了依据。第一作者应该做的所有事情都做得很完美。

在接下来的其余部分中，当我提到“ InstaHide作者”时，我指的是本文中的高级作者，他们应该更了解。其中，他们获得了两次戈德尔奖，8万次引用和400的i-10指数。第一个完全没有错误。

我将在下面进行详细介绍，但在此简要概述一下出了什么问题。

InstaHide没有任何可辩驳的声明。科学与伪科学之间的主要区别在于科学中的主张是可以证伪的。必须存在一种方法来驳斥索赔。 InstaHide不会伪造任何隐私声明，而是声明其算法是私有的，而从未定义这意味着什么。

InstaHide移动了隐私目标。即使论文本身没有提出可辩驳的主张，作者也发表了可以解决的竞赛。因此，我们做到了：彻底打破了比赛。作者对此的回应是，无论如何InstaHide都不打算成为防弹方案，因此解决他们的挑战也就不足为奇了。

InstaHide只是为了演示而复杂。 InstaHide没有构建可能提供隐私的最简单的方案，而是构建了一个复杂的方案，因为它使视觉图片看起来更漂亮。

InstaHide的虚假复杂性破坏了该方案。通常，人为的复杂性是一种有效的禁止操作。在这种情况下，由于实现错误，伪造的复杂性实际上允许对该方案进行完全攻击。

InstaHide具有虚假的定理。隐私定理很重要，但是InstaHide给出的定理在数学上是正确的，但与方案的安全性或隐私无关。

InstaHide忽略了严格的技术要求。文献中非常精确地定义的语句（例如，不可区分性）变得轻而易举。争论不清是需要工作的，但是本文只运行了一次统计检验。

InstaHide的作者继续对其进行推广。有时防御会被破坏。这是计算机安全的一部分。发生这种情况时，有必要承认它已损坏，然后尝试对其进行修复或继续进行新的提案。取而代之的是，InstaHide的作者继续宣传他们的工作，就好像它是有效的一样，而不考虑现实。

假设某家医院想训练世界上最伟大的医学成像扫描仪，该扫描仪可以对您的身体进行扫描，在上面运行一个漂亮的机器学习模型，并告诉您所有的问题。为此，他们当然需要大量的培训数据：来自具有扫描内容的个人的图像，以及他们遇到的（或没有）遇到的问题的列表。

我不想只是随机组织我曾经对我的身体进行的所有扫描。它们是我的私人照片。如果他们泄漏了怎么办？

训练数据隐私方案为某人提供了一种在此私有数据上训练机器学习模型的方式，而不必担心他们的训练数据将被泄漏。今天发布的大多数方案都可以证明是正确的：有一个正式的论据，除非证明中有错误，否则我的数据永远不会从训练过的模型中泄漏出来。

（是的，诸如RSA或AES之类的密码系统不是可证明的安全性，我们还是要使用它们。但是，这些系统明确地旨在尽可能简单以使分析变得容易。这完全独立于我们在谈论的内容，因为隐私方案确实确实可以证明是安全的。））

问题在于这些方案通常很慢，并且通常会降低最终模型的准确性。这不是理想的，但这是正确性的代价。

InstaHide是关于如何使用相当简单的算法来实现此结果的建议，该算法不会增加模型训练时间，也不会引起巨大的精度下降。这显然是一个重要的最终目标，任何尝试做到这一点的方案都应使我们感到兴奋。

InstaHide的基本思想是一个简单的两步过程。要对任何特定的私人图像进行编码，请将其与一堆其他随机图像组合在一起，然后随机翻转图像中像素的符号。

现代科学的核心宗旨之一（在过去的一百年里）是主张应该是可辩驳的：如果主张是错误的，那么必须存在一个可以证明它的实验。这就是将科学与伪科学区分开来的原因。不幸的是，InstaHide并未提出虚假的声明。它声称提供隐私，而从未定义这意味着什么。这是许多关于机器学习的安全性和隐私性的常见故障，但是最近没有一篇论文比InstaHide更好地证明了这一点。

一个典型的隐私定义会说“如果Y成立，就不可能学习有关训练数据集的属性X”的形式。例如，差异性隐私表示不可能区分特定用户是否在数据集中的情况。 InstaHide纸没有可辩驳的隐私声明。它定义了一个算法，并说它是私有的，而从未说过这意味着什么。

结果，不可能写出声称破坏它的论文，因为定义攻击必然需要一个破坏的定义。最好的方法（实际上是我们在本文中所做的）是定义InstaHide隐私可能意味着的潜在定义，并表明它不满足这些定义。但是，总有可能存在InstaHide确实满足的一些隐私定义。

幸运的是，作者的确发布了InstaHide挑战赛：他们要求研究人员在尽可能强大的环境下尝试破坏InstaHide的隐私。在这里，定义隐私的定义很明确：给定InstaHide算法的输出，我们被要求尝试重建原始数据集。即使算法不可重演，至少这场比赛也是。

该挑战（以及该算法的源代码）在最初的论文被公开介绍和讨论四个月后发布。如此巨大的延误这一事实意味着，在头四个月中，不可能肯定地说InstaHide是不安全的。

如果作者按时发布了挑战，那么在仍被认为是贝尔实验室奖的论文发表之初，它会获得奖项吗？我怀疑不是。 （现在，由于我们的攻击是在奖品发布前一个月发生的，所以它获得奖项仍然是不可原谅的。但是我希望，如果它在出版后几周就被打破了，它将不会在所有。）

因此，在作者发布挑战的一周后，我们解决了挑战。我们提出了两种攻击方式，一种破坏基本算法，另一种破坏挑战的实现。因此，至少我们知道挑战数据不是私有的。但这将我们带入下一个问题...

在发布我们的攻击后，Sanjeev Arora（该论文的高级作者）在博客文章中回复说：“ InstaHide绝不是像RSA这样的任务关键型加密”。第一：什么？！第二：本文从未提到过，只有在我们将其破解后才予以说明。第三：任何算法都不应设计为仅在最佳情况下提供“某种”安全性。算法被设计为能够（几乎）完全安全，并且一旦发现任何弱点，就会将其丢弃以采用更强大的方法，或者将其修复以保持强大的安全性。

一旦发现DES（或MD5或SHA-1）根本没有任何弱点，密码学家便开始设计全新的算法来替代它们。显然，这些替换算法设计为完全安全的。即使防御者只有非常有限的计算量，加密算法仍然认为安全性可以抵抗功能强大几个数量级的对手。仅仅因为防御者只能以1瓦的功率运行，并不意味着对手就不能在计算集群上运行。

现在要获得技术知识，我应该真正讨论安全性参数。这是控制方案“多么强大”的价值。如果选择此参数的低值，许多算法（例如RSA）的安全性可能会大大降低。但是，重要的是，这很容易避免-只需选择一个大的！ InstaHide没有安全参数，因此无法通过调整一些常量来使其更加安全。

争辩说InstaHide仅在被破坏后才用于关键任务加密-甚至将攻击称为“在预期的环境下仍不具有成本效益的攻击”-简直就是在移动目标杆。这是您第一次不提出任何要求时可以做的事情。 InstaHide旨在确保安全。它不是。

（简而言之，该攻击的成本效益不高。该攻击大约需要12个小时的P100 GPU时间。在AWS或GCP上，这笔租金不到20美元。现在20美元已经算是什么了，它39; s肯定比免费软件贵。但是当DES第一次被破解时，它的造价为25万美元，并且需要几天的计算时间才能破解单个密钥。P100GPU的价格为2500美元（便宜100倍，不是通货膨胀的原因）。调整后），攻击速度至少快了几倍。但我离题了。）

对于论文而言，重要的是要使该技术背后具有引人入胜的故事，而不仅仅是引入一种先进技术。通常，这意味着通过在不需要的地方人为地引入复杂性，可以使论文看起来比实际意义更重要。

InstaHide正是这样做的。在他们的算法中的某个时刻，InstaHide有一个数字列表[1、3，-5、7，-2]。它需要增加此数字列表的私密性，因此将每个值乘以1或-1（随机选择）。因此，例如，如果我们选择[-1，1，1，-1，-1]，那么我们将得到[-1，3，-5，-7，2]。现在的主张是这样可以保留这些数字的隐私。

实际上，InstaHide可在图像上运行。因此，它将这幅图像放在猫的左边（我们可能将其视为私有），然后将其转换为右边图像的“编码”版本，其中每个像素都乘以1或-1。

精明的读者可能会发现，我们所做的只是删除原始列表的标志信息。因为我们随机地乘以1或-1，所以从理论上讲我们有信息完全删除了该符号。因此，InstaHide可以（更简单地）释放列表中每个项目的绝对值：[1、3、5、7、2]。这不会比做一些怪异的符号翻转过程揭示更多或更少的数据。

那么，为什么还要打扰这个标志呢？好吧，事实证明，有一种叫做“一次性垫”的东西。这是一种（证明是安全的）加密算法，在不同的设置下，它也依赖于通过将每个条目乘以1或-1来掩盖数字的随机列表。

因此，为了说InstaHide就像是一种完美的加密算法，作者必须介绍这种疯狂的符号翻转过程。当然，将其描述为采用绝对值会更简单。但这并没有一个很好的故事。无法将其称为加密算法。一个时间垫可以讲一个好故事。

如果InstaHide改用绝对值而不是翻转符号会发生什么？好吧显然还是猫。但是，如果这篇论文声称采用绝对值是安全的，会引起注意吗？可能不会。

这就是为什么伪造复杂性很危险的原因。它需要一个显然是一个破损的主意（采用像素的绝对值以某种方式保留其隐私权），并用看起来理智的东西代替它。但不是理智。

旁注：我怎么知道这种复杂性实际上是在欺骗人们？在颁奖典礼上，颁奖的贝尔实验室研究员明确表示，他不了解InstaHide是如何安全的，但我引用“仍然有效”。没有！它不是。但是这种复杂性正在按预期进行。

现在具有讽刺意味的是，事实证明，InstaHide使用的这种带有标志翻转的虚假复杂性实际上恰好引入了一个全新的漏洞，如果作者只是采用了列表的绝对值，该漏洞就不会存在。数字。

此实现使用标准伪随机数生成器（PRNG）来创建随机符号翻转掩码。事实证明，PRNG具有这样的属性：给定一些输出，就可以了解其状态，从而可以恢复每个后续输出。学习状态需要一点点工作，但并不是那么困难（大约需要100个CPU小时，花费约4美元）。所以我们做到了。

这意味着我们实际上可以取消符号翻转过程，并恢复原始图像。完成此操作后，InstaHide不再提供任何有意义的隐私。我们可以完全打破算法。

现在，如果InstaHide刚取了绝对值，那么标志信息实际上将被破坏。这种攻击是行不通的。但是由于作者坚持要添加不必要的复杂性以展示事物，因此实际上削弱了该方案。变得复杂并不好。它引入了其他错误的余地。

机器学习研究论文在提出算法A的地方做这件事，用言语说它起作用，然后证明定理T。问题是定理T常常与算法A根本不起作用完全脱节。 。立顿和斯坦哈特称这些伪定理。

InstaHide导致此错误的方法如下。为了证明所提出方法的安全性，作者证明“对于最坏情况的像素矢量，很难找到k图像集。”也就是说，他们说存在一个数据集，如果使用InstaHide加密，则将很难进行转换。

这个说法是正确的。确实存在难以反转的数据集。但这并没有说明标准图像会发生什么。证明存在困难的情况并没有帮助，我们必须证明问题始终是困难的。

将其与差异性隐私之类的东西相比，故事完全相反。这里的证据表明，对于所有数据集-不管病理如何-都将保留隐私。 InstaHide声称仅在某些病理数据集上是私有的。

该论文在其论文的图2的标题中突出指出“不同图像的加密分布是无法区分的”。这个短语看似平淡无奇，但是意识到不可分辨性实际上意味着在计算机安全性论文中有一个非常具体的含义：这意味着没有任何对手能够以比随机猜测加成倍的指数小概率更好的概率来区分两种分布。

本文断言这些分布不是无法用证据来区分的，而是因为在对直方图进行目视检查时，这些分布看起来或多或少地相互重叠，并在附录中进行了统计检验。

如果提出加密算法的论文在加密的消息中绘制1s和0s的频率，然后说“我们的算法输出的数据与随机数据没有区别，那您就可以知道，因为1的概率看起来大致等于”可能性为0”，但本文正是提出了这一论点。

如果到现在为止的一切都是真的，但是作者要出来说：“我们试图引入一种方案来增加训练数据的隐私性。事实证明我们的方案行不通。我们现在了解了这一点，并正在尝试使用隐私定义来构建更强大的方案。”那么我不会写这篇文章。问题是看到我们休息后，这还没有发生。他们仍然认为在某些情况下它是安全的，没有撤回贝尔实验室奖的提交，并且（一个月后）还没有接受我们在挑战排行榜上的表现。

我真的希望我们能够实现InstaHide的最终目标：不牺牲准确性或培训时间的保护隐私的培训。这将是惊人的。

但是，InstaHide不提供此功能。而且它不仅不提供隐私，

......