学习

广播加密

定义及实现

Posted by Keeno on October 28, 2019

广播加密的定义及实现

1. 广播加密的定义

广播加密是一种提供在不安全的广播信道上向指定用户集合分发受保护的数字内容的加密机制。在广播加密系统中，广播者通过广播信道把加密后的明文广播出去，所有授权用户可以利用自己的私钥对接受的加密广播信息进行解密从而获得数字内容，而未授权用户则无法正确解密加密广播信息。

在一般的公钥加密系统中，加密者需要使用集合中各个用户的公钥对消息进行加密，比较繁琐，而通过广播加密，广播者只要通过授权用户的信息计算得到报头$Hdr$，便能够通过一次加密得到授权用户都能够解密的密文，大大提高了效率。并且由于用户的信息是初始化得到的，因此广播者可以提前进行计算，在实际广播过程中，只需要撤销(添加)未包含(包含)的用户的信息即可。

1.1 广播加密的加密原语

通常情况下，一个广播加密方案是由初始化、加密和解密三个算法组成：

$\text{Setup}(n)$：输入系统用户数量$n$，输出密钥集合${d_{1}, \ldots, d_{n}}$，分别安全地传送给对应的用户，公钥$PK$。

$\text{Encrypt}(S,PK,M)$：输入授权用户子集$S \subseteq{1, \ldots, n}$，公钥$PK$，明文$M$。算法生成$(Hdr,K)$，$Hdr$称为报头，$K \in \mathcal{K}$为用于对称加密的密钥，然后将授权用户集合$S$、报头$Hdr$、使用$K$进行加密得到的密文$C_M$通过不安全的广播信道发送给所有系统用户。

$\text{Decrypt}(S,i,d_i,Hdr,PK)$：输入授权用户子集$S \subseteq{1, \ldots, n}$，用户id $i \in {1, \dots,n}$以及对应的私钥$d_i$，报头$Hdr$，公钥$PK$。

如果$i \in S$，则该用户是授权用户，算法输出密钥$K$。然后使用这个会话密钥解密密文$C_M$，从而得到明文$M$；否则该算法失败，该用户不能解密密文。

1.2 需要满足的安全性要求

  1. 保密性：传播的广播消息是保密的，只有授权用户可以解密得到明文，而任何非法接受者仅从密文得不到任何有用的信息。（这是广播加密必须具有的属性）

  2. 正确性：对于所有$S \subseteq{1, \ldots, n}$，以及$i \in S$，如果满足：

    ①$\left(P K,\left(d_{1}, \ldots, d_{n}\right)\right) \stackrel{\mathrm{R}}{\leftarrow} \operatorname{Setup}(n)$

    ②$(\mathrm{Hdr}, K) \stackrel{\mathrm{R}}{\leftarrow} \text { Encrypt }(S, P K)$。

    那么有$\text {Decrypt }\left(S, i, d_{i}, \mathrm{Hdr}, P K\right)=K$。

  3. fully collusion resistant：此属性要求，即使是合法接受者集合外的所有非法接受者集合的任何子集的用户合谋，都不能得到关于广播消息的任何有用信息。

1.3 需要满足的效率要求

  1. stateless receiver：这条属性对系统的效率很重要，如果一个广播加密不具有stateless receiver，那么接受者集合一旦发生改变，那么就必须重新分发新的私钥。

  2. 存储代价：主要包括：1. 广播中心为了能够进行广播加密所必需存储的系统公共参数（公钥）的大小 2. 每个用户为了能够恢复加密的广播消息，所必需存储的私钥的大小。

  3. 通信代价：广播中心通过不安全的广播信道向所有系统用户发送的广播消息的报头$Hdr$大小。（会话密钥$K,C_M$一般不考虑，因为一般是恒定的大小）

  4. 计算代价：主要包括：1.广播中心计算广播消息报头$Hdr$所需的计算量。2. 用户对广播消息报头$Hdr$进行解密，恢复出会话密钥$K$所需的计算量。

2. 论文中的广播加密方案

在论文[BGW05]中，作者提出了三种广播加密的构造：

  1. 在第一种方案中，对于任意接收者的子集，密文尺寸和私钥尺寸都是恒定的（由两个群元素组成），而系统中的公钥尺寸与接受者的总数是呈线性增长的。
  2. 在第二种方案中，能够实现报头尺寸和公钥尺寸之间的权衡，第一种方案是他的一个特例。其中报头尺寸和公钥尺寸都是$O(\sqrt{n})$，私钥尺寸不变。
  3. 在第三种方案中，作者引入一个签名方案$\text { (SigKeyGen, Sign, Verify) }$和抗碰撞的哈希函数（将Verification keys映射到 $ \mathbb{Z}_ {p}$），在标准模型中（没有使用随机谕言机）得到了一个CCA安全的广播加密系统。

2.1 安全性基于的难度假设

BDHE(bilinear Diffie-Hellman Exponent assumption) assumption：

令$\mathbb{G}$为一个素数$p$阶的双线性群。$\mathbb{G}$中的$\ell-\mathrm{BDHE}$问题是指，给定一个包含$2\ell+1$个元素的向量$\left(h, g, g^{\alpha}, g^{\left(\alpha^{2}\right)}, \ldots, g^{\left(\alpha^{\ell}\right)}, g^{\left(\alpha^{\ell+2}\right)}, \ldots, g^{\left(\alpha^{2 \ell}\right)}\right) \in \mathbb{G}^{2 \ell+1}$，计算$e(g, h)^{a^{(l+1)}}$。（由于向量中缺乏$g^{\alpha^{(\ell+1)}}$,因此双线性映射无法帮助计算）

Decision BDHE problem：

定义素数$p$阶的群$\mathbb{G}$，$\mathbb{G_T}$，以及满足的双线性映射$e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_ {T}$，令$g,h$为$\mathbb{G}$的生成元，$a\stackrel{R}{\leftarrow} \mathbb{Z}_ {p}^{* }$，$b \stackrel{R}{\leftarrow}{0,1}$。如果$b=0$，那么设$Z \leftarrow e(g, h)^{a^{l+1}}$。如果$b=1$，那么设$Z \stackrel{R}{\leftarrow} \mathbb{G}_ {T}$。给定一个$Z$以及$\left(h, g, g^{\alpha}, g^{\left(\alpha^{2}\right)}, \ldots, g^{\left(\alpha^{\ell}\right)}, g^{\left(\alpha^{\ell+2}\right)}, \ldots, g^{\left(\alpha^{2 \ell}\right)}\right) \in \mathbb{G}^{2 \ell+1}$，攻击者判定$b=0\ or\ b=1$。

2.2 特例1

一个针对$n$个用户的广播加密系统，其中密文和私钥尺寸是恒定的，公钥随着系统中用户数量线性增长。

此方案包含以下三个算法：

$\text{Setup}(n)$：

  1. 输入系统中用户数量$n$，定义$p$阶的双线性群$\mathbb{G}$。选择一个随机的生成元$g \in \mathbb{G}$，和随机数$\alpha \in \mathbb{Z}_ {p}$。对$i=1,2, \ldots, n, n+2, \ldots, 2 n$，计算$g_{i}=g^{\left(\alpha^{i}\right)} \in \mathbb{G}$。

  2. 选择一个$\gamma \in \mathbb{Z}_ {p}$，并定义$v=g^{\gamma} \in \mathbb{G}$。输出公钥$P K=\left(g, g_{1}, \ldots, g_{n}, g_{n+2}, \ldots, g_{2 n}, v\right) \in \mathbb{G}^{2 n+1}$。

  3. 对于系统中的用户$i \in{1, \ldots, n}$，输出各自的私钥$SK=d_{i}=g_{i}^{\gamma} \in \mathbb{G}$。

$\text{Encrypt}(S,PK,M)$：

  1. 输入公钥$PK$，授权集合$S$，明文$M$。

  2. 从$ \mathbb{Z}_ {p} $中随机选择一个$t$，定义会话密钥$K=e\left(g_{n+1}, g\right)^{t} \in \mathbb{G}$。

  3. 输出报头$\mathrm{Hdr}=\left(g^{t},\left(v \cdot \prod_{j \in S} g_{n+1-j}\right)^{t}\right) \in \mathbb{G}^{2}$，和使用$K$进行对称加密得到的密文$C_M$。

$\text Decrypt\left(S, i, d_{i}, \mathrm{Hdr}, PK, C_M\right)$：

  1. 输入$\mathrm{Hdr}=\left(C_{0}, C_{1}\right)$，公钥$PK$。

  2. 授权集合$S$中的用户可利用各自的私钥$(i,d_i)$计算并输出会话密钥$K=e\left(g_{i}, C_{1}\right) / e\left(d_{i} \cdot \prod_{j \in S \atop j \neq i} g_{n+1-j+i}, \quad C_{0}\right)$，并使用$K$对密文$C_M$进行解密得到明文$M$。

效率分析：

在本方案中，私钥$d_i$是一个群元素，报头$Hdr$只包含两个群元素。由于$e\left(g_{n+1}, g\right)$能够被提前计算，因此加密阶段可以不需要配对计算。但是在本方案中，公钥的尺寸随着系统中用户数量线性增长。

2.3 通用构造

因此作者提出了一种能够权衡公钥与报头尺寸的通用构造方案，使得报头与公钥尺寸都是随着系统中用户数量亚线性增长的。

主要思路：

将广播加密系统划分成$A$个实例，每个实例都能够广播给最多$B$个用户，从而得到一个支持$n=AB$个用户的广播加密系统。（当$B=n$时，系统就是第一种方案）不同实例中的用户都共用同样的公钥$ PK=\left(g, g_{1}, \ldots, g_{B}, g_{B+2}, \ldots, g_{2 B}\right) $。

此方案包含以下三个算法：

$\text{Setup}(n)$：

  1. 输入系统中用户数量$n$，该算法会生成$A=\left\lceil\frac{n}{B}\right\rceil$个实例，每个实例中包含$B$位用户。

  2. 定义$p$阶的双线性群$\mathbb{G}$。该算法首先选择一个随机的生成元$g \in \mathbb{G}$，和随机数$\alpha \in \mathbb{Z}_ {p}$。

  3. 对$i=1,2, \ldots, B, B+2, \ldots, 2B$，计算$g_{i}=g^{\left(\alpha^{i}\right)} \in \mathbb{G}$。接着，算法随机选择$\gamma_{1}, \dots, \gamma_{A} \in \mathbb{Z}_ {p}$，并定义$v_{1}=g^{\gamma_{1}}, \ldots, v_{A}=g^{\gamma_{A}} \in \mathbb{G}$。

  4. 对于系统中的用户$i \in{1, \ldots, n}$，将$i$表示为$ i=(a-1) B+b\ (1≤a≤A,1≤b≤B)$，即有$a=\lceil i / B \rceil$，$b=i\ mod\ B$，用户$i$的私钥为$d_i=g_b^{\gamma_a}\in \mathbb G$。

  5. 算法输出公钥$P K=\left(g, g_{1}, \ldots, g_{B}, g_{B+2}, \ldots, g_{2 B}, v_{1}, \ldots, v_{A}\right) \in \mathbb{G}^{2 B+A}$，各自的私钥$d_1 \ldots d_n $。

$\text{Encrypt}(S,PK,M)$：

  1. 对于各个实例$\ell=1, \ldots, A$，定义$\hat{S}_ {\ell}=S \cap{(\ell-1) B+1, \ldots, \ell B}$，$ S_{\ell}={x-\ell B+B | x \in \hat{S}_ {\ell}} \subseteq{1, \ldots, B}$。$\hat{S}_ \ell$指$S$中索引在$B(\ell-1)-B\ell$之间的用户集合，$S_{\ell}$将$\hat{S}_ \ell$中用户的索引映射到区间${1, \dots ,B}$。

  2. 定义会话密钥$K=e\left(g_{B+1}, g\right)^{t} \in \mathbb{G}$。

  3. 输出报头$\mathrm{Hdr}=\left(g^{t},\left(v_{1} \cdot \prod_{j \in S_{1}} g_{B+1-j}\right)^{t}, \ldots,\left(v_{A} \cdot \prod_{j \in S_{A}} g_{B+1-j}\right)^{t}\right) \in \mathbb{G}^{A+1}$，和使用$K$进行对称加密得到的密文$C_M$。

$\text Decrypt\left(S, i, d_{i}, \mathrm{Hdr}, PK, C_M\right)$：

  1. 输入$\mathrm{Hdr}=\left(C_{0}, C_{1},\dots ,C_{A}\right)$，公钥$PK$。

  2. 授权集合$S$中的用户$i=(a-1)B+b$可利用私钥$(i,d_i)$计算并输出会话密钥$K=e\left(g_{b}, C_{a}\right) / e\left(d_{i} \cdot \prod_{j \in S_{a} \atop j \neq b} g_{B+1-j+b}, C_{0}\right)$，并使用$K$对密文$C_M$进行解密得到明文$M$。

效率分析：

在本方案中，私钥$d_i$仍是一个群元素，报头$Hdr$包含了$A+1$个群元素，而公钥尺寸从$2n+1$减为$2B+A$。在系统中用户较多时，能够在略微降低分发$Hdr$效率的情况下，极大的提高公钥分发的效率。

2.4 CCA安全的广播加密

上述的两个方案无法抵抗选择密文攻击。作者提出可以通过结合一个签名方案$(\text {SigKeyGen}, \text {Sign}, \text {Verify})$，和一个抗碰撞的哈希函数，将验证密钥映射到$\mathbb Z_p$中，能够得到一个不需要使用随机谕言机的CCA安全的广播加密系统。

相比较于上述两种方案，第三种方案在加密和解密算法中进行了修改，添加了签名与验证的操作。

$\text{Encrypt}(S,PK,M)$：

  1. 输入公钥$PK$，授权集合$S$，明文$M$。从$ \mathbb{Z}_ {p} $中随机选择一个$t$，定义会话密钥$K=e\left(g_{n+1}, g\right)^{t} \in \mathbb{G}$。

  2. 运行$SigKeyGen$算法获得签名密钥$K_{\mathrm{SIG}}$和验证密钥$V_ {\mathrm{SIG}} \in \mathbb{Z}_ {p}$。

  3. 定义$C=\left(g^{t},\left(v \cdot g_{1}^{V_{\mathrm{SIG}}} \cdot \prod_{j \in S} g_{n+1-j}\right)^{t}\right) \in \mathbb{G}^{2}$，$\mathrm{Hdr}=\left(C,{Sign}\left(C, K_{\mathrm{SIG}}\right), V_{\mathrm{SIG}}\right)$，输出$(Hdr,K)$。

$\text Decrypt\left(S, i, d_{i}, \mathrm{Hdr}, PK, C_M\right)$：令$\mathrm{Hdr}=\left(\left(C_{0}, C_{1}\right), \sigma, V_{\mathrm{SIG}}\right)$。

  1. 验证$\sigma$是$(C_0,C_1)$在验证密钥$V_{\mathrm{SIG}}$下的有效签名，如果验证失败输出$?$。
  2. 随机选择$w \in \mathbb{Z}_ {p}$，计算$\hat{d}_ {0}=\left(d_{i} \cdot g_{i+1}^{V_{\mathrm{SIG}}} \cdot \prod_{j \in S \atop j \neq i} g_{n+1-j+i}\right) \cdot\left(v \cdot g_{1}^{V_{\mathrm{SIG}}} \cdot \prod_{j \in S} g_{n+1-j}\right)^{w}$ 以及$\hat{d}_ {1}=g_{i} g^{w}$。
  3. 计算会话密钥$K=e\left(\hat{d}_ {1}, C_{1}\right) / e\left(\hat{d}_ {0}, C_{0}\right)$，并输出。

效率分析：

在本方案中，私钥尺寸和报头尺寸没有变化，但由于在解密阶段为了安全性证明引入了随机值$w$，因此解密速度降低了2倍。

CATALOG
    FEATURED TAGS
    学习
    FRIENDS