云存储中具有用户撤销功能的公共审计密钥暴露保护

摘要

随着云数据存储的发展，越来越多的数据拥有者选择将数据存储在云中并以组的形式进行共享。为了保护共享数据的完整性，数据在存储到云之前会被签名。当某个用户被从组中撤销后，云可以通过将被撤销用户的签名转换为现有组成员的签名来保持撤销的效率。因此，公共审计应由第三方审计员使用现有组成员的公钥来进行。作为一个基本的安全要求，即使云服务器获得了被撤销用户的私钥，也不应知晓现有组成员的私钥。
本文提出了一种新的公共审计协议，使得即使部分共享数据已被云重新签名，公共验证者仍能够对其完整性进行审计。通过结合代理重签名与随机掩码技术，该新公共审计协议满足了这一基本安全要求。此外，我们证明了该新协议的安全性，并最终将其与其他现有的公共审计协议进行了比较，结果表明，该新机制在不损失通信和计算效率的前提下，为现有的共享数据公共审计协议提供了良好的密钥暴露保护。

关键词

公共审计 · 共享数据 · 云存储 · 用户撤销 · 密钥暴露保护

1 引言

云数据存储允许数据拥有者将数据从本地计算系统迁移到云中。云数据存储服务包含三个不同的参与者，即云服务器、第三方审计员（TPA）和用户。云服务器拥有充足的存储空间，为用户提供数据存储和共享服务。第三方审计员（TPA）能够根据用户的请求提供数据审计服务，而无需下载整个文件。云用户将大量数据或文件存储在云服务器上。在一个组中，存在两种类型的用户：创建共享数据的原始用户，以及可以访问和修改该数据的多个组用户。
共享数据进一步被划分为多个数据块。
与昂贵的基础设施建设、大型设备和日常维护成本的初期投入不同，数据拥有者只需为其实际使用的存储空间付费，例如按存储每千兆字节计费模型。此外，数据拥有者可以依赖云随时随地访问数据。越来越多的数据拥有者选择将数据存储在云中。当原始组用户创建共享数据并将其存储在云服务器上后，每个组用户都可以访问和修改共享数据，从而能够与组内其他成员共享最新版本的共享数据。为了保护共享数据的完整性，所有数据（包括由原始组用户创建的数据以及由不同组用户修改的数据）在存储到云服务器之前都必须进行签名。因此，由于不同用户对数据进行了修改，不同的数据块由不同的用户签名。
由于每个数据块均由一个组用户签名，公共验证者（如第三方审计员（TPA））可以在无需下载全部数据的情况下检查云中的数据完整性，这被称为公共审计。公共审计允许在不完全下载数据的情况下公开检查数据完整性。阿特尼塞等人[1]首次提出了可证明数据持有（PDP）模型，该模型允许验证者使用基于RSA的同态认证器对存储在不可信存储中的客户端数据的正确性进行公开检查。随后，阿特尼塞等人[2]提出了一种先前PDP方案的动态版本，基于哈希函数和对称密钥加密支持动态操作。然而，该方案失去了两个重要属性，即公开可验证性和完全动态数据操作。之后，埃尔维等人[3]通过使用基于秩信息的认证字典引入了动态可证明数据持有。朱尔斯等人[4]提出了POR模型，以确保数据持有和可 retrievability。不幸的是，该机制难以高效扩展以支持数据更新。沙查姆和沃特斯[5]设计了一种基于BLS签名的改进型PDP方案，但该方案不具备公开可验证性，且仅允许用户有限次数的验证请求。2012年，王等人[6]提出了一种实现公共审计性、存储正确性、隐私保护、批量审计、轻量级、支持动态数据以及错误定位与恢复的数据完整性检查方法。为防止TPA获取用户的机密数据，王等人[7]提出了一种使用随机掩码的公共机制，该机制也支持批量审计。在朱等人[8]的公共审计机制中，利用片段结构来减少签名的存储开销，并采用索引哈希表为用户提供动态操作支持。同时，为了向用户和TPA隐藏每个区块上签名者的身份，王等.[9]提出了一种利用基于环签名的同态认证器对云中一组用户的共享数据进行公共审计的机制。文献[10]中的审计机制旨在为大量用户保护身份隐私。然而，它未能支持公共审计。

公共审计中带用户撤销的密钥暴露保护

当被撤销用户离开群组时，出于安全考虑，该被撤销用户生成的签名应由群组中的现有用户重新签名，因为这些签名对群组而言已不再有效。最高效的方法是允许云将被撤销用户的签名转换为现有组成员的签名。相应地，公共审计过程应由第三方审计员使用现有组成员的公钥来完成。有两个基本的安全要求：（1）云与每个用户不属于同一可信域，仅能将被撤销用户的签名转换为同一数据块上某现有用户（例如Alice）的签名，但不能代表被撤销用户或现有用户对任意数据块进行签名；（2）即使云服务器获得了被撤销用户的私钥，也不应得知现有组成员的私钥。
先前的研究工作主要关注对个人数据完整性的审计以及从第三方审计员处保护身份隐私。最近，王等人[11]提出了一种利用代理重签名在不可信云环境中实现高效用户撤销的公共审计机制[12]。在王等人方案中，第一个安全要求得到了满足，但第二个安全要求却未能实现。具体而言，如果一个被撤销用户（例如 B）将其私钥泄露给云，则云可以计算出有效组成员（例如 A）的私钥。其直接后果是，不可信的云服务器将能够否认删除消息，因为他可以使用 A 的私钥对消息进行签名，从而引发争议。应对这一威胁的一个直接方法是，在重签名私钥分发到云之后，用户 A 更新其私钥。然而，这将带来巨大的通信和计算资源开销，因为 A 必须下载其所有已签名的消息，重新签名后再重新上传至云服务器，这使得王等人方案所带来的优势荡然无存。因此，如何在被撤销用户的私钥被泄露的情况下，仍能保障组成员私钥的安全性，是我们本文要解决的问题。
本文中，我们通过结合代理重签名与随机掩码技术，构建了一种新型公审机制，以确保被撤销用户的私钥被泄露后，不会影响组内其他用户私钥的安全性。因此，与现有的公共审计方案相比，新方案具有更高的安全性，即在审计协议执行后，即使被撤销用户的私钥被泄露，云也无法获取组内用户私钥的任何信息。我们证明了所提方案的安全性，并将其效率与最先进的方案进行了比较。
本文的其余部分安排如下。在第2节中，我们介绍几种密码学原语。在第3节中，给出了新机制的详细设计和安全性分析。第4节分析了新机制的效率。最后，第5节给出全文的结论性备注。

2 预备知识

在本节中，我们介绍新方案将使用到的背景知识。我们给出双线性对的基本定义和性质，以及相关的计算问题。

我们首先回顾“可接受双线性映射”[13]以及在我们的方案中起核心作用的计算性Diffie‐Hellman问题。
可接受双线性映射 $\hat{e}$ 定义在两个相同素数阶 $p$ 的群上，分别记为 $G_1$ 和 $G_2$，其中计算性Diffie‐Hellman问题是困难的。更正式地，我们有以下定义：

定义 1.（双线性映射）

设 $G_1$ 和 $G_2$ 是两个相同阶数 $p$ 的乘法循环群。令 $g$ 表示 $G_1$ 的一个生成元。一个可接受的配对是一个双线性映射 $e: G_1 \times G_1 \to G_2$，具有以下性质：
- 双线性 ：给定 $u, v \in G_1$ 和 $a, b \in \mathbb{Z}$，我们有 $e(u^a, v^b) = e(u, v)^{ab}$。
- 非退化 ： $e(g, g) \neq 1$。
- 可计算 ： $e$ 是可高效计算的。

在本文中，我们将直接使用“双线性映射”这一术语来指代上述定义的可接受双线性映射。

我们现在重新回顾一下计算性Diffie‐Hellman（CDH）问题和离散对数（DL）问题。

定义 2.（计算性Diffie-Hellman问题）

对于 $a,b \in \mathbb{Z}_p$，以 $g, g^a, g^b \in G_1$ 作为输入，输出 $g^{ab} \in G_1$。
如果在 $G_1$ 中计算CDH问题在计算上是不可行的，则CDH假设在 $G_1$ 中成立。

定义 3.（离散对数 (DL) 问题）

对于 $a \in \mathbb{Z}_p$，给定 $g, g^a \in G_1$ 作为输入，输出 $a$。
如果在 $G_1$ 中解决离散对数问题在计算上是不可行的，则DL假设在 $G_1$ 中成立。

3 新型公审机制的构建

在本节中，我们将展示如何为共享数据构建公共审计机制。与王等人[11]方案一样，我们也将云指定为代理，以代表组内的用户转换签名，并要求将被撤销用户的签名转换为原始用户的签名。

3.1 方案细节

新型公审机制包含六个算法：密钥生成、重密钥生成、签名、重签名、证明生成、证明验证。
- 密钥生成 。该算法由组内的每个用户运行，以生成其公钥和私钥。
- 重密钥生成 。该算法在被撤销用户、现有组用户和云服务器之间执行。执行后，该算法帮助云输出一个重签名密钥。
- 签名 。该算法由所有组用户运行，即原始用户对其创建的共享数据块进行签名；组用户对修改后的共享数据块进行签名。
- 重签名 。该算法由云服务器运行。当一个用户被从组中撤销后，云使用重签名密钥对之前由被撤销用户签名的数据块重新签名。
- 证明生成 。该算法由云运行，用于生成共享数据的持有证明。
- 证明验证 。该算法由公共验证者运行，用于验证证明的正确性。

设 $G_1$ 和 $G_2$ 为两个阶为 $p$ 的群，$g$ 是 $G_1$ 的生成元，$e: G_1 \times G_1 \to G_2$ 是一个双线性映射，$w$ 是 $G_1$ 中的一个随机元素。全局参数为 $(e,p, G_1, G_2, g, w, H, H)$，其中 $H$ 是一个哈希函数，满足 $H:{0, 1}^ \to G_1$，且 $H$ 是一个哈希函数，满足 $H:{0, 1}^ \to \mathbb{Z}_q$。共享数据中数据块的总数为 $n$，共享数据表示为 $M=(m_1,\dots, m_n)$。组中用户的总数为 $d$。

密钥生成

对于用户 $u_i$，他随机生成 $x_i \in \mathbb{Z}_p$，并输出他的公钥 $pk_i = g^{x_i}$ 和私钥 $sk_i = x_i$。不失一般性，假设用户 $u_1$ 为原始用户，即共享数据的创建者。原始用户还创建一个公有用户列表（UL），其中包含组内所有用户的 ID，并由原始用户签名。

ReKey

假设每对实体之间存在私有且认证的信道，且不存在共谋行为。云生成一个重签名密钥 $k_{ij}$，步骤如下：
- 云生成一个随机的 $r \in \mathbb{Z} p$ 并将其发送给被撤销用户 $u_i$；
- 用户 $u_i$ 向用户 $u_j$ 发送 $r / x_i$，其中 $sk_i = x_i$；
- 用户 $u_j$ 随机选择 $r_j \in \mathbb{Z}_p$ 并将 $(r(r_j + \lambda x_j)/x_i, g^{r_j})$ 发送给云，其中 $sk_j = x_j$ 和 $\lambda = h(g^{r_j})$；
- 云恢复 $k {i \to j} = (r_j + \lambda x_j)/x_i \in \mathbb{Z}_p$。

Sign

给定私钥 $sk_i = x_i$，共享数据 $M$ 中的区块 $m_k \in \mathbb{Z}_p$ 及其块标识符 $id_k$（其中 $k \in [1, n]$），用户 $u_i$ 输出对区块 $m_k$ 的签名为 $\sigma_k = (H(id_k) w^{m_k})^{x_i} \in G_1$。

重签名

当用户 $u_i$ 被从组中撤销时，云能够将用户 $u_i$ 的签名转换为用户 $u_j$ 在同一区块上的签名。更具体地，给定重签名密钥 $k_{i \to j}$、公钥 $pk_i$、签名 $\sigma_k$、区块 $m_k$ 和块标识符 $id_k$，云首先检查 $e(\sigma_k, g) \stackrel{?}{=} e(H(id_k) w^{m_k}, pk_i)$。如果验证结果为0，云输出；否则，它输出
$$
\sigma’ k = \sigma_k^{k {i \to j}} = (H(id_k) w^{m_k})^{x_i (\lambda x_j + r_j)/x_i)} = (H(id_k) w^{m_k})^{\lambda x_j + r_j}.
$$
重新签名后，原始用户从用户列表中移除用户 $u_i$ 的 ID 并对新的用户列表进行签名。

ProofGen

为了审计共享数据的完整性，第三方审计员生成如下审计消息：
- 从集合 $[1, n]$ 中随机选取一个包含 $c$ 个元素的子集 $L$，以确定本次审计任务中将被检查的 $c$ 个随机块。
- 生成一个随机的 $y_l \in \mathbb{Z} q$，其中 $l \in L$ 和 $q$ 是比 $p$ 小得多的素数。
- 输出一个审计消息 $(l, y_l) {l \in L}$，并将其发送到云。

在收到审计消息后，云生成共享数据的持有证明 $M$。更具体地说，
- 云将集合 $L$ 分为 $d$ 个子集 $L_1,\cdots, L_d$，其中 $L_i$ 是用户 $u_i$ 签名的选定数据块的子集。子集 $L_i$ 中的元素数量为 $c_i$。显然，我们有
$$
c = \sum_{i=1}^d c_i, \quad L = L_1 \cup \cdots \cup L_d \quad \text{且} \quad L_i \cap L_j = \emptyset, \quad \text{其中 } i \neq j.
$$
- 对于每个集合 $L_i$（$i \neq 1$），云计算
$$
\alpha_i = \sum_{l \in L_i} y_l m_l \in \mathbb{Z} p, \quad \beta_i = \prod {l \in L_i} \sigma_l^{y_l} \in G_1.
$$
- 对于 $L_1$，云分别计算
$$
\alpha_{11} = \sum_{l \in L_{11}} y_l m_l, \quad \beta_{11} = \prod_{l \in L_{11}} \sigma_l^{y_l},
$$
和
$$
\alpha_{12} = \sum_{l \in L_{12}} y_l m_l, \quad \beta_{12} = \prod_{l \in L_{12}} (\sigma’_l)^{y_l}.
$$

最后，云输出一个审计证明 $(\alpha, \beta, \gamma, id_l) {l \in L}$，其中
$$
\alpha = (\alpha_1,\dots, \alpha_d), \quad \beta = (\beta_1,\dots, \beta_d), \quad \gamma = g^{r_1},
$$
$$
\alpha_1 = (\alpha {11}, \alpha_{12}), \quad \beta_1 = (\beta_{11}, \beta_{12});
$$

证明验证

对于一个审计证明 $(\alpha, \beta, \gamma, id_l) {l \in L}$、一个审计消息 $(l, y_l) {l \in L}$ 以及所有现有用户的公钥 $(pk_1,\dots, pk_d)$，第三方审计员检查该审计证明的正确性如下：
- 对于 $l \in L_i$ ($i \neq 1$)，云检查方程
$$
e\left(\prod_{i=2}^d \beta_i, g\right) = \prod_{i=2}^d e\left(\prod_{l \in L_i} H(id_l)^{y_l} \cdot w^{\alpha_i}, pk_i\right)
$$
成立与否。
- 对于 $l \in L_{11}$，云检查方程
$$
e(\beta_{11}, g) = e\left(\prod_{l \in L_{11}} H(id_l)^{y_l} \cdot w^{\alpha_{11}}, pk_1\right)
$$
成立与否。
- 对于 $l \in L_{12}$，云检查方程是否成立
$$
e(\beta_{12}, g) = e\left(\prod_{l \in L_{12}} H(id_l)^{y_l} \cdot w^{\alpha_{12}}, pk_1\right)^\lambda \cdot e\left(\prod_{l \in L_{12}} H(id_l)^{y_l} \cdot w^{\alpha_{12}}, \gamma\right)
$$
成立与否。

如果结果为1，验证者认为共享数据 $M$ 中所有数据块的完整性是正确的。否则，验证者输出0。

备注 。类似于王等人[11]的方案，由于我们使用了双线性对，我们的公共审计协议也支持批量审计，即第三方审计员可以同时执行多个审计任务。

3.2 公共审计机制的安全分析

在本小节中，我们将对我们的公共审计协议进行安全性分析，包括存储正确性和密钥隐私保护。

存储正确性保证

我们需要证明云服务器若不忠实地存储数据，则无法向第三方审计员生成有效的响应。

定理1. 给定共享数据 $M$ 及其签名，验证者能够正确检查共享数据 $M$ 的完整性。

证明： 我们可以通过验证以下方程来证明本机制的正确性。根据双线性映射的性质，这些方程的正确性如下所示：
- 对于 $l \in L_i$ ($i \neq 1$)，云检查该方程
$$
e\left(\prod_{i=2}^d \beta_i, g\right) = \prod_{i=2}^d e\left(\prod_{l \in L_i} \sigma_l^{y_l}, g\right)
= \prod_{i=2}^d e\left(\prod_{l \in L_i} (H(id_l) w^{m_l})^{x_i y_l}, g\right)
= \prod_{i=2}^d e\left(\prod_{l \in L_i} H(id_l)^{y_l} \cdot w^{\sum_{l \in L_i} y_l m_l}, g^{x_i}\right)
= \prod_{i=2}^d e\left(\prod_{l \in L_i} H(id_l)^{y_l} \cdot w^{\alpha_i}, pk_i\right)
$$

• 对于 $l \in L_{11}$，云检查该方程
  $$
  e(\beta_{11}, g) = e\left(\prod_{l \in L_{11}} \sigma_l^{y_l}, g\right)
  = e\left(\prod_{l \in L_{11}} (H(id_l) w^{m_l})^{x_1 y_l}, g\right)
  = e\left(\prod_{l \in L_{11}} H(id_l)^{y_l} \cdot w^{\sum_{l \in L_{11}} y_l m_l}, g^{x_1}\right)
  = e\left(\prod_{l \in L_{11}} H(id_l)^{y_l} \cdot w^{\alpha_{11}}, pk_1\right)
  $$

• 对于 $l \in L_{12}$，云检查方程
  $$
  e(\beta_{12}, g) = e\left(\prod_{l \in L_{12}} (\sigma’ l)^{y_l}, g\right)
  = e\left(\prod {l \in L_{12}} \left((H(id_l) w^{m_l})^{\lambda x_1 + r_1}\right)^{y_l}, g\right)
  = e\left(\prod_{l \in L_{12}} H(id_l)^{y_l} \cdot w^{\sum_{l \in L_{12}} y_l m_l}, g^{\lambda x_1 + r_1}\right)
  = e\left(\prod_{l \in L_{12}} H(id_l)^{y_l} \cdot w^{\alpha_{12}}, pk_1^\lambda \cdot \gamma\right)
  = e\left(\prod_{l \in L_{12}} H(id_l)^{y_l} \cdot w^{\alpha_{12}}, pk_1\right)^\lambda \cdot e\left(\prod_{l \in L_{12}} H(id_l)^{y_l} \cdot w^{\alpha_{12}}, \gamma\right)
  $$

因此，定理得证。

定理2. 对于云而言，在我们的机制下，生成审计证明的伪造在计算上是不可行的。

证明： 我们的方案与王等人方案之间的差异[11]在于重签名密钥的生成方式，即在我们的方案中使用随机掩码技术来生成重密钥。因此，来自原始数据创建者的某些签名的验证 $U_1$ 与王等人方案略有不同。然而，我们发现当我们将王等人的策略应用于我们的方案时，这些差异不会影响证明过程。因此，我们方案的证明与王等人方案的证明类似。

密钥隐私保障

我们希望确保即使第三方审计员与被撤销用户共谋，也无法推导出现有组用户的私钥。这相当于证明以下定理。

定理3. 对于云服务器而言，即使在被撤销用户的私钥协助下，在我们的机制中计算目标签名者的私钥也是计算上不可行的。

证明： 根据公共审计协议的描述，我们知道如果云服务器与被撤销用户共谋，他将拥有该被撤销用户的私钥 $a$。我们需要证明云服务器无法获取到现有组用户的私钥，即签名从被撤销用户转移给的那个现有组用户。在我们的方案中，假设此现有组用户为共享数据的创建者 $U_1$。该问题的困难性在于离散对数问题的困难性（给定 $g$ 和 $g^k$，很难计算出 $k$）。更具体地说，当云服务器向 $U_1$ 发起“重密钥”查询时，挑战者会返回 $(k + h(g^k)b)/a, g^k)$ 给云服务器。注意，尽管有 $g^k$ 的值，但由于离散对数假设的困难性，$k$ 的值对云服务器仍然是隐藏的。因此，$U_1$ 的私钥 $b$ 相对于 $k$ 的隐私性得以保证。

4 效率分析与比较

在本节中，我们通过将新方案与王等人[11]的方案进行比较，讨论了我们机制的通信和计算开销。假设 $d$ 是组内现有用户的数量，$c$ 是选定块的数量，$|n|$ 是集合 $[1, n]$ 中元素的大小，$|q|$ 是 $\mathbb{Z} q$ 中元素的大小，$|p|$ 是 $G_1$ 或 $\mathbb{Z}_p$ 中元素的大小，$|id|$ 是块标识符的大小。此外，假设 $\text{Exp} {G_1}$ 表示 $G_1$ 中的一个指数运算，$\text{Mul} {G_1}$ 表示 $G_1$ 中的一个乘法运算，$\text{Pair}$ 表示 $e$ 上的一个配对运算：$G_1 \times G_1 \to G_2$，且 $\text{Hash} {G_1}$ 表示 $G_1$ 中的一个哈希运算。

从表1可以看出，我们的方案的通信开销略高于王等人方案。更准确地说，在我们的方案中，审计消息 $(l, y_l) {l \in L}$ 的大小为 $c \cdot (|n| + |q|)$ 位，审计证明 $(\alpha, \beta, \gamma, id_l) {l \in L}$ 的大小为 $3d \cdot |p| + c \cdot |id|$ 位。因此，一次审计任务的总通信开销为 $3d \cdot |p| + c \cdot (|id| + |n| + |q|)$ 位。而王等人方案的一次审计任务总通信开销为 $2d \cdot |p| + c \cdot (|id| + |n| + |q|)$ 位。因此，我们的方案比王等人方案多出 $d \cdot |p|$ 的通信开销，但整体仍处于相近水平。

在计算开销方面，如我们机制中的重签名所示，云首先验证数据块上原始签名的正确性，然后使用重签名密钥对同一数据块计算新的签名。云中对一个数据块进行重新签名的计算开销为 $2\text{Exp} {G_1} + \text{Mul} {G_1} + 2\text{Pair} + \text{Hash} {G_1}$。云可以通过直接重新签名而不进行验证，进一步将数据块重新签名的计算开销降低至 $\text{Exp} {G_1}$。由第三方审计员执行的公共审计可确保重新签名的数据块是正确的。

因此，我们机制中一个审计任务的计算开销为
$$
(c + d)\text{Exp} {G_1} + (c + 2d)\text{Mul} {G_1} + (d + 2)\text{Pair} + d\text{Mul} {G_2} + c\text{Hash} {G_1} + (c_{12})\text{Exp} {G_2}
$$
而王等人方案的计算开销为
$$
(c + d)\text{Exp} {G_1} + (c + 2d)\text{Mul} {G_1} + (d + 1)\text{Pair} + d\text{Mul} {G_2} + c\text{Hash} {G_1}
$$
因此，我们的方案比王等人方案多出 $1\text{Pair} + (c {12})\text{Exp}_{G_2}$ 的计算开销。由于第三方审计员的计算能力足够强，我们认为两者在实际应用中的性能差异可以忽略。

我们最后检查了当被撤销用户的私钥被泄露给云时的安全性。从该方案可以看出，当被撤销用户的私钥被泄露给云时，在我们的方案中现有组用户的私钥是安全的，而在王等人方案中，云容易计算出现有组用户的私钥。

5 结论

我们提出了一种具有高效用户撤销功能的云中共享数据密钥暴露保护公共审计机制。该方案的主要优势在于，即使被撤销用户的私钥被泄露，通过结合本文提出的随机掩码技术与增强的代理重签名方案，仍能确保组内其他用户的私钥对云服务器保持保密。此外，即使部分共享数据已被云重新签名，公共验证者始终能够审计共享数据的完整性。我们分析了该新型公共审计方案的效率与安全性，并证明了我们的机制提供了良好的密钥暴露保护，同时保持高通信和计算效率。