广播加密与非零内积加密方案调研

调研论文列表

论文标题	作者	出处	标注
Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys	Dan Boneh, Craig Gentry, Brent Waters	CRYPTO 2005, CCF A	[1]
Non-zero Inner Product Encryption with Short Ciphertexts and Private Keys	Jie Chen et al.	SCN 2016, CCF C	[2]

本周工作

Boneh-Gentry-Waters 广播加密方案

[1] 中构造了密文密钥都是常数级的广播加密方案，大致构造如下：

$$\begin{aligned} \mathsf{mpk} &: [1, a^1,a^2,\cdots,a^n,a^{n+2},\cdots,a^{2n}, \mu]_{1,2} \\ \mathsf{msk} &: a^1,a^2, \cdots, a^n, a^{n+2},\cdots, a^{2n},\mu \\ \mathsf{sk}_i &: [\mu a^i]_1 \\ \mathsf{ct}_{\mathsf{m}, S} &: [t,t(\mu+\sum_{j\in S}a^{n+1-j})]_2,\quad \mathsf{m}\cdot [ta^{n+1}]_T \end{aligned}$$

解密原理：

解密主要使用下面这个等式：

$$a^i \sum_{j\in S} a^{n+1-j} = \sum_{j\in S, j\neq i}a^{n+1-j+i} +a^{n+1}$$

构造思路：

可以这样理解这个构造：在解密时，需要计算出一个满足如下要求的关于 $\alpha$ 的多项式 $f(\alpha)$：

• 每项的系数都已知
• $n+1$ 次项的系数不为 $0$
• 能用两个不含 $n+1$ 次项的多项式计算出

对于广播集合 $S$ 与任意 $i\in S$，只需要使用 $\alpha^i$ 与 $\sum{j\in S} \alpha^{n+1-j}$ 相乘，就能计算出满足上述要求的多项式。为了安全性，会改成使用 $[\mu \alpha^i]_1$、$[t(\mu+\sum{j\in S}\alpha^{n+1-j})]_2$、$[t]_2$ 和 $a^i$ 四项算出 $[t\cdot f(\alpha)]_T$，从而得到 $[t\alpha^{n+1}]_T$。

非零内积加密（Non-Zero IPE）构造

如果要构造一个 Non-Zero IPE，可以使用相同的思路。注意到上面提到的多项式的第二个要求正好和 Non-Zero IPE 的正确性要求相吻合，所以不妨令最后计算出的多项式的 $n+1$ 次项的系数是 $\langle \vec{x}, \vec{y}\rangle$。注意到：

$$\begin{aligned} \langle \vec{x}, \vec{y}\rangle \alpha^{n+1} &= \alpha^{n+1} \sum_{i} x_i y_i \\ &= \sum_i (x_i \alpha^i) \cdot (y_i \alpha^{n+1-i}) \end{aligned}$$

因此，可以使用 $\sum_i x_i \alpha^i$ 和 $\sum_i y_i \alpha^{n+1-i}$ 计算出满足要求的多项式。与上面的广播加密类似，密钥构造为 $[\mu\sum_i x_i \alpha^i]_1$，密文中嵌入 $[t]_2, [t(\mu+\sum_i y_i \alpha^{n+1-i})]_2$，从而得到下面的 Non-Zero IPE：

$$\begin{aligned} \mathsf{mpk} &: [1, a^1,a^2,\cdots,a^n,a^{n+2},\cdots,a^{2n}, \mu]_{1,2} \\ \mathsf{msk} &: a^1,a^2, \cdots, a^n, a^{n+2},\cdots, a^{2n},\mu \\ \mathsf{sk}_{\vec{x}} &: [\mu\sum_i x_i \alpha^i]_1 \\ \mathsf{ct}_{\mathsf{m}, \vec{y}} &: [t,t(\mu+\sum_i y_i \alpha^{n+1-i})]_2,\quad \mathsf{m}\cdot [ta^{n+1}]_T \end{aligned}$$

这正是 [2] 中给出的 Non-Zero IPE 方案，密文和密钥都做到了常数级。

开放问题

师兄之前说这个方案好像能改造成标准的 IPE，但我现在还不知道怎么做。因为方案里计算 $[t\alpha^{n+1}]_T$ 就是要对 $[t\langle \vec{x}, \vec{y}\rangle\alpha^{n+1}]_T$ 开 $\langle \vec{x}, \vec{y}\rangle$ 次方，换成标准 IPE 的话该怎么处理，我还没想出来。

下周计划

• 了解基于配对的经典广播加密方案

参考文献

[1] Dan Boneh, Craig Gentry, Brent Waters. Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys. CRYPTO 2005.

[2] Jie Chen et al. Non-zero Inner Product Encryption with Short Ciphertexts and Private Keys. SCN 2016.