New Publicly Verifiable Databases with Efficient Updates

一、引入

1. VDB

首先引入可验证数据库(VDB)的概念,可验证数据库实现了客户端将大规模的数据存储在一个不信任的数据库(即数据库可能会进行恶意操作),并且客户端之后可以取回或者更新数据。可验证的意思就是服务器对数据的任何篡改都可以被检测到。这篇论文提出了一个基于向量承诺(承诺绑定)的公开可验证数据库,并且可以抵御FAU攻击。

2. 文章结构

原文献的内容可以分为下面这几个部分:

1. 提出VDB的安全要求的正式定义;    
2. 概述目前已有的一些VDB框架;    
3. 提出新的VDB框架及其详细实现;    
4. 本文的VDB框架的安全性分析以及与现有VDB框架的对比;    
5. 结论

详细的论文结构可以参阅本文末尾的思维导图。

二、可更新验证数据库

存储内容

我们将数据库存储的原始内容(即不考虑验证、加密,真正的数据部分)定义为一个二元组$(x,m_x)$,也可以将其看为一个键值对,其中$x$表示序号,$m_x$表示对应序号的值。但是为了数据的机密性,通常$m_x$都被加密为$v_x$,因此通常情况下存在服务器端的数据为$(x,v_x)$。

VDB的主要四个算法

1. 数据库初始化算法:$Setup(1^k,DB)$

Setup算法用于数据库的初始建立阶段,主要功能是由输入的安全参数$k$来产生数据库$DB$的服务端和客户端所需要用到的公钥和私钥以及数据库的编码格式$S$。

2. 数据查询算法:$Query(PK,S,x)$

Query算法实现的是客户端对服务器请求第$x$个数据的功能,服务器会返回一个二元组$\tau =(v,\pi)$,这里的$\pi$可以暂时理解为是对这里的密文数据$v$的一个验证。

3. 数据验证算法:$Verify(PK/SK,x,\tau)$

对于验证算法,有一些VDB框架仅使用公钥验证,有些也需要用到私钥,这个问题我们会在后面详细讨论。对于接收到的查询结果$\tau$,若验证通过,则输出$v$,若不通过,则输出$error$。

4. 数据更新算法:$Update(SK,x,v’)$

客户端想要更新第x个数据的时候,首先需要利用私钥生成一个票据$t’_x$,然后向服务器发送$(t’_x,v’)$。然后服务器利用$v’$替换原数据$v$,并利用$t’_x$生成新的公钥$PK$。

符号 含义 符号 含义
$x$ 数据序号 $m_x$ 数据库中第x个数据
$v_x$ 第x个数据对应的密文 $k$ 数据库安全参数
$DB$ 数据库DB $S$ 数据库编码格式
$\tau$ $\tau =(v,\pi)$为服务器对于客户端查询请求的响应 $\pi$ 对于查询结果$v$附带的验证码
$v’$ 用于更新替代原数据$v$的新数据 $t’_x$ 用于更新第x个数据所需要的票据

三、新VDB框架所用到的概念

双线性配对

$\mathbb{G}_1$和$\mathbb{G}_2$为两个p阶素数乘法循环群。$g$为$\mathbb{G}_1$的生成元,双线性配对即为下面这个映射:$$e:\mathbb{G}_1 \times \mathbb{G}_1 \to \mathbb{G}_2$$它具有以下这些性质:

  1. 双线性,$e(u^a,v^b)=e(u,v)^{ab}$,对于所有的$u,v\in \mathbb{G}_1$,并且$a,b\in \mathbb{Z}_p^*$。
  2. 非退化性。$e(g,g)\neq 1$。
  3. 可计算性。存在一个高效的算法对于所有的$u,v\in \mathbb{G}_1$都能够计算出$e(u,v)$。

向量承诺

承诺就如同一个被封口的信封,发送方将消息放在信封中封口之后交给接收方。一方面,除了发送方,没有人可以打开信封阅读里面的内容(这被称为隐藏),另一方面,发送方再也不可以更改信封中的内容了(这被称为封装)。
不同于普通的承诺只对一个单独的消息进行承诺,向量承诺可以对一个有序的数值序列进行承诺。并且承诺人之后可以打开特定位置的承诺。并且最重要的是,对于一个攻击者来说,找到一个位置的承诺的两个不同的值是困难的(找到一对碰撞是困难的)。

向量承诺的定义

向量承诺由一系列的算法组成,向量承诺$$VC=(VC.KeyGen,VC.Com,VC.Open,VC.Veri,VC.Update,VC.ProofUpdate)$$

  • $VC.KeyGen(1^k,q)$。输入安全参数$k$以及多项式大小$q$,输出一些公共参数$PP$(定义了消息空间$M$)。
  • $VC.Com_{pp}(m_1,…,m_q)$。输入一个消息序列以及公共参数$PP$,承诺算法会输出一个承诺字符串$C$和一个辅助消息$aux$。
  • $VC.Open_{PP}(m,i,aux)$。承诺者运行这个算法来产生一个能够证明$m_i$是第$i$个被承诺消息的证据$\pi_i$。
  • $VC.Ver_{PP}(C,m,i,\pi_i)$。验证算法若成功验证$\pi_i,C$是有效的,则返回1。
  • $VC.Update_{PP}(C,m,i,m’)$。承诺者运行这个算法来更新某一个消息$m$。算法会输出一个新的承诺$C’$和一个更新信息$U$。
  • $VC.ProofUpdate_{PP}(C,U,m’,i,\pi_i)$。任何拥有原$\pi_i$的人都可以用这个算法计算出信息更新之后的新的$\pi_i’$和新承诺$C’$。

四、Catalano-Fiore VDB框架

框架组成

1. $Setup(1^k,DB)$

数据库存储格式和通常情况一样,为$DB=(i,v_i)$。运行向量承诺的密钥生成算法产生公共参数$$PP\gets VC.KeyGen(1^k,q)$$。然后运行承诺算法计算承诺以及辅助信息$$(C,aux)\gets VC.Com_{pp}(v_1,…,v_q)$$。定义公钥为$PK=(PP,C)$,$S=(PP,aux,DB)$,私钥$SK=\perp$。

2.$Query(PK,S,x)$

服务器接收到一个序号$x$之后,先运行打开算法计算验证信息$$\pi_x\gets VC.Open_{PP}(v_x,x,aux)$$之后再返回$\tau = (v_x,\pi_x)$。

3. $Verify(PK,x,\tau)$

若$VC.Ver_{PP}(C,x,v_x,\pi_x)=1$,那么返回$v_x$。否则返回一个错误$error \perp$。

4. $Update(SK,x,v’)$

客户端更新数据的步骤为

  1. 从客户端取得$\tau$:$$\tau \gets Query(PS,S,x)$$并检查$$Verify(PK,x,\tau)=v_x\neq \perp$$。
  2. 同时,客户端计算$$(C’,U)\gets VC.Update_{PP}(C,v_x,x,v_x’)$$并且输出$PK’=(PP,C’)$以及$t_x’=(PK’,v_x’,U)$。
  3. 之后,服务器利用$v_x’$更新公钥,利用$U$更新辅助信息。

前向自动更新攻击(FAU)

Catalano-Fiore VDB框架存在FAU

上述的框架中存在前向自动更新攻击漏洞,从前面对于框架中$Update$算法的描述可以看出,客户端执行的一系列操作以及所需要的参数,服务器都可以获取到。这也就意味着恶意服务器完全可以自行篡改数据库。并且对于第三方评判机构来说,无法判断究竟是服务器篡改了还是客户端在撒谎。

FAU存在的根本原因

上述框架能够遭受FAU攻击的根本原因是因为它的更新算法没有使用到公钥,其使用到的信息都是相对公开的,恶意服务器可以轻易掌握这些信息从而篡改数据。

五、新型高效VDB框架

1.本框架设计理念

使用承诺绑定的概念解决这个问题。客户端使用私钥$SK$给一些绑定的信息计算出签名并附着在后面。并且这个签名也用来计算更新过的承诺$C’$,这样一来服务器无法在没有客户端合作的情况下计算新的$C’$。
绑定信息的组成为:

符号 含义
$C_{T-1}$ 更新前承诺值(带有签名)
$C^{(T)}$ 更新后承诺值(不带签名)
$T$ 计数器(更新次数)
$H_T$ 签名($H_T=SIGN_{sk}(C_{T-1},C^{(T)},T)$)
$C_T$ 更新后承诺值(带签名)

2.本框架组成

1. $Setup(1^k,DB)$

数据库存储格式和通常情况一样,为$DB=(i,v_i)$。运行向量承诺的密钥生成算法产生公共参数$$PP\gets VC.KeyGen(1^k,q)$$
然后运行承诺算法计算承诺以及辅助信息$$(C_R,aux)\gets VC.Com_{pp}(v_1,…,v_q)$$令计数器$T$的初始值为0。令$$C^{(T)}=VC.Com_{PP}(v_1^{(T)},…,v_q^{(T)})$$为最后一次更新的数据库的承诺值。令$$C^{(0)}=C_R,C_{-1}=C_R$$令$$PK=(PP,pk,C_R,C_0)$$$$S=(PP,aux,DB)$$$$SK=sk$$

2. $Query(PK,S,x)$

假定当前的公钥为$PK=(PP,Y,C_R,C_T)$,输入$x$时,服务器运行打开算法计算出$$\pi_x \gets VC.Open_{PP}(v_x,x,aux)$$并且返回$$\tau = (v_x,\pi_x,{\sum} _T)$$其中$${\sum}_T=(H_T,C_{T-1},C^{(T)},T)$$

3. $Verify(PK,x,\tau )$

分析$\tau = (v_x,\pi_x,\sum_T)$。
如果:$$Ver_{pk}({\sum}_T)=1$$
(这就意味着$H_T$签名有效)
并且:$$VC.Ver_{PP}(C_T,H_T,x,v_x,\pi_x)=1$$
那么就返回$v_x$。否则返回$error \perp$。

4. $Update(SK,x,v_x’)$

客户端首先取得需要修改的数据的当前值:
$$\tau \gets Query(PS,S,x)$$
并且检查:
$$Verify(PK,x,\tau)=v_x\neq \perp $$
令$T\gets T+1$。然后客户端计算出修改之后的承诺值:
$$C^{(T)}=VC.Com_{PP}(v_1^{(T)},…,v_q^{(T)})$$
以及包含承诺值的承诺票据:
$$t_x’=H_T=SIGN_{sk}(C_{T-1},C^{(T)},T)$$
然后向服务器发送$(t_x’,v_x’)$。
服务器检查$t_x’$有效之后,服务器计算
$$C_T=H_TC^{(T)}$$
并且更新公钥
$$PK=(PP,pk,C_R,C_T)$$
更新$v_x$之后,服务器向$aux$中添加信息$\sum_T$:
$$\sum_T = (H_T,C_{T-1},C^{(T)},T)$$

下面是原论文的思维导图
New Publicly Verifiable Databases with Efficient Updates

0%