多维数据的完整性验证方法

—55—

多维数据的完整性验证方法

滕明岩

(渤海大学数学系，辽宁 锦州 121000)

摘 要：为解决在边缘计算环境下多维数据的完整性验证问题，提出一种基于数据间邻居关系的完整性验证方法。该方法通过寻找数据项在多维空间各个象限的最佳近邻建立数据项间的邻居关系。经过加密的数据项和其邻居关系能够保证结果集的数据完整性。实验证明了该方法在多维数据完整性应用中的有效性。

关键词：完整性验证；数据安全；多维数据；边缘计算

Completeness Verification Method for Multi-dimensional Data

TENG Ming-yan

(Department of Mathematics, Bohai University, Jinzhou 121000, China)

【Abstract 】To address the problem of completeness verification on multi-dimensional data in the applications of edge computing, this paper proposes a Neighborhood-Based Completeness Verification(NBCV) method. The solution creates the neighborhood of a data item by finding the nearest neighbor of the data item in each quadrant. The encrypted data items and their neighborhoods guarantee the completeness of the query results. Experimental shows that the proposed solution can be effectively applied in completeness verification of multi-dimensional data. 【Key words 】completeness verification; data security; multi-dimensional data; edge computing

计 算 机 工 程 Computer Engineering 第36卷 第20期

Vol.36 No.20 2010年10月

October 2010

·软件技术与数据库·

文章编号：1000—3428(2010)20—0055—03

文献标识码：A

中图分类号：TP311

1 概述

边缘计算作为一种重要的分布式计算模型，近年来得到了相当程度的关注[1]。边缘计算主要是为了提高分布式计算环境下服务器的吞吐率，从而支持更大规模的用户。在边缘计算模型下，系统所提供的数据和服务由少数中心服务器发布到大量的边缘服务器上[2]。边缘服务器直接处理用户的请求，从而使中心服务器的负载得到较大程度的降低。中心服务器通常起数据发布、用户管理等功能。它由数据和服务发布者来管理和维护。边缘服务器在接收到中心服务器发布的数据和服务后，处理用户的请求。由于边缘服务器很可能由第三方服务商提供，因此对系统的安全性提出了挑战。由边缘服务器响应的用户请求，很可能被第三方篡改，从而导致在边缘服务器上得到的查询结果与直接从中心服务器的查询结果不一致，系统的可靠性不能得到保障。

本文研究用户对服务器端提出的数据查询请求。用户想得到相应的并且是可靠的数据作为查询结果。为了解决边缘计算系统中数据的可靠性验证，用户从第三方除了得到查询请求的数据外，还要得到一些具有验证数据可靠性的验证信息。用户可以根据这些信息，对所得到的数据进行可靠性验证。边缘计算系统中的数据可靠性验证可分为2个方面：数据的正确性和数据的完整性。数据的正确性指从第三方获取的每一项数据都是中心服务器所发布的真实数据，而并非是经过第三方篡改过的数据。它可以简单地通过信息安全领域的对称性加密(公钥/私钥密钥对[3])的方法解决。数据的完整性是指所有满足用户查询请求的数据都能完整地返回给用户。没有任何正确结果的数据被忽略掉，也没有任何伪造的新数据来冒充正确的查询结果。

数据完整性问题可以定义为：给定一个数据集(或者数据库)D ，其被中心服务器发布到边缘服务器上。对于用户在客

户端提交的一个范围查询请求q (获取数据集D 中一定范围内的数据)，边缘服务器返回查询结果R ，以及相关的完整性验证信息V R 。基于R 和V R ，客户端可以判断数据集D 中所有满足查询请求q 的数据项是否都被成功返回到客户端。

数据完整性已有的研究[2,4-5]主要是基于Merkle 哈稀树的一维数据完整性验证。在这些研究方法中，相邻的数据项被串在一起并加密处理。这样数据间的相邻关系可以通过公有密钥/私有密钥对的方式，在客户端进行验证。然而，这些方法只能应用到一维数据上。由于多维数据间的相邻关系很难进行建模，因此还没有一个能够验证数据完整性的方法被提出来。本文通过对多维数据及多维空间的合理分析，提出了解决多维数据完整性验证的方案。

2 相关工作

在数据完整性验证方面已有一些研究工作[2,4-5]。绝大多数的研究工作需要数据发布者对数据集构建层次化的数字签名。用户端可以利用这些数字签名来验证每个查询结果。和本文最相关的研究工作是[5]：该方法需要数据发布者对其发布的数据集构建Merkle 哈稀树，并且将根节点的数字签名直接发送给用户。如图1所示，Merkle 哈稀树是一种二叉树。每个叶子节点记录一个数据项的哈稀值。例如：N 3=h (7)。其中，h ()为一个单向哈稀函数。Merkle 哈稀树的每个内部节点记录的是其2个子节点串联后的哈稀值。根节点则是Merkle 哈稀树所包含的所有数据值的一个数字签名。它最终在中心服务器上，通过数据发布者的私有密钥被加密。在图1中，根节点的数字签名是S (N 1~8)。

作者简介：滕明岩(1979－)，女，讲师、硕士，主研方向：数据完整性验证，信息检索，信息安全

收稿日期：2010-03-10 E-mail ：morange@https://www.wendangku.net/doc/4a9244431.html,