本文介绍了一种基于KZG承诺的见证加密(Witness Encryption, WE)方案。该方案允许对KZG承诺和评估声明进行加密,只有掌握有效KZG opening proof π的解密者才能解密,即只有知道承诺中多项式在某点的值时才能解密。此外,还介绍了一个基于该WE方案的高效简洁的茫然传输(Laconic Oblivious Transfer, LOT)协议。
你能创建一个密文,如果多项式承诺中的多项式具有特定的求值结果,该密文就可以被解密吗? 是的,而且事实证明这并不复杂……
今天,我们将看看我们最近在Asiacrypt 2024上发表的论文中的构造, 它使得标准的KZG承诺能够做到这一点。 所以,一起来探索KZG承诺的见证加密世界吧。
在公钥加密方案中,有两种类型的密钥:公钥和私钥。 加密使用公钥和消息并生成密文:
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 承诺方案是如何工作的:
设置:设置包括 “tau 的幂”: ([τ]2,[τ]1,[τ2]1,[τ3]1,…,[τd]1) 我们使用 [v]1 表示 v=G1v,其中 G1 是 G1 的生成元; 使用 [v]2 表示 v=G2v,其中 G2 是 G2 的生成元。
承诺:通过在 τ 处同态地评估多项式 f(X) 来形成承诺:
f(X)=∑i=0dfiXi
com=f(τ)=∑i=0d[fi⋅τi]1=∑i=0dfi⋅[τi]1
其本质是 Swartz-Zippel + τ 的 “加密”: 为了找到承诺之间的冲突,他必须找到在 τ 处一致的两个多项式—— 但这很难,因为 指数运算 [τi]1=G1v 隐藏了求值点 τ。
打开:在 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) 是一个多项式(而不是一个有理函数)。
验证:配对可以被用来将已承诺的多项式与 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 承诺本身的可提取性。
把所有东西放在一起,我们可以如下构造加密方案:
加密:
解密:
正如你所看到的,从/到 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 助手,为大家转译优秀英文文章,如有翻译不通的地方,还请包涵~
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!