本文最后更新于:星期二, 四月 7日 2020, 8:11 晚上

一、引入

1. VDB

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

2. 文章结构

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

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

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

二、可更新验证数据库

存储内容

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

VDB的主要四个算法

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

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

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

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

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

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

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

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

符号 含义 符号 含义
xx 数据序号 mxm_x 数据库中第x个数据
vxv_x 第x个数据对应的密文 kk 数据库安全参数
DBDB 数据库DB SS 数据库编码格式
τ\tau τ=(v,π)\tau =(v,\pi)为服务器对于客户端查询请求的响应 π\pi 对于查询结果vv附带的验证码
vv' 用于更新替代原数据vv的新数据 txt'_x 用于更新第x个数据所需要的票据

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

双线性配对

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

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

向量承诺

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

向量承诺的定义

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

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

四、Catalano-Fiore VDB框架

框架组成

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

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

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

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

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

VC.VerPP(C,x,vx,πx)=1VC.Ver_{PP}(C,x,v_x,\pi_x)=1,那么返回vxv_x。否则返回一个错误errorerror \perp

4. Update(SK,x,v)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)PK'=(PP,C')以及tx=(PK,vx,U)t_x'=(PK',v_x',U)
  3. 之后,服务器利用vxv_x'更新公钥,利用UU更新辅助信息。

前向自动更新攻击(FAU)

Catalano-Fiore VDB框架存在FAU

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

FAU存在的根本原因

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

五、新型高效VDB框架

1.本框架设计理念

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

符号 含义
CT1C_{T-1} 更新前承诺值(带有签名)
C(T)C^{(T)} 更新后承诺值(不带签名)
TT 计数器(更新次数)
HTH_T 签名(HT=SIGNsk(CT1,C(T),T)H_T=SIGN_{sk}(C_{T-1},C^{(T)},T))
CTC_T 更新后承诺值(带签名)

2.本框架组成

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

数据库存储格式和通常情况一样,为DB=(i,vi)DB=(i,v_i)。运行向量承诺的密钥生成算法产生公共参数$$PP\gets VC.KeyGen(1^k,q)$$
然后运行承诺算法计算承诺以及辅助信息$$(C_R,aux)\gets VC.Com_{pp}(v_1,…,v_q)$$令计数器TT的初始值为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)S=(PP,aux,DB)

SK=skSK=sk

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

假定当前的公钥为PK=(PP,Y,CR,CT)PK=(PP,Y,C_R,C_T),输入xx时,服务器运行打开算法计算出$$\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,τ)Verify(PK,x,\tau )

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

4. Update(SK,x,vx)Update(SK,x,v_x')

客户端首先取得需要修改的数据的当前值:

τQuery(PS,S,x)\tau \gets Query(PS,S,x)

并且检查:

Verify(PK,x,τ)=vxVerify(PK,x,\tau)=v_x\neq \perp

TT+1T\gets T+1。然后客户端计算出修改之后的承诺值:

C(T)=VC.ComPP(v1(T),...,vq(T))C^{(T)}=VC.Com_{PP}(v_1^{(T)},...,v_q^{(T)})

以及包含承诺值的承诺票据:

tx=HT=SIGNsk(CT1,C(T),T)t_x'=H_T=SIGN_{sk}(C_{T-1},C^{(T)},T)

然后向服务器发送(tx,vx)(t_x',v_x')
服务器检查txt_x'有效之后,服务器计算

CT=HTC(T)C_T=H_TC^{(T)}

并且更新公钥

PK=(PP,pk,CR,CT)PK=(PP,pk,C_R,C_T)

更新vxv_x之后,服务器向auxaux中添加信息T\sum_T

T=(HT,CT1,C(T),T)\sum_T = (H_T,C_{T-1},C^{(T)},T)

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


Crypto      笔记 密码 论文

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!

使用git push时忽略.DS_store文件 上一篇
2018 To Do List 下一篇