多项式
本文适合有一定的数学基础的人进行阅读，有很多基础概念不会在本文中详细介绍，如多项式的次数、系数、项、一元多项式、多元多项式等特别基础的概念。本文主要讨论一元多项式。
多项式有不少核心性质，如运算封闭性、因式分解、插值与近似、求导与积分等。
本文主要关注其在密码学中的性质以及应用。接下来直接上干货。
系数表示形式
定义在域$F$上的$n-1$次多项式的系数表示：
$$f(x)=a_0+a_1x+a2x^2+...+a{n-1}x^{n-1}$$
点的表示形式
假设有$n$个不同的点$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$，那么根据拉格朗日插值法，该多项式式可以表示为：
$$f(x)=y_1\ast h_1(x)+y_2\ast h_2(x)+...+y_n\ast h_n(x)$$
其中：
$$
\begin{aligned}
h_1(x)&=\frac{(x-x_2)(x-x_3)...(x-x_n)}{(x_1-x_2)(x_1-x_3)...(x_1-x_n)} \
\dots\
h_i(x)&=\frac{(x-x_1)(x-x2)...(x-x{i-1})(x-x_{i+1})...(x-x_n)}{(x_i-x_1)(x_i-x_2)...(xi-x{i-1})(xi-x{i+1})...(x_i-x_n)} \
\dots \
h_n(x)&=\frac{(x-x_1)(x-x2)...(x-x{n-1})}{(x_n-x_1)(x_n-x_2)...(xn-x{n-1})}
\end{aligned}
$$
点的表示形式说明如果一个$n-1$次多项式有$n$个不同点，那么该多项式可以通过拉格朗日插值法唯一的表示出来。这种形式比较简单写出，只不过在计算多项式在某个点的值的时候，计算复杂度比较高。
用途
纠错码、信息论编码、同态加密、秘密分享、零知识证明、多方安全计算等。
BLS 签名
双线性映射
双线性映射是现代密码学（尤其是椭圆曲线密码学）中的核心工具，其本质是一种同时对两个输入参数满足线性性质的映射。它在密码协议设计（如密钥交换、数字签名、属性基加密、零知识证明等）中具有不可替代的作用。以下从定义、性质、分类、构造及应用等方面展开简单介绍。
- 数学定义
- 双线性（Bilinearity）：\
对任意 $P, Q \in G_1$，$R, S \in G_2$，$a, b \in \mathbb{Z}_p$，有：$e(aP, bQ) = e(P, Q)^{ab}, \quad e(P+Q, R) = e(P, R) \cdot e(Q, R), \quad e(P, R+S) = e(P, R) \cdot e(P, S)$
- 非退化性（Non-degeneracy）：\
存在 $P \in G_1, Q \in G2$，使得 $e(P, Q) \neq 1{GT}$（$1{G_T}$ 为 $G_T$ 的单位元）。
- 可计算性（Efficiency）：\
存在高效算法计算 $e(P, Q)$ 的值。
- 变种
- 对称双线性映射：\
当 $G_1 = G_2$ 时，称为对称双线性映射（如部分椭圆曲线配对）。
- 非对称双线性映射：\
当 $G_1 \neq G_2$ 时（如 $G_1$ 为椭圆曲线点群，$G_2$ 为其对偶群），应用更灵活。
- 经典构造
- Weil 配对（Weil Pairing）
- ate 配对（Tate Pairing）及改进版
- 配对友好型椭圆曲线
- BN 曲线（Barreto-Naehrig 曲线）：\
满足 $p = 36m + 31$ 等形式，用于构建对称双线性映射。
- BLS 曲线（Boneh-Lynn-Shacham 曲线）：\
支持非对称配对，广泛应用于短签名和聚合签名。
bls 签名流程
接下来直接上干货
- 密钥生成算法 $Gen$ ：\
$g_1,g_2$ 分别是 $G_1,G_2$ 的生成元。随机选择 $sk\leftarrow[1,p-1]$ 作为私钥，计算 $pk=g_2^{sk}$ 作为公钥，公私钥对记为 $(sk,pk)$。
- 签名算法 $Sign$ ：\
假设 $m$ 是一个要签名的消息，计算 $h=H(m)$，那么签名 $\sigma=h^{sk}$。
- 验证算法 $Verify$ ：\
使用双线性配对，验证 $e(\sigma,g_2)=e(h,pk)$ 是否成立？
阈值组签名以及分布式密钥生成算法 DKG
参数设置
$t$ 为阈值，$n$ 为参与者个数，不妨将他们的编号设置为 $1,2,\dots,n$，一般 $t\ge n/2+1$。这里不妨假设 $G_1=G_2$，生成元 $g$ 。
也就是说组内有 $n$ 个参与者，每个人都有自己得公私钥对，都可以对某一个特定的消息进行签名，搜集这些签名，只要是能搜集到至少 $t$ 个签名就能恢复出阈值组签名，且能通过组公钥的验证。这个方案可以应用于带有阈值的场景，也可以应用于可验证的伪随机数生成，可以应用到区块链的共识机制中。
广播多项式系数承诺并生成公私钥对
- 对于参与者 $P_i$ ，随机选择一个 $(t-1)$ 次多项式
$$ fi(x)=a{i0}+a{i1}x+a{i2}x^2+\dots+a_{i,t-1}x^{t-1}
$$
多项式系数需要保密，这样每个参与者都拥有一个保密的多项式。
- 计算系数承诺
$$
A{i0}=g^{a{i0}},\dots,A{i,t-1}=g^{a{i,t-1}}
$$
并广播出去。
-
计算各自的公私钥对 \
比如 $P_1$, 先秘密的接收其他参与方发来的 $f_2(1),\dots,f_n(1)$，并验证是否有效，验证方法：验证 $g^{fi(1)}=A{i0}(A_{i1})^1\dots(A_{i,t-1})^{1^{t-1}}$ 是否成立，于是 $P_1$ 的 $sk_1=f_1(1)+f_2(1)+\dots+f_n(1))$ ，公钥是 $pk_1=g^{sk_1}$ 。\
\
比如 $P_2$ ，先秘密的接收其他参与方发来的 $f_1(2),\dots,f_n(2)$ ，并验证是否有效，验证方法：验证 $g^{fi(2)}=A{i0}(A{i1})^2\dots(A{i,t-1})^{2^{t-1}}$ 是否成立，于是 $P_2$ 的 $sk_2=f_1(2)+f_2(2)+\dots+f_n(2))$ ，公钥是 $pk_2=g^{sk_2}$。
公钥不用广播了，根据多项式承诺本地就可以去计算出来，计算公式如下：
$$
\begin{aligned}
pk_i &=g^{f_1(i)+f_2(i)+\dots+f_n(i)} \
&=g^{f_1(i)}\ast g^{f_2(i)}\ast \dots\ast g^{fn(i)} \
&=(A{10}\ast \dots\ast A{n0})\ast (A{11}\ast \dots\ast A{n1})^{i^1}\ast \dots\ast (A{1,t-1}\ast \dots\ast A_{n,t- 1})^{i^{t-1}} \
\end{aligned}
$$
参与方生成签名分片
对于参与方$P_i$ 计算$\sigma_i=H(m)^{sk_i}$作为签名。并广播出去。
恢复组签名
任意参与方都可以去搜集其他参与方的签名分片，一旦搜集到 $t$ 个签名分片，就可以恢复出组签名。比如说搜集到了编号为 $1,2,\dots,t$ 参与者的签名分片 $\sigma_1,\sigma_2,\dots,\sigma_t$。
对应的私钥为 $sk_1,\dots,sk_t$ ，记 $F(x)=f_1(x)+,\dots,+f_n(x)$ ，于是满足 $F(i)=sk_i,i=1,\dots,t$ ，根据拉个朗日插值法有 $F(x)=sk_1h_1(x)+,\dots,+sk_th_t(x)$ ，其中 $h_i(x)$ 是插值多项式，这里不再详细展示。
组签名
$$
\begin{aligned}
\sigma&=H(m)^{F(0)}\
&=H(m)^{sk_1h_1(0)+,\dots,+sk_th_t(0)}\
&=\sigma_1^{h_1(0)}\sigma_2^{h_2(0)}\dots,\sigma_t^{ht(t)}
\end{aligned}
$$
组公钥 $pk=g^{F(0)}=A{10},\dots,*A_{n0}$
验证 $e(\sigma,g)==e(H(m),pk)$
以上就是组签名的推导过程。下次准备讲一讲快速傅里叶变换（FTT）。
