ToB企服应用市场:ToB评测及商务社交产业平台

标题: 密码学承诺之原理和应用 - Kate多项式承诺 [打印本页]
作者: 海哥    时间: 2024-10-11 22:32
标题: 密码学承诺之原理和应用 - Kate多项式承诺
主页

微信公众号：密码应用技能实战
博客园首页：https://www.cnblogs.com/informatics/
GIT地址：https://github.com/warm3snow
简介

多项式承诺是一种实用性比较强的密码学承诺方案，答应一个方（承诺者）向另一个方（验证者）承诺一个多项式的值，而不泄露多项式的具体形式。在零知识证明、可验证密码共享等领域有广泛应用，常见的多项式承诺有Kate多项式承诺、FRI多项式承诺，IPA多项式承诺等。本文将重点介绍Kate多项式承诺的构造和应用。
在阅读下文之前，了解底子的密码学承诺原理和应用是非常有必要的，读者可以参考以下几篇文章：
《密码学承诺之原理和应用 - 概览》
《密码学承诺zhi原理和应用 - Sigma承诺》
《密码学承诺之原理和应用 - Pedersen承诺》
媒介

多项式

在详细介绍Kate多项式承诺之前，我们先来简单介绍一下多项式的基本概念。多项式一样平常表示为：

\[f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_dx^d = \sum_{i=0}^{d}a_ix^i\]
上述多项式中，\(a_0, a_1, a_2, ..., a_d\)是多项式系数，\(x\)是多项式的变量，\(d\)是多项式的次数(或多项式的度)。多项式的次数是指多项式中最高次幂的指数，比方上述多项式的次数为\(t\),因此上述\(f(x)\)我们也称作d次多项式。多项式系数\(a_0, a_1, a_2, ..., a_d\)是多项式的重要组成部分，它们决定了多项式的形状和性子，也是必要保护的重要信息。
多项式的值是指将变量x代入多项式后的结果，比方\(f(\beta)\)表示将\(x=\beta\)代入多项式中，计算出的结果。
多项式的根是指多项式的值为0的点，即\(f(x) = 0\)的点。
多项式有两个重要的性子：
注：在零知识证明中，通常会将要证明的题目转化为多项式表达，并通过多项式与商多项式的等式关系来进行证明。
双线性映射

在多项式承诺验证中，会用到双线性映射的概念。双线性映射（Bilinear Map）是数学中一种重要的映射，尤其在密码学和数论中有广泛的应用。它是一种特殊的函数，具有以下性子：
界说
设\(G\)是一个乘法循环群, \(g\)是一个生成元, \(G_T\)是另一个群。一个映射\(e: G \times G \rightarrow G_T\)被称为双线性映射，假如满足以下条件：
重要性子：
多项式承诺

多项式承诺重要流程如下：

以上方式的多项式承诺打开阶段是明文揭示，即承诺者直接揭示多项式\(f(x)\)，验证者重新计算多项式承诺\(C^{'} = Commit(CRS, f(x))\)，并验证\(C^{'}\)和\(C\)是否相当。
明文揭示的方式简单直接，但存在以下题目：
Kate多项式承诺

为了解决明文揭示多项式承诺存在的题目，Kate多项式承诺基于多项式点打开的方式，实现了多项式的承诺和验证。点打开方式指的是承诺者不直接揭示多项式\(f(x)\)，而是揭示多项式在某个点的值\(f(β)\)，并提供一个witness证明，验证者通过双线性映射验证多项式在β点的值是否正确。通过点打开的方式，Kate多项式承诺解决了明文揭示的题目，同时保护了多项式的隐私。
Kate多项式承诺的构造一样平常有两种方案，两种方案在安全性上有所不同：
界说上比较抽象，简单来说就是无条件隐藏通过引入随机性，使得承诺的值在计算上无法被推断出来，而计算隐藏仅使用离散对数困难性假设，使得承诺的值在计算上无法被推断出来。
计算隐藏的Kate多项式承诺

计算隐藏的Kate多项式承诺的构造如下:

[00] Setup初始化阶段

Kate多项式承诺必要初始化阶段，重要是生成和公开CRS，以及双线性映射\(e: G \times G \rightarrow G_T\)。在Kate多项式承诺中CRS如下：

\[CRS = (G, g^α, g^{α^2}, ..., g^{α^t})\]
此中，\(G\)代表乘法群，\(g\)是\(G\)的一个生成元，\(α\)是一个随机数，\(t\)是最高幂次。注：在零知识证明中，\(α\)是一个私密的值，不会公开，必要被安全销毁（通常被称为有毒废料）。
注：在Kate论文中，CRS被叫做PK，即公钥。
[01] Commit承诺阶段

承诺者计算多项式的承诺值\(C = Commit(CRS, f(x))\)，并发送\(C\)给验证者。多项式的承诺值计算方式如下：

\[C = g^{f(α)} = g^{\sum_{i=0}^{d}{a_iα^i}} = \prod_{i=0}^{d}g^{a_iα^i} = \prod_{i=0}^{d}{(g^{α^i})^{a_i}}\]
[02] CreateWitness点打开阶段

承诺者计算多项式在某个点的值\(f(β)\)，并提供一个witness证明\(w\)，此中\(w\)是多项式在β点的承诺，计算方式如下：

\[φ(x) = \frac{f(x) - f(β)}{x - β} = \sum_{i=0}^{d-1}b_ix^i\]

\[f(β) = \sum_{i=0}^{d}a_iβ^i\]

\[w = Commit(CRS, φ(x)) = g^{φ(α)} = g^{\sum_{i=0}^{d-1}{b_iα^i}} = \prod_{i=0}^{d-1}g^{b_iα^i} = \prod_{i=0}^{d-1}{(g^{α^i})^{b_i}}\]
承诺者将\((β, f(β), w)\)发送给验证者。
[03] VerifyEval点验证阶段

验证者使用双线性映射验证多项式在β点的打开值是否正确，验证方式如下：

\[e(C, g) \stackrel{?}{=} e(w, g^{α}/g^{β}) \cdot e(g, g)^{f(β)}\]
正确性验证：

\[e(w, g^{α}/g^{β}) \cdot e(g, g)^{f(β)} = e(g^{φ(α)}, g^{α-β}) \cdot e(g, g)^{f(β)} = e(g,g)^{φ(α) \cdot (α-β)+f(β)}\]
根据商多项式的界说，有：\(f(α) - f(β) = φ(α) \cdot (α-β)\)，因此：

\[e(w, g^{α}/g^{β}) \cdot e(g, g)^{f(β)} = e(g,g)^{f(α)-f(β)+f(β)}= e(g,g)^{f(α)} = e(g^{f(α)}, g) = e(C, g)\]
因此，\(e(C, g) = e(w, g^{α}/g^{β}) \cdot e(g, g)^{f(β)}\)，验证通过。
无条件隐藏的Kate多项式承诺

无条件隐藏的Kate多项式承诺构造与计算隐藏的Kate多项式承诺流程类似，区别在于：
初始化阶段

CRS的构造如下：

\[CRS = (G, g^α, g^{α^2}, ..., g^{α^t}, h, h^α, h^{α^2}, ..., h^{α^t})\]
此中，\(h\)是\(G\)的另一个生成元。
Commit承诺阶段

承诺者计算多项式的承诺值\(C = Commit(CRS, f(x))\)，计算方式如下：

\[C = g^{f(α)} \cdot h^{\hat{f(α)}}f(α) = \sum_{i=0}^{d}{a_iα^i}\hat{f(α)} = \sum_{i=0}^{d}{b_iα^i}= \prod_{i=0}^{d}{(g^{α^i})^{a_i}} \cdot \prod_{i=0}^{d}{(h^{α^i})^{b_i}}\]
CreateWitness点打开阶段

承诺者计算多项式在某个点的值\(f(β)\)，并提供一个witness证明\(w\)，计算方式如下：

\[φ(x) = \frac{f(x) - f(β)}{x - β}\hat{φ(x)} = \frac{\hat{f(x)} - \hat{f(β)}}{x - β}\]

\[w = Commit(CRS, φ(x)) \cdot Commit(CRS, \hat{φ(x)}) = g^{φ(α)} \cdot h^{\hat{φ(α)}}\]
\(g^{φ(α)}\)和\(h^{\hat{φ(α)}}\)计算方式基于CRS（方式与上文相同，略），承诺者将\((β, f(β), \hat{f(β)}, w)\)发送给验证者。
VerifyEval点验证阶段

验证者使用双线性映射验证多项式在β点的打开值是否正确，验证方式如下：

\[e(C, g) \stackrel{?}{=} e(w, g^{α}/g^{β}) \cdot e(g^{f(β)} \cdot h^{\hat{f(β)}}, g)\]
正确性验证：
\(h\)是\(G\)中的一个群元素，因此不是一样平常性可设\(h = g^\lambda\)，此中\(\lambda\)是一个随机数。因此：

\[e(w, g^{α}/g^{β}) \cdot e(g^{f(β)} \cdot h^{\hat{f(β)}}, g)= e(g^{φ(α)} \cdot h^{\hat{φ(α)}}, g^{α-β}) \cdot e(g^{f(β)} \cdot h^{\hat{f(β)}}, g)= e(g^{φ(α)+\lambda\hat{φ(α)}}, g^{α-β}) \cdot e(g^{f(β)+\lambda\hat{f(β)}}, g)= e(g,g)^{φ(α) \cdot (α-β)+\lambda\hat{φ(α)} \cdot (α-β) + f(β) + \lambda\hat{f(β)}}= e(g,g)^{φ(α) \cdot (α-β)+ f(β) + \lambda \cdot(\hat{φ(α)} \cdot (α-β) + \hat{f(β)})}\]
根据商多项式的界说，有：\(f(α) - f(β) = φ(α) \cdot (α-β)\)，\(\hat{f(α)} - \hat{f(β)} = \hat{φ(α)} \cdot (α-β)\)，因此：

\[e(w, g^{α}/g^{β}) \cdot e(g^{f(β)} \cdot h^{\hat{f(β)}}, g)= e(g,g)^{φ(α) \cdot (α-β)+ f(β) + \lambda \cdot(\hat{φ(α)} \cdot (α-β) + \hat{f(β)})}= e(g,g)^{f(α) - f(β)+ f(β) + \lambda \cdot(\hat{f(α)} - \hat{f(β)} + \hat{f(β)})}= e(g,g)^{f(α) + \lambda \cdot \hat{f(α)}}= e(g^{f(α)} \cdot g^{\lambda \cdot \hat{f(α)}}, g)= e(g^{f(α)} \cdot h^{\hat{f(α)}}, g)= e(C, g)\]
因此，\(e(C, g) = e(w, g^{α}/g^{β}) \cdot e(g^{f(β)} \cdot h^{\hat{f(β)}}, g)\)，验证通过。
结语

Kate多项式承诺是一种实用性比较强的多项式承诺方案，通过点打开的方式，可以在保护多项式隐私的同时，有效淘汰通信量。Kate多项式承诺在零知识证明、可验证密码共享等领域有广泛应用。了解Kate多项式承诺的原理和构造，对于学习zk-snarks、zk-starks等零知识证明协议是非常有帮助的。通过本文的介绍，渴望读者可以或许对Kate多项式承诺有一个初步的了解，并为进一步学习零知识证明协议打下底子。
参考文献

转载请注明原文链接：https://www.cnblogs.com/informatics/p/18456902 本文版权归作者和博客园共有，接待转载，但未经作者同意必须在文章页面给出原文连接，否则保留追究法律责任的权利。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4