关系型数据加密和存储模型-《分布式数据库技术》最新成果

2023-10-28 理论教育版权反馈

【摘要】：下面讨论关系型数据加密和存储模型，对每个关系：R（A 1，A 2，…表13.1使用关系emp存储关于雇员的信息emp表在服务器上映射成对应的表，如下：emp S对应属性的索引会在搜索和连接谓词中使用。表13.2存放服务器的加密关系emp S第一列etuple是与emp关系对应的加密元组的串。

下面讨论关系型数据加密和存储模型，对每个关系：

R（A 1，A 2，…，An）

可以在服务器上存储加密关系，记作：

RS（etuple，AS1，AS2，…，ASn）

其中：属性etuple用于存储一个与关系R中元组对应的加密串。为每个属性Ai生成对应的索引ASi，并在服务器上实现查询处理。例如，考虑一个关系emp，存储关于雇员的信息，如表13.1所示。

表13.1　使用关系emp存储关于雇员的信息

pagenumber_ebook=276,pagenumber_book=261

emp表在服务器上映射成对应的表，如下：

emp S（etuple，eidS，enameS，salary S，addrS，didS）

对应属性的索引会在搜索和连接谓词中使用。不失一般性，可以假设为关系的每个属性创建相应索引。实现时需要以下函数的支持。

分割函数（partition function）：为了说明如何为关系R的每个属性存储相应的RSi的属性RSi，先说明有些记法。属性R.Ai的值域D首先映射为分割｛p1，p2，…，pk｝，并让这些分割合起来覆盖整个值域，则函数分割定义为：

partition（R.Ai）=｛p1，p2，…，pk｝

例如，emp关系中的属性eid的值域是［0，1000］，假设整个值域分为5个分割：

partition（emp.eid）=｛［0，200］，（200，400］，（400，600］，（600，800］，（800，1000］｝

不同的属性可以使用不同的分割函数，或者可把它们放在一起分割成一个多维模型。属性Ai的分割对应将其值域分成一个吊桶集合。分成吊桶可以提高结果查询效率。假设分割是等宽实施的，且让泄密局限到吊桶以内。

标识函数（identification function）：标识函数ident R.Ai（pj）将属性Ai的每个分割pj映射成一个唯一的标识。图13.5所示的为emp.eid的分割和标识函数，其中identemp_eid（［0，200］）=2，and identemp.eid（（800，1000］）=4。

图13.5　emp.eid的分割和标识函数

映射函数（mapping function）：给出上述分割函数和标识函数后，还需要一个映射函数，记作Map R.Ai，将属性Ai域中的一个值v映射成分割标识，即Map R.Ai（v）=ident R.Ai（pj），其中pj是包含v的分割。

存储加密数据（storing encrypted data）：对R中的每个元组t=〈a1，a2，…，an〉，在关系RS中存储一个元组：

〈encrypt（｛a1，a2，…，an｝），Map R.A1（a1），Map R.A2（a2），…，Map R.An（an）〉

其中：encrypt是一个用于对关系元组加密的函数。例如，表13.2就是存放在服务器的加密关系emp S。

表13.2　存放服务器的加密关系emp S

pagenumber_ebook=277,pagenumber_book=262

第一列etuple是与emp关系对应的加密元组的串。例如，第一个元组加密成“1100110011110…”，等价于encrypt（23，Tom，70000，Maple，40）。第二个加密成“1000000000011101…”等价于encrypt（860，Mary，60000，Main，80）。加密函数作为一个黑盒子，可以使用任意块加密技术，如AES、Blowfish、DES等算法来加密元组。第二列对应于属性雇员标识（即工号）的索引。例如，第一个元组的属性eid是23，对应的分割是［0，200］。因为该分割标识为2，因此存放2作为索引。

解密函数（decryption function）：给定的E算符将关系映射成用其加密表示，其逆运算D将加密映射成用对应的解密表示，也就是D（RS）=R。上例中，D（empS）=emp。D算符也可用于查询表达式。

1.映射条件

为了将运算（如选择运算和连接运算）中的指定查询条件翻译成服务器端表示的对应条件，会使用翻译函数，记作Mapcond。这些条件可帮助服务器端实现翻译关系算符和翻译查询树。对每个关系，服务器端存放加密元组和属性索引，客户端存放特定索引的元数据，如属性的分映射函数等信息。客户端利用这些信息翻译给定查询Q成为服务器端的查询QS，在服务器端执行。

2.翻译关系算符

这里讨论选择运算和连接运算。策略是通过分割算符的条件，让其跨客户端和服务器端，使得存在服务器端的属性索引有算符生成答案的扩展集（superset）。这个集合在客户端解密后进行过滤，产生真实的结果。目标是尽量让客户端的工作最小化。(www.chuimin.cn)

下面举一个例子加以说明，令R和T为两个关系。

●选择算符（σ）：σC（R）是关系R上的一个选择运算，C是与R上的属性A1，A2，…，An相关的选择条件。这样一个算符的直接实现是把关系RS从服务器端传输到客户端。然后，客户端使用D算符解密结果和实现选择运算。然而，这个策略把整个选择实现工作推给了客户端。此外，整个加密关系需要从服务器端传输到客户端。一种替代机制是使用C中涉及属性的索引将部分选择运算工作放在服务器端进行计算，再把结果推送给客户端。客户端解密传输过来的结果，过滤掉不满足C的元组，即

以σeid＜395∧did=140（emp）为例，使用前面所说的映射函数Mapcond（C），这个查询演变成：

其中：服务器端的条件C′是：

C′=Mapcond（C）=［eidS∈［2，7］∧didS=4）

●连接算符（∞）：考虑一个连接运算R∞CS，其中C可以是连接条件，可以是等连接，也可以是不等连接。这样一个连接可以实现为：

例如，连接运算：

emp∞emp.did=mgr.did mgr

可以翻译为：

其中：C′是C的映射结果。值得一提的是，连接运算∞也映射成∞S，因为条件变了，所以运算形态也得有所变化，以保证获得正确的结果。

3.查询执行

给定一个查询Q，先把Q分解成两部分，一部分交给服务器端，一部分交给客户端。下面是一个例子（这个例子选自参考文献［2］，需要了解细节的读者请阅读参考文献［2］）。

SELECT emp.name FROM emp

WHERE emp.sa lar y>(SELECTAVG(sa l ar y)

FROM emp WHERE did=1)；

图13.6是原始查询对应的原始查询树。图中的QC表示客户端实施的查询，QS表示服务器端实施的查询，PH指的是隐私同态（privacy homomorphisms）^[1]。如果采用第一种策略，则简单地把加密后的emp表传输到客户端，在客户端解密域实施查询，如图13.7所示。另一种策略是分解查询（称为内查询），一部分让服务器端实施，选择出对应Mapcond（did=1）的元组。然后服务器端将emp表的加密版本emp S里满足内查询的元组集（加密形式）传输给客户端。客户端解密收到的结果，选出在部门号1工作的雇员，再把结果返回给用户（见图13.8）。图13.9则是图13.8的一种变形，服务器端和客户端多次交互，如先在服务器端对内查询进行评估，选出did=1的雇员，再把结果发送给客户端，解密后计算平均工资。平均工资加密后再发送给服务器端，计算连接。接着把结果发送给客户端解密。

限于篇幅，这些图的含义及细节这里不再赘述，关于细节和其他运算，请读者参见参考文献［2］。

pagenumber_ebook=279,pagenumber_book=264