使用SNARKs的可验证FHE引导

博客

/

研究

使用SNARKs的可验证FHE自举

2024年5月5日

  -

Louis Tremblay Thibault 和 Michael Walter

这篇博文是我们新作品的精简版本：“迈向实践中的可验证FHE：使用plonky2证明TFHE自举的正确执行”。完整版本可在 ePrint 上找到，相关代码可在 github 上找到。

全同态加密 (FHE) 是一种允许在加密输入上执行任意计算，并生成加密输出的技术。这些结果在解密后，与在明文输入上执行计算的结果一致。

简洁的非交互式知识论证 (SNARKs) 是另一种密码学技术，它允许证明者说服验证者某些任意计算已被正确执行。

FHE 本身不提供关于计算正确性的保证，因此不提供任何关于完整性的保证，使其甚至容易受到某些现实世界部署中的隐私攻击。另一方面，SNARKs 保证计算的完整性，但需要证明计算正确的明文数据的知识，这在某些保护隐私的应用程序中可能是禁止的。

通过结合 FHE 和 SNARKs，我们获得了可验证的 FHE (VFHE)，其中证明者可以使验证者相信某些加密数据上的任意计算已正确执行。这是非常有吸引力的，因为这种技术有许多应用。例如，它可以改进支持私有交易的区块链协议。它还可以解决外包计算时的安全问题，在这些问题中，它可用于替换安全硬件模块，从而将信任从硬件供应商转移到加密假设。

虽然这一切在理论上听起来不错，但这种方法的核心问题是实用性：与明文操作相比，FHE 不仅会产生显着的开销，而且 SNARKs 本身的计算成本通常比被证明的计算要高得多。该项目的目的是探索 VFHE 实际上有多实用。

一个典型的 FHE 方案包括实现明文同态算术的密文运算和一个自举运算。如果你不熟悉 FHE，那么乍一看可能不清楚自举运算是做什么用的。我们在这里不详细介绍（有关更多详细信息，请参阅我们之前的博文），但简单地说，它是一种密文管理操作，允许程序无限期地在加密数据上进行计算。虽然算术运算通常计算起来非常有效（并且使用 SNARK 证明也很有效），但迄今为止成本最高的运算通常是自举。因此，它构成了通往真正 VFHE 系统的最大障碍，因为这种方案的实用性将主要取决于使用 SNARK 有效地证明自举的能力。因此，我们着手准确地做到这一点，看看我们是否可以为人们在实践中可能使用的实际参数做到这一点。

自然，我们专注于 TFHE，它提供了一种非常轻量级的可编程自举 (PBS)。即使 TFHE 的 PBS 比其他 FHE 方案中的自举成本更低，但它也足够复杂，如果天真地对其进行 SNARK 化，会导致证明者在大多数应用程序中可能被认为非常不切实际，这主要是由于巨大的内存需求。我们不是基于纯粹的估计来做出这个声明的，我们实际上尝试了这一点。即使只是使用适度的玩具参数，具有 128GB 内存的 AWS 实例也会耗尽内存。

当很明显这种直接的方法无法产生有效的方案时，我们专注于利用自举运算的结构。结果是，PBS 本质上由一个具有许多迭代的循环组成（想想 600-700），并且 SNARKs 上的文献已经产生了多种技术来更有效地证明这种循环，而不是天真地将其展开成一个大型电路。这些技术总结在 增量可验证计算 一词下，它允许一次证明循环迭代，而不是一次全部证明。我们使用 plonky2（它支持非常有效的递归，因此适用于此目的）实现了基于递归的 IVC 方案，并将其应用于 PBS。其工作原理如下。在每次迭代中，都会为 1) 本次迭代中的实际计算和 2) 验证前一次迭代的证明生成单个证明。在循环结束时，最终证明使验证者相信中间证明已得到正确生成和验证。

因此，我们将传统 PBS 计算的循环操作转换为统一的算术电路形式，以便可以使用 IVC 进行证明。我们调整了 TFHE 中的一些地方，使其更适合有限域上的算术电路模型。例如，我们将密文模数更改为 plonky2 本机使用的素数，并修改了密钥切换，以便可以通过外部乘积执行。这需要调整参数，但我们确保参数仍然正确且安全（目标为 128 位）。PBS 循环迭代的电路如下所示（不包括检查前一个循环证明的验证电路）：

该电路接收循环计数器和前一次迭代的结果作为输入。循环计数器值确定应用于前一次迭代结果的函数。此函数可以是简单的反循环多项式旋转（“旋转多项式”）、输入及其反循环旋转之间的密文多路复用器（“旋转多项式”+“外部乘积”）或密钥切换操作（通过“外部乘积”）。PBS 由这三个操作组成。反循环多项式旋转（“旋转多项式”）和外部乘积的子电路主导了电路的大小，从而主导了证明者的成本。有关它们如何精确实现的详细信息，请参阅论文。

正如预期的那样，使用这种基于 IVC 的实现，内存需求降低到即使是商用笔记本电脑现在也可以运行此证明器的程度。运行时间仍然相当长——在典型的 AWS 实例上，计算证明需要大约 20 分钟——但接近可以在实践中使用的程度，如下表所示。

我们还将我们的方法与通用 zkVM（Risc0 和 SP1）上的简单实现进行了比较，它们的执行速度比我们的方案至少慢两个数量级。

我们从我们的工作中得出结论，VFHE 正处于实用的边缘。我们证明了可以使用计算资源非常合理的 SNARK 证明 FHE 方案中最难的部分。虽然我们认为这是一个重要的里程碑，但这当然仅仅是个开始。有很多途径可以探索。以下是我们很想知道答案的（非详尽）问题列表：

• 我们如何将我们的证明器从 PBS 扩展到完整的 FHE 电路？
• 有没有办法改进基于 zkVM 的实现？有没有更适合我们目的的 zkVM？
• 我们可以使用基于折叠的 IVC 而不是递归获得更好的结果吗？
• 有没有其他方法可以提高我们的证明器的效率？

我们很高兴看到我们和整个社区会找到什么答案。我们相信，一个实用的 VFHE 方案将对隐私技术产生重大影响，并将释放出惠及每个人的众多应用。

附加链接

• 查看 Louis Tremblay Thibault 在 FHE Onchain 播客 上关于：使用 ZK 构建可验证 FHE 的采访。
• 阅读 ePrint 上的论文：迈向实践中的可验证 FHE：使用 plonky2 证明 TFHE 自举的正确执行。
• 观看 Michael Walter 在第 12 届零知识峰会上的演讲：迈向实践中的可验证 FHE。
• 在 Twitter 上关注 Zama，获取最新消息。

阅读更多相关帖子

未找到任何项目。

库

Concrete ↗ Concrete ML ↗ FHEVM ↗ TFHE-rs ↗

产品与服务

保护隐私的机器学习 机密区块链 阈值密钥管理系统

开发者

博客 文档 ↗ ‍ GITHUB ↗ FHE 资源 ↗ 研究论文 ↗ 赏金计划 ↗ FHE 状态操作系统

公司

关于 FHE 介绍 活动 媒体 职业 ↗ 法律

联系方式

与专家交谈 联系我们 X Discord Telegram 所有社区频道

在电子时代，隐私对于开放社会是必要的。隐私不是秘密。私事是不想让全世界知道的事情，但秘密是不想让任何人知道的事情。隐私是有选择地向世界展示自己的力量。如果双方有某种交易，那么双方都会记得他们的互动。每一方都可以谈论他们自己对这件事的记忆；谁能阻止呢？人们可以制定法律来反对它，但言论自由甚至比隐私更重要，对于一个开放的社会来说是根本的；我们不寻求限制任何言论。如果许多方在同一个论坛中一起发言，每个人都可以向所有其他人发言，并将关于个人和其他方的知识汇总在一起。电子通信的力量使这种群体言论成为可能，并且它不会仅仅因为我们可能想要它而消失。既然我们渴望隐私，我们就必须确保交易的每一方只了解该交易直接需要的知识。由于任何信息都可以被谈论，我们必须确保我们尽可能少地透露信息。在大多数情况下，个人身份并不重要。当我在商店购买杂志并将现金交给店员时，没有必要知道我是谁。当我要求我的电子邮件提供商发送和接收消息时，我的提供商不需要知道我在与谁交谈，或者我在说什么，或者其他人在对我说什么；我的提供商只需要知道如何将消息发送到那里以及我欠他们多少费用。当我的身份被交易的基础机制泄露时，我就没有隐私了。我不能在这里有选择地展示自己；我必须始终展示自己。因此，开放社会中的隐私需要匿名交易系统。到目前为止，现金一直是主要的此类系统。匿名交易系统不是秘密交易系统。匿名系统使个人能够在需要时以及仅在需要时透露自己的身份；这是隐私的本质。开放社会中的隐私也需要密码学。如果我说了一些话，我希望只有我打算让它听到的人才能听到。如果我的演讲内容对全世界开放，我就没有隐私。加密是为了表明对隐私的渴望，而使用弱密码术加密是为了表明对隐私没有太多的渴望。此外，当默认设置为匿名时，为了有保证地透露自己的身份，需要密码签名。我们不能期望政府、公司或其他大型、无面目的组织出于他们的恩惠而给予我们隐私。谈论我们对他们有利，我们应该期望他们会谈论。试图阻止他们的演讲是与信息的现实作斗争。信息不只是想自由，它渴望自由。信息会扩展到填满可用的存储空间。信息是谣言更年轻、更强大的表弟；信息比谣言跑得更快，有更多的眼睛，知道得更多，并且理解得更少。如果我们希望拥有任何隐私，我们必须捍卫我们自己的隐私。我们必须走到一起，创建允许进行匿名交易的系统。几个世纪以来，人们一直在用耳语、黑暗、信封、关着的门、秘密握手和信使来捍卫自己的隐私。过去的技术不允许强大的隐私，但电子技术允许。我们密码朋克致力于构建匿名系统。我们正在用密码学、匿名邮件转发系统、数字签名和电子货币来捍卫我们的隐私。密码朋克编写代码。我们知道必须有人编写软件来捍卫隐私，并且由于除非我们都这样做，否则我们无法获得隐私，所以我们将编写它。我们发布我们的代码，以便我们的密码朋克伙伴可以练习和使用它。我们的代码对全世界所有人免费使用。如果你不赞成我们编写的软件，我们不太关心。我们知道软件无法被销毁，并且一个广泛分散的系统无法被关闭。密码朋克谴责对密码学的监管，因为加密本质上是一种私人行为。事实上，加密行为将信息从公共领域移除。即使是反对密码学的法律也只能达到一个国家的边界和其暴力的手臂。密码学将不可避免地遍布全球，以及它所实现的匿名交易系统。为了使隐私得到广泛应用，它必须成为社会契约的一部分。人们必须走到一起，部署这些系统以造福共同利益。隐私的延伸程度仅限于社会中同伴的合作。我们密码朋克寻求你的疑问和疑虑，并希望我们能够与你互动，以便我们不会欺骗自己。但是，我们不会因为某些人可能不同意我们的目标而改变我们的路线。密码朋克正在积极致力于使网络更安全，以保护隐私。让我们一起加快步伐。前进。作者：Eric Hughes。1993 年 3 月 9 日。

• 原文链接： zama.ai/post/verifiable-...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～