When Query Authentication Meets Fine-Grained Access Control: A Zero-Knowledge Approach

未分类

问题关键词

Query Authentication

用户在获取数据的过程中，因为各种原因（权限，方便），往往不会直接接触数据源，而是由一个service provider(SP)对原数据进行一通操作（获取整理筛选）然后返回给用户。

一个常见的问题是这个service provider 是否可信，service provider可能会被hack亦或是它本身就是恶意的(e.g 某度竞价排名, 美国大选期间google不到关于希拉里的负面新闻)，无论处于哪种原因，此时 service provider 返回的结果都会出现偏差。

所以Query Authtication 的问题就是，对于可信的数据源和不可信的service provider，验证其返回结果是否与源数据无出入。基本方案是用私钥为每个数据生成签名，用户使用公钥来验证。

为了验证数据完整性，常用有两个姿势。上图a是Signature Chaining, 类似于双向链表，对一个数据$o_i$，对其与左右节点$o_{i-1}$和$o_{o+1}$一起生成签名。b图用了一个树形的结构，假设要查询的数据是$o_2$，对该数据点返回数据和签名，其他数据点仅返回非叶子结点的哈希，最终通过验证$root$节点的哈希来验证数据的完整性

Fine-Grained Access Control

因为查询验证需求的多样性使得这方面的研究得以开展，本文的一个点就是细粒度访问控制（Fine-Grained Access Control）。

Fine-grained 对应的是 corase grained (粗粒度)。用户对不同的数据应当有不同的权限，简单的访问控制方法有：Access Control List(ACL), Role-Based Access Control 等。相比于细粒度的访问控制，这些方法在面对复杂规则往往不尽如人意（举个例子，男卫生间对所有男性开放也对保洁阿姨开放，残疾人、母婴室等等）。

这里使用了一个 Attribute-Based Signature(ABS), 将权限方案表示成多个属性构成对布尔表达式，然后将其于数据关联生成签名。如下图

对于$o_1$这个$record$, 需要$Role_A$和$Role_B$两个条件。

而对于$o_2$,$Role_B$和$Role_C$只需满足任意一个。

Zero-Knowledge Approach

简单的说就是除了给你的什么都不知道

还是用上面的图来说明，用户$u_2$对于这个Q查询，返回结果是${<o_3,v_3>, <o_3, v_3>}$,对于没有权限的$o_3$,不仅内容看不见，需要什么权限也查不到，用户可以验证返回信息的完整性，同时可以验证自己缺少权限获取$o_3$，但对于$o_3$需要什么权限无法获知。

问题关键点

Untrusted Service Provider

SP 返回给用户查询结果$v_i$的同时返回一个 Verification Object $vo_i$

用户验证两个点：
1. Soundness: 数据未被任何人篡改，同时数据符合查询规则和用户权限
2. Completeness: 不在返回结果中的数据要么不在查询范围中要么无权限

对 inaccessable data 保密

对于 inaccessable data, 大致需要满足三个方面的机密性要求
1. 查不到其内容（显然）
2. 查不到其权限（预防攻击？）
3. 什么都查不到（包含上述两点）

如何解决了

引入Attribute-Based Signature

首先介绍一个现有的加密技术，Ciphertext-Policy Attribute-Based Encryption, 通过将权限规则嵌入密文来实现精细的权限控制。大致有这么几个流程：
1. $CP-ABE.Setup(1^\lambda) \rightarrow (mk, pp)$: 用一个系数$1^\lambda$来生成master private key和public key
2. $CP-ABE.KeyGen(mk, A)\rightarrow sk_A$: 对于master private key 和一个属性集 $A$, 生成一个解密密钥$sk_A$.
3. $CP-ABE.Encrypt(pp, x, \gamma) \rightarrow c_\gamma$: 对于一个public key和一个权限条件$\gamma$, 将明文$x$加密成密文$c_\gamma$。
4. $CP-ABE.Decrypt(sk_A, c_\gamma) \rightarrow x$: 有signature key和密文$c_\gamma$解密出明文$x$.

将其原理用到签名技术上，便有了Attribute-Based Signature:
1. $ABS.Setup(1^\lambda) \rightarrow (msk, mvk)$: 通过系数$1^\lambda$生成master signature key和master verification key.
2. $ABS.KeyGen(msk, A) \rightarrow sk_A$: 对于一个msk和一个属性集$A$，生成一个signing key
3. $ABS.Sign(sk_A, m, \gamma) \rightarrow \sigma_{m, \gamma}$: 对于$sk_A$，message, 和一个monotone function $\gamma$，当$\gamma(A) = 1$的时候生成一个签名$\sigma_{m, \gamma}$
4. $ABS.Verrify(mvk, m, \gamma, \sigma_{m, \gamma}) \rightarrow \{0, 1\}$: 有master verification key, 未验证的信息message, monotone function $\gamma$, 和签名$\sigma_{m, \gamma}$, 验证其是否有效。

单点查询(Equality Query)

文中的描述为 Equality Query, 用户有一个权限组 $A$，请求查询一个record $O_q$

很容易理解有三种情况：
1. Record $O_q$ 存在，且用户有权限(accessable)
2. Record $O_q$ 存在，用户无权限(inaccessable)
3. Record $O_q$ 不存在

对于不存在的数据我们生成一个假的的权限规则$Role_\emptyset$和一条与之对应的假的数据Record。

authenticated data structures(ADS)

Definition5.1(APP Signature). Consider a record$⟨o_i,v_i,\gamma_i⟩$. Let $sk_{DO}$ be the signing key of the $DO$, $hash(·)$ a cryptographic hash function, and ‘|’ denote string concatenation. The access-policy-preserving(APP) signature for this record is generated as:

$$\sigma_i = ABS.Sign(sk_{DO}, hash(o_i)|hash(v_i), \gamma_i)$$
In the case of pseudo(non-existent) records, $v_i$ will be assigned a
random value and $Υ_i$ will be $Role_\emptyset$.

如上图的$user_1$，显然他有权限访问数据$o_2$，将APP signature加入VO，然后用户用ABS.verify来验证.

当用户没有权限(如上图的$user_2$), 用APS signature代替 APP signature加入VO(最后返回用户).

返回给用户的数据用CP-ABE加密传输给用户，防止攻击

上面有个欠账，APS signature是个什么玩意？

Definition 5.2(APS Signature). Consider a record $⟨o_i , v_i , \gamma_i ⟩$. Denoted by $\mathbb A$ and $A$ the global access role set and the query user’s role set, respectively. Let $sk_{DO}$ be the signing key of the $DO$, $hash(·)$ a cryptographic hash function, and ‘|’ denote string concatenation. The access-policy-stripped(APS) signature for this record and the user with access role set $A$ is de ned as:

$$\widehat{\sigma}_{i,A} = ABS.Sign(sk_{DO},hash(o_i)|hash(v_i),\widehat{\sigma}_A),$$
$$where \widehat{\sigma}_A = a_1 \vee a_2 \vee ···\vee a_n, a_i \in \mathbb A\backslash A.$$

Attribute-Based Signature(ABS)是针对可以访问的数据的一套方法，针对无权限的数据大致需要另一套验证方法，我们命名为$ABS.Relax$，文中这一章节涉及来大量密码学的方法，我自己看的有点晕乎乎的，我们可以将其理解成一个黑盒，其原理与结构与正常的$ABS$十分的雷同，为的是在用户不知道是自己无权限还是数据不存在的情况下进行验证。

区间(Range)查询和Join查询

在区间查询中，用户有个查询范围$[\alpha, \beta]$，然后服务器把范围内符合需求用户可达的数据返回给用户。

最朴素的做法是，对区间内数据一个一个check，然后把合法的返回，显然，这个复杂度 $O(n)$，非常的丑陋和不能忍受

来给数据结构优化 Access-Policy-Preserving Grid-Tree, 如下图

Definiton 3($AP^2G$-Tree Non-Leaf Node).
The access policy and APP signature are:

$$p_i = p_{c_1} \vee p_{c_2} \vee ... \vee p_{c_C}$$
$$sig_i = ABS.Sign(sk_{DO}, gb_i, p_i)$$
Definition 4($Ap^2G$-Tree Leaf Node).
The access policy and APP signature are indetical to those of underlying data record.

看这个例子，二维的数据在平面中，通过对空间分块(分成很多grid)，然后形成四叉树的结构，对于level 2, $[\alpha, \beta]$的范围如图a，其中$o_6, o_7, o_8$为用户有权限的数据，这颗树的结构如右图，和hash树的情况类似，VO包含$N_7, N_8, N_4, N_{14}, N_{18}$和$o_6, o_7, o_8$, 通过对$o_6, o_7, o_8$对签名一个个验证来验证其正确性，检查VO中这么多节点对并集对范围是否等于$[\alpha, \beta]$来验证其数据完整性

查询过程的算法和线段树的区间查询类似（貌似所有的区间查询都差不多，talk later）

对于Join查询，再看个栗子

两个table，R和S，红框内为查询范围，有权限访问的是$r_1, r_2, s_1, s_3$四个节点。显然，因为是Join查询，返回结果应该是$\left \langle r_1, s_1 \right \rangle$。

流程：服务器先查 $Table R$, 得到$r_1, r_2$，然后一一检查$Talbe S$的$s_1, s_2$，筛完后剩下$\left \langle r_1, s_1 \right \rangle$(what we want).服务器返回$\left \langle r_1, s_1 \right \rangle$(accessable)和$R_2, R_4$(inaccessable)，验证accessable的数据来检验正确性，将验证结果并集是否等于$[\alpha, \beta]$来验证数据完整性。

优化的姿势

Hierarchical Role Assignment

将role分级来减少逻辑运算，栗子：

$Role_A \wedge Role_{A, P} \Rightarrow Role_{A, P}$

Acceleration by Parallelism

并行计算的优化，多核的CPU。

数据结构优化，K-d Tree

k-d Tree相对Grid-Tree更多的利用数据分布的信息，加速query

运行的效果

随着权限规则规模的增长，查询时间的增长是线性的

just a lot

总结与引申

• ABS -> Fine-Grained Access Control,
• APP Signature -> Zero Knowledge
• Grid Tree, K-d Tree -> DataStructure to accelerate

？？？引申的问题？？？