WE-KZG：加密到KZG - ZKSECURITY

你能创建一个密文，如果多项式承诺中的多项式具有特定的求值结果，该密文就可以被解密吗？ 是的，而且事实证明这并不复杂……

今天，我们将看看我们最近在Asiacrypt 2024上发表的论文中的构造， 它使得标准的KZG承诺能够做到这一点。 所以，一起来探索KZG承诺的见证加密世界吧。

见证加密 (WE) 简介

在公钥加密方案中，有两种类型的密钥：公钥和私钥。 加密使用公钥和消息并生成密文：

ct←Enc(pk,msg)

而解密需要私钥：

msg←Dec(sk,ct)

在不知道私钥的情况下，密文会隐藏消息。

见证加密与之类似， 但“公钥”是一个陈述 x，而私钥是该陈述的见证 w（“它为真的原因”）， 而不是让 (pk,sk)←KeyGen() 算法生成公钥/私钥。 即 (x,w)∈R。 这意味着你可以“加密”到陈述，而无需知道见证，甚至不知道陈述是否为真。

例如，你可以加密到如下的陈述/关系：

加密到数独：w 是数独谜题 x 的解。

加密到哈希：w 是 SHA3 哈希 x 的原像，即 SHA3(w)=x。

从技术上讲，我们要求的是可提取的见证加密， 其中，不仅 x 在语言中（例如，数独谜题有解）， 而且解密者被保证知道见证 w（例如，数独解）。

从标准假设出发，所有 NP 问题的见证加密仍在研究中， 但我们可以有效地为特定语言构造它， 今天我们将展示 如何为一个特定的语言构造一个见证加密方案， 即 KZG 承诺的打开证明：

R={(x=(com,x,y),w=π)∣Verify(com,x,y,π)=1}

换句话说：你可以加密到一个 KZG 承诺和一个 “求值声明” (com,x,y)， 只有当解密者知道一个有效的 KZG 打开证明 π 时才能解密，即承诺“内部”的多项式在 x 处的值为 y。

KZG 打开的见证加密

这个构造实际上非常简单（而且非常优雅）， 尽管安全性证明更为复杂。 让我们简要回顾一下基于配对的 KZG 承诺方案是如何工作的：

1. 设置：设置包括 “tau 的幂”： ([τ]2,[τ]1,[τ2]1,[τ3]1,…,[τd]1) 我们使用 [v]1 表示 v=G1v，其中 G1 是 G1 的生成元； 使用 [v]2 表示 v=G2v，其中 G2 是 G2 的生成元。

2. 承诺：通过在 τ 处同态地评估多项式 f(X) 来形成承诺：

   f(X)=∑i=0dfiXi
   com=f(τ)=∑i=0d[fi⋅τi]1=∑i=0dfi⋅[τi]1

   其本质是 Swartz-Zippel + τ 的 “加密”： 为了找到承诺之间的冲突，他必须找到在 τ 处一致的两个多项式—— 但这很难，因为 指数运算 [τi]1=G1v 隐藏了求值点 τ。

3. 打开：在 x 处打开到 y 通过承诺于商多项式来完成：

   g(X)=f(X)−yX−x
   π←Commit(g)

   这源于一个简单的观察，如果 f(x)=y，则 f(x)−y=0，即 f(X)−y 在 x 处有一个根。这等价于 (X−x) 整除 f(X)−y。 所以，当且仅当 f(x)=y 时，g(X) 是一个多项式（而不是一个有理函数）。

4. 验证：配对可以被用来将已承诺的多项式与 1 次多项式相乘。 这被用来 “乘出” 商多项式的分母并检查相等性。 具体来说，验证者检查：

e(π,[τ]2−[x]2)=e(com−y,[1]2)

这里 [τ]2−[x]2 是第 2 组中 1 次多项式 X−x 的承诺。

加密时刻！

构建 KZG 承诺的见证加密的技巧是查看最终的验证等式，并尝试随机化等式的一侧。 验证等式是：

e(π,[τ]2−[x]2)=e(com−y,[1]2)

如果我们选择 r∈Zp 并将两侧都提升到 r 次方，则关系仍然成立：

e(π,[τ]2−[x]2)r=e(com−y,[1]2)r

我们可以将指数移到配对内部：

e(π,r⋅([τ]2−[x]2))=e(com−y,[r]2)

为了构建公钥加密， 观察到的情况是，加密者可以选择 r 并在不知道 π 的情况下计算绿色部分。 与此同时，即使你得到 s=r⋅([τ]2 - [x]2)∈G2，在不知道 π 的情况下计算红色部分也很难。 我们在论文中表明，找到 π st. e(π,s)=e(com−y,[r]2) 相当于计算 KZG 打开证明 在一个叫做 “代数群模型” AGM 的模型中，这个模型通常被用来证明 KZG 承诺本身的可提取性。

把所有东西放在一起，我们可以如下构造加密方案：

加密：

1. 选择一个随机 r∈Zp。
2. 计算 s←r⋅([τ]2−[x]2)。
3. 计算 k←Hash(e(com−y,[r]2)) 以获得对称密钥 k。
4. 用对称密钥 k 加密消息 msg：c=Enck(msg)。
5. 输出 ct=(s,c)。

解密：

1. 像往常一样计算 KZG 打开证明 π。
2. 计算 k←Hash(e(π,s))。
3. 用对称密钥 k 解密密文 c：msg=Deck(c)。
4. 输出 msg。

正如你所看到的，从/到 KZG 开放的加密和解密的成本与 KZG 本身的成本基本相同。 即使该方案非常简单，但仍有一些或多或少令人惊讶的应用。 也许你可以自己想出一些？

让我们看一个简单的例子。

应用：简洁的茫然传输

在茫然传输 (OT) 协议中，有两方：发送方和接收方。 发送方有两条消息 m0 和 m1， 接收方有一个比特 b∈{0,1}。 目标是让接收方了解他选择的消息 mb，而无需让发送方了解 b， 或者让接收方了解另一条消息 m1−b。 基本上是一个“选择二选一消息而不告诉我的协议”。

茫然传输在安全多方计算的上下文中特别有用。

简洁的茫然传输是茫然传输 (OT) 的一种变体，但通信复杂度降低了： 接收方（图中的 Bob）可以使用一个非常短的承诺 com 来提交许多不同的选择 b1,b2,…,bn∈{0,1}。 然后，发送方（图中的 Alice）可以将消息 m0,m1 加密到任何位置 i， 以便 Bob 只能了解 mbi，而 Alice 不会了解 bi。 有了我们新的 KZG 见证加密方案，我们可以轻松地构造一个高效的简洁 OT 协议，如下所示：

• 承诺：Bob 插值一个多项式 f(X)，使得 f(i)=bi。 然后，他使用一个 KZG 承诺 com 来承诺多项式 f(X)。

• 加密：Alice 使用 KZG 见证加密方案来加密 m0 和 m1 到 x=(com,i,0) 和 x=(com,i,1) 分别。 获得密文 ct0 和 ct1， 对应于 f(i)=0 和 f(i)=1 这两个矛盾的声明。

• 解密：Bob 可以计算求值 f(i)=bi 的 KZG 开放证明 π。 使用 KZG 开放，他可以解密密文 ctbi 以获得 mbi。 如果他可以解密另一个密文 ct1−bi，他将打破承诺的绑定性。

在论文中， 我们观察到这个简单的方案实际上与最先进的简洁 OT 协议非常有竞争力。 特别是通信复杂度非常低。

结论

我们研究了什么是见证加密，以及如何有效地为 KZG 开放的语言构造它。 简洁的 OT 方案已经 被实施和基准测试，该代码可在此处公开获得here。 如果你有兴趣了解更多关于这些主题的信息， 我的一个合著者在 Ethereum Privacy & Scaling Explorations 的学习俱乐部做了一个演讲：

<iframe src="https://www.youtube.com/embed/81Hq7Ij94vE?autoplay=0&controls=1&end=0&loop=0&mute=0&start=0"></iframe>

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