LBS中外包空间数据的kNN安全查询方法

第38卷第1期

2021年1月

计算机应用与软件

Computer

Applications

and

Software

Vol

.38

No

. 1

Jan

. 2021

LBS

中外包空间数据的

kNN

安全查询方法

梁丽莎1卢来〃吴卫祖2

1 (广东海洋大学寸金学院广东湛江524094)

2 (广东海洋大学数学与计算机学院广东湛江524088)

摘要

云计算服务允许数据拥有者将数据库外包出去，从而避免高昂的存储和计算资源，该方法的关键在于

既要对第三方服务提供商保持数据的机密性,又要为认证用户提供实时查询结果。对此，提出一种转换和加密方

法，应用到服务提供商在空间数据集上执行用户查询和响应过程中。采用空间填充

Hilbert

曲线将多维空间的每

一个空间点映射到单维空间；基于顺序保留加密技术处理转换的空间数据；用户向服务提供商发起基于

Hilbert

值的空间

kNN

查询，并应用加密密钥对查询响应进行解密。实验证明该加密方法能减少认证用户与服务提供商

之间的通信开销。

关键词

外包空间数据空间填充曲线加密

TP

中图分类号 399 文献标志码

A

DOI

:10.3969/

j

.

issn

. 1000-386

x

.2021.01.054

SECURE KNN QUERIES OF OUTSOURCED SPATIAL DATA

IN LOCATION-BASED SERVICES

1*

Wu

Weizu

2

1

(Cunjin

College

,

Guangdong

Ocean

University

,

Zhanjiang

524094,

Guangdong

,

China

)

2 (

Mathematics

and

Computer

College

,

Guangdong

Ocean

University

,

Zhanjiang

524488 ,

Guangdong

,

China

)

LiangLishaLuLai

Abstract

1

computing

resources

.

The

key

of

this

method

is

not

only

to

maintain

data

confidentiality

for

third-party

service

providers

but

also

provide

real-time

query

results

for

authenticated

users

.

This

paper

proposes

a

transformation

and

encryption

method

,

where

the

service

provider

executes

queries

and

returns

results

to

the

users

.

The

space-filling

Hilbert

curve

was

used

to

map

each

point

in

multidimensional

space

to

one-dimensional

space

;

the

converted

spatial

data

was

processed

based

on

sequential

preservation

encryption

technology

；

the

user

initiated

a

spatial

kNN

the

service

provider

,

and

decrypted

the

query

response

using

the

encryption

key

.

The

experiments

show

that

this

encryption

method

can

reduce

communication

cost

between

authorized

users

and

service

providers

.

Cloudcomputingservicesallowsdataownerstooutsourcedatabasestoavoidexpensivestorageand

Keywords

Outsource

Spatialdata

Space-fillingcurve

Encryption

〇引言

数据库外包是常见的云计算服务范例，数据所有

者可以充分利用其存储和计算资源。为了减少成本，

资源受限的公司可以将他们大量的数据外包给具有动

态存储和计算能力的第三方服务提供商。云计算由于

其方便性引起了较高的关注度，但是大量数据被不受

信任的第三方控制会引起机密性和隐私性的安全

问题。

移动设备和导航系统普遍使用基于位置服务（

Lo

­

cation

Based

Service

,LBS

) ， 导致需要妥善管理的空间

数据增加。日常生活中有大量用户使用

LBS

，他们以

匿名的方式发起空间查询并在有效时间内收到响应。

同样，数据所有者为了保护数据隐私性，不想将其透露

给服务提供商（

Service

Provider

,

SP

)，因此将数据外包

收稿日期：019 -07 -29。教育部高等教育司产学合作协同育人项目（2)。梁丽莎，讲师，主研领域:人工智能，智

能算法及应用。卢来，副教授。吴卫祖，教授。

326

计算机应用与软件

2021 年

给云服务提供商（例如：百度地图）。认证用户向

SP

发送信息查询请求时，数据所有者和用户都不想把真

实数据透露给服务提供商。

在把空间数据库外包到云平台上时，必须考虑以

下几点情况。对于恶意攻击者和服务提供商来说，数

据库内容必须保持隐藏。通过数据加密可以简单地保

护用户数据隐私，即数据所有者加密整个数据库，并且

将加密数据（不带任何其他信息）发送给

SP

。在查询

期间，认证用户从

SP

处获取所有的加密数据，然后解

1相关研究

移动设备和导航系统的大量应用使

LBS

迅速发

展起来。文献[-9]提出通过在

SP

处增加一个中间

设备或者防干扰设备来确保安全性。该设备通过对传

送的消息加密和解密来协助处理查询。假设在服务器

端存在一个可信设备，文献[9 ]提出一种快速查找加

密技术用于非顺序保留

AES

加密。数据库所有者先

密并搜索需要的数据点。这样虽能保证安全，但是由

于其产生的通信开销极高，尤其是当用户只需要一小

部分数据点时，在实时应用中并不可用。

现有的保护外包数据的方法大部分采用空间变

换机制[1-3]或者密码学技术[4-6]。然而大多数的保

护机制都会在数据机密性和查询过程有效性之间权

衡。为了解决这些问题，本文提出一种两层编码方

法，先转换数据，然后对转换空间加密。此外，查询

过程只需要在用户和云服务提供商之间通信一次就

可实现。采用

Hilbert

空间填充曲线（用户定义曲线

参数）来变换空间数据点。由

Hilbert

索引范围定义

数据包列表，然后用顺序保留加密（〇

rder-Preserving

Encryption

，

OPE

)技术[7]对列表加密，

OPE

支持在服

务器处执行空间

kNN

查询。采用0

PE

的优势在于

其将原始距离值隐藏，在

SP

处通过简单的对比来正

确评估。另外，数据所有者向认证用户提供密钥，用

转换密钥和加密密钥向

SP

发送编码查询，最后用

0

PE

密钥解密查询响应。

云架构模型主要由三类实体构成，分别为:数据所

有者

（Data

Owner，DO

)，服务提供商

（Service

Provide

，

SP

)和认证用户

（Authorized

User

，

AU

)，如图1所示。

DO

外包其空间数据点，在外包给

SP

之前通过变换和

加密数据库确保数据的安全性。

AU

利用变换密钥向

SP

发起加密的

kNN

查询。该查询在

SP

处在加密数据

库上处理并将结果返回给用户。

AU

利用密钥解密查

询响应来获取真实的查询结果。

基于一维值建立一个

B

树，然后加密每一个节点级的

记录来防御非受信任

SP

攻击数据。

然而，在用户数量越来越多的情况下，

SP

处单台

设备服务每一个

AU

已经不现实。为了解决这个问

题，文献[]提出一种基于密码的转换机制来确保二

维数据的安全性:

DO

采用

R

*树架构来索引数据库并

采用

AES

加密算法加密每一个节点;根据

R

*树服务

器与用户之间的深度大小，查询过程需要多个回合，导

致通信开销的增加;

SP

向

AU

发送加密的根节点

，AU

利用密钥解密节点，然后请求子节点与查询区域重叠，

直到找到相应数据点的叶节点。

类似地，文献[5 ]提出一种基于

Hilbert

曲线转换

的密码机制来平衡数据安全性和查询效率之间的关

系。采用

Hilbert

曲线将数据局部聚类，并用

AES

加密

转换数据。加密文件安全地存放在

SP

处。查询过程

首先将整个加密文件发送至

AU

，解密之后搜索与查询

内容相关的记录。但该方法后来被证明需要消耗大量

的时间。

除上面提到的密码技术以外，学者还提出了基于

空间位置分割和再分配的空间变换方法，如:空间层次

划分

（Hierarchical

Space

Division

，

HSD

)、基于误差变换

(

Error-Based

Transformation

,

ERB

)和

HSD/ERB

混合

变换[4]。文献[10]提出另一种空间变换机制，通过切

边变换和路由变换提供数据安全性。然而，这些技术

均需要保留原始空间点的坐标，并且假设攻击者能够

获取原始点和变换空间中原始点坐标的背景信息，暴

露了数据点附近的信息。

对用户而言，保证查询过程的即时性是

LBS

的关

键，因此数据库外包必须使用低通信开销技术，需要对

空间数据和查询区域进行编码。大多数现有的研究成

果并没有利用

SP

的计算能力，基于此本文提出一种服

务器端针对加密数据的安全有效的

kNN

查询方法来

解决这一问题。

第1期

梁丽莎，等:

LBS

中外包空间数据的

kNN

安全查询方法327

2加密空间变换

的方式保存，并可以在加密数据上评估查询。最后，

DO

向

AU

发送

OPE

密钥来加密查询

Hilbert

单元，并

将

SP

返回的查询结果解密。

3

kNN

为了保证空间数据的机密性，原始空间的二维数

据点以两种方式隐藏：（1)利用

Hilbert

空间填充曲线

将空间中的二维点转换成一维点；（2)利用

OPE[11]M

密生成的

Hilbert

单元值，然后用

AES

加密产生的数据

点。变换密钥和加密密钥都通过

SSL

协议由

DO

直接

发送至

AU

。

查询过程

本文主要关注

LBS

中应用最为广泛的二维空间

kNN

查询。评估期间，将

kNN

查询转换成一组一维

Hilbert

单元值（部分或者全部与周围区域重叠

）。SP

2

.

1 Hilbert

数据包列表设计

首先将静态空间数据点分配到网格中，网格由

Hilbert

空间密钥[2]

(Hilbert

Space

Key

,

HSK

)根据曲线

生成。。/

S

尺=丨，其中：（&，◦)是曲线起始

点，0为曲线方向，〃为曲线顺序。

HSK

支持单向转换，

有可能出现两个或者多个点在曲线中有相同的单元

索引。

DO

创建

Hilbert

数据包列表

（Hilbert

Packet

Lit

，

HPL

)过程如下

:

首先，为空间中的每个数据点在网格

中分配一个

Hilbert

单元值。其次，基于单元值将数据

点存储到数据包中，每个数据包包括：匕（数据包起始

Hilbert

索引），匕（数据包结束

Hilbert

索弓丨）和匕（数

据包原始空间点固定值）。

PS

、

A

分别代表数据包中起

始和结束数据点的位置

，

匕由每个数据包存储的数据

点的数量

c

决定。

当曲线顺序^为3,为4时，

HLP

示意图如图2所

示。第一个数据包匕=〇,以

c

个数据点填充

Ce

是

数据包中第

c

个目标的单元索引。空

Hilbet

索引值表

示没有分配空间点，其一般不会在

HPL

中出现，除非

索引在

2

数据包填充完成之前发生冲突。

i_

22

I

3842

20

.L

25

lh

37

27

r

23"1'2436

---

39

1 40

43

19

.ft

18j 29

J

i

35

34Us44

Hilhert

数据似列表

e

：

28

>

16

1 17

:3031

丨

32

丨

33:46

47

15

J

<6

abcd>

—

u

」

，!12

i

J

'.j...

1110

卡

士

j 5

…

1

"

48

<1926efgh>

|

丨

m

14

1

J

«C I 8

9

54

49

<2850ijkl>

13 !

!!•

；

<5158mnop>

^ h

57

%

56

!61

62

°l

厂

n

3]|

14

55859 | 60

[

|

•

63l

p

图2

Hilbert

空间变换和

Hilbert

数据列表

2.2 OPE

为了进一步对空间数据进行编码，在将

HLP

发送

至

SP

之前，

DO

采用

OPE

技术对其加密。这保证了数

据不会被

SP

泄露给第三方中介。此外，为了阻止数据

的非认证访问

，SP

在使用数据之前没有能力解密数

据。因此，采用

OPE

机制确保明文数据的顺序以加密

和

AU

均参与处理查询过程。数据点及其

Hilbert

单元

值放入

HPL

，经加密之后存放在

SP

。

AU

通过定义查

询点发起

kNN

查询。通过定义圆形区域

（Circular

Re

-

gi

〇

n

，

CR

)可以发现查询点周围的

A

个邻近点。

AU

将

查询转换成一组落入该区域的加密

Hilbert

单元值。

利用

OPE

密钥加密查询请求然后将其发送至

SP。SP

通过比较加密的

Hilbert

起始和结束单元值范围，将相

关的加密返回给

AU

。

AU

利用密钥解密返回的结果

数据点，通过寻找查询点的&个临近点生成真实的查

询结果。

kNN

查询过程如图3所示。查询请求由

Hilbert

值重叠的

CR

组成。发送的

Hilbert

值相当于

HPL

的

起始和结束元组。两个元组中包含的加密数据点集返

回

AU

，用户从中取出需要的&个点。

图3

kNN

查询交换过程

算法1列出了空间

kNN

查询的处理过程。已知

查询点

Q

和点

Q

周围的圆形区域

CR

。步骤2)中

Hil

­

bert

单元与

CR

重叠生成查询 区域; 步骤 3) - 步骤 5)

中加密查询

Hilbert

单元并发送至

SP

;步骤6)-步骤

12)、步骤15)在

SP

处完成。与查询

Hilbert

单元值匹

配的元组返回至

AU

。如果返回数据点的数量小于&，

则重新定义个更大范围的

CR

并另外发送

Hilbert

单元

值给

SP

，之后的处理方法同上。此外，步骤16)-步骤

20)中，空间数据点在

AU

处加密，获得

Q

周围的&个

最近的数据点。

算法1空间

kNN

查询

输入:查询点

Q

。

输出

:kNN

结果为&个空间数据点。

1)

while

(

k

>

size

(

Result

))

328

计算机应用与软件

2021 年

2)

QueryCells

=

cells

contained

in

CR

around

Q

3 )

for

all

(

c

g

QC

)

4)

HilbertCells

=

HilbertCells

U

(

encrypt

)

Hilbert

(

c

)

5 )

end

for

6 )

for

all

(

p

g

HPL

)

7 )

while

(

HilbertCells

^

Psi

)

8)

if

(HilbertCells

g

[

PsiP

ei])

9)

Result

=

Result

U

Pci

10)

end

if

11)

end

while

4.

空间

kNN

查询处理时间

两个数据集中

SP

处理

kNN

查询（如搜索加密

HPL

)的消耗时间如图5所示，每个

kNN

查询的查询

点从区域空间随机生成。不同查询大小的查询时间均

为毫秒级别。&值越小，查询时间越短，且两个数据集

性能趋势大致相同。

12)

end

for

13)

Increase

the

radius

of

circular

region

,

CR

14)

end

while

15)

Return

Result

to

AU

16 )

for

all

(

yg

Result

)

17)

rD

=

Decrypt

r

18)

distNN

=

Compute

distance

between

Q

and

rD

19)

end

for

20 )

kNNResult

=

FindkNN

(distNN

)

4实验

通过实验对该方法进行有效性评估，采用多个参

数来衡量

Hilbert

变换效果，均展示出快速的系统响

应。实际环境为

Intel

Core

i

7 -3770

CPU

@ 3.40

GHz

。

以两个不同大小的真实空间数据集[2]为例：1)奥尔

登堡市

（Oldenburg

City

，0

C

)道路网，包含1 104个点；

(2)美国东北部

（North

East

，

NE

)，包含 123 593

个点。

4.1 Hilbert

空间密钥

Hilbet

空间变换利用

HSK

对空间数据库进行编

码。为了突出

HSK

的全面性，通过改变

Hilbet

曲线顺

序来分配数据点。〃值越大表示网格粒度越大，安全性

越高。分配给每个

Hilbet

索引值的平均点数量如图4

所示。随着^的增加，每个

Hilbet

索引值的平均点数

量急剧减少。对于数据集

OC

和

NE

，当^ = 5和^ = 8

实验中根据不同的

A

值生成随机

kNN

查询，并测

量在此交换过程中

SP

和

AU

之间的数据量，通信幵销

包括：）

AU

利用

HSK

将查询区域转换成一组

Hilbert

单元值并将其发送至服务器;2)

SP

搜索

HPL

中相应

的空间点并返回加密结果，用4个字节代表

Hilbert

单

元值，每个空间点为1字节。

OC

和

NE

中八取4种

不同大小值，10次查询的平均通信幵销如图6所示。

可以看出，随着查询大小的增加，发送的

Hilbet

单元

值和返回数据点也增加，通信幵销呈线性增长。当

A

=20时，与同样采用

AES

加密的

CRT

技术[]相比，

该方法响应时间比

CRT

技术快了 1.75倍。

第1期

梁丽莎，等:

LBS

中外包空间数据的

kNN

安全查询方法

329

[

二

]HPL

o

CRT

5

outsourced

private

spatial

data

[

C

]//2014

International

Con

­

ference

on

Big

Data

and

Smart

Computing

(

BIGJ

-

COMP

).

IEEE

,2014：77 -82.

[6]李远铭，严迎建，李伟.基于粗粒度可重构密码阵列的

AES

算法映射实现[

J

].计算机应用与软件，2018,35(3):

304 -308,326.

[7 ]马行坡，梁俊斌，马文鹏，等.面向双层传感网的安全

T

〇

p

-

k

查询协议[

J

].计算机研究与发展，2018,55 ( 11 ):

graphictransformationschemeforprotectingdataprivacyon

10

10 15 20

(b)

查

NE

询大小々

数据库

图6查询大小与通信开销关系图

5结语

云计算服务可以通过在服务器端虚拟存储和计算

资源，向认证用户提供数据的方式将数据集外包。为

了平衡服务器端数据的机密性和查询的有效性，本文

提出一种安全有效的

kNN

查询方法。利用

Hilbert

曲

线变换空间数据集，并引入顺序保留加密方法变换数

据来提高安全性。实验证明该方法比现有的加密方法

性能更好。该双重变换方法不仅为数据提供保护，而

且使认证用户能及时收到空间

kNN

查询回复。

参考文献

[1]王占兵，宋伟，彭智勇，等.一种面向密文基因数据的子序

列外包查询方法[〗].计算机科学，2018,45(6):57 -62.

[2 ]

Khoshgozaran

A,Shahabi

C

.

Blind

evaluation

of

nearest

neigh

­

bor

queries

using

space

transformation

to

preserve

location

pri

­

vacy

[

C

]//

l^roceedings

of

the

10

th

international

conference

on

Advances

in

spatial

and

temporal

databases

.

ACM

, 2007：

239 -257.

[3 ]

Ku

W

S,Hu

L,Shahabi

C,et

al

.

A

query

integrity

assurance

scheme

for

accessing

outsourced

spatial

databases

[

J

].

Geolnformatica

,2013,17 ：7 - 124.

[4 ]

Yiu

M

L，Ghinita

G，Jensen

CS，et

al

.

Enabling

search

serv

­

ices

on

outsourced

private

spatial

data

[

J

].

The

VLDB

Jour

­

nal

,2010,19(3) ：63 -384.

[5 ]

Kim

H

l

,

Hong

S

T，Chang

J

W

.

Hilbert-curve

based

crypto

­

150 -160.

[8 ]朱敬华，明骞.

LBSN

中融合信任与不信任关系的兴趣点

推荐[

J

] •通信学报，2018，39(7) ：57 - 165.

[9 ]

Damiani

E,Vimercati

S

D

C,Jajodia

S,et

al

.

Balancing

confi

­

dentiality

and

efficiency

in

untrusted

relational

DBMSs

[

C

] //

Proceedings

of

the

10

th

ACM

conference

on

Computer

and

communications

security

,

ACM

，2003 ： 93 -102.

[10]

Hossain

A

A，Lee

S，Huh

E

.

Shear-based

spatial

transforma

­

tion

to

protect

proximity

attack

in

outsourced

database

[

C

] //

2013 12

th

IEEE

International

Conference

on

Trust，Security

and

Privacy

in

Computing

and

Communications

.

IICEE

,2013 ：

1633 -1638.

[11]

Boldyreva

A

,

Chenette

N

,

O

?

Neill

A

.

Order-preserving

en

­

cryption

revisited

：

Improved

security

analysis

and

alternative

solutions

[

C

]

//Proceedings

of

the

31

st

Annual

Cryptology

Conference

.

Springer

,2011 ：578 -595.

[12]

Real

spatial

datasets

[

DS

/

OL

]. [2019 - 07 - 29 ].

http

：//

www

.

cs

.

fsu

.

edu

/

lifeifei

/

SpatialDataset

.

html

.

(上接第302页）

[6]刘世超，朱福喜，甘琳•基于标签传播概率的重叠社区

发现算法[].计算机学报，2016, 39(4)717 -729.

[17]

Moradi

F

,

Olovsson

T，Tsigas

P

.

A

local

seed

selection

algo

­

rithm

for

overlapping

community

detection

[

C

]//2014

IEEE

/

ACM

International

Conference

on

Advances

in

Social

Net

­

works

Analysis

and

Mining

(ASONAM

2014) ,2014.

[18]

Lancichinetti

A，Fortunato

S

，

Radicchi

F

.

Benchmark

graphs

for

testing

community

detection

algorithms

[

J

].

Physi

­

cal

Review

E

, 2008, 78(4) ：046110.

[19]

Chen

M

,

Kuzmin

K

,

Szymanski

B

K

.

Extension

of

modulari

­

ty

density

for

overlapping

community

structure

[

C

]//2014

IEEE^ACM

International

Conference

on

Advances

in

Social

Networks

Analysis

and

Mining

(

ASONAM

2014).

IEEE

,2014.

(上接第319页）

[18]

Jannach

D，Lerche

L，Gedikli

F，et

al

.

What

recommenders

recommend-An

analysis

of

accuracy

，

popularity

，

and

sales

diversity

effects

[

M]/Carberry

S

,

Weibelzahl

S

,

Micarelli

A

.

User

modeling

，

adaptation，and

personalization

.

Springer

，

2013：25 -37.