背景問(wèn)題

NN query：Nearest Neighbor query。

用戶需要找離自己最近的某些點(diǎn)，但是同時(shí)自己的準(zhǔn)確位置不能泄露。

之前研究的不足

傳統(tǒng)加密技術(shù)有O（n）的計(jì)算開銷，log級(jí)的通信開銷。

未開發(fā)節(jié)點(diǎn)的空間特性。

本文貢獻(xiàn)

1. 用Hilbert曲線，將原始空間（2D）轉(zhuǎn)換為編碼后的空間，存在服務(wù)器中，計(jì)算復(fù)雜度降為（得到的結(jié)果是近似值）

K是前K個(gè)最近點(diǎn)，N是Hilbert變換空間的維數(shù)

通信復(fù)雜度降為O(K)

2. 兩種位置隱私metric（比k-anonymity好）：

user-based?anonymity 叫 u-anonymity：混淆發(fā)請(qǐng)求user的身份

M是總user數(shù)

?area-based anonymity 叫 a-anonymity：混淆發(fā)送請(qǐng)求的user點(diǎn)的位置

A是所有點(diǎn)的全集

相當(dāng)于對(duì)于user和area，都加大了混淆的范圍，把局部混淆擴(kuò)展到全局混淆。

原理

結(jié)果集混淆：

混淆所有感興趣點(diǎn)

KNN盲估：滿足上述三個(gè)混淆的KNN請(qǐng)求。

單向（one-way）轉(zhuǎn)換，在轉(zhuǎn)換后的空間處理請(qǐng)求。

要實(shí)現(xiàn)上述轉(zhuǎn)換，會(huì)有精度損失。

兩個(gè)度量轉(zhuǎn)換結(jié)果好壞的自定義參數(shù)：

與原空間相同結(jié)果所占比

此公式有改進(jìn)空間

Hilbert轉(zhuǎn)換： ? ?每個(gè)點(diǎn)通過(guò)轉(zhuǎn)換，都會(huì)有一個(gè)H-value（相當(dāng)于把二維映射到一維），H-value可能會(huì)有重復(fù)相同的。

空間加密技術(shù)，key為

其實(shí)點(diǎn)坐標(biāo)（2維），方向角，，曲線規(guī)格系數(shù)

線下空間加密：對(duì)POI（point of interest），即查詢的目標(biāo)點(diǎn)，進(jìn)行空間編碼（每個(gè)點(diǎn)轉(zhuǎn)換出對(duì)應(yīng)的H-value）。

升序存放POI的H-value

線上請(qǐng)求處理：請(qǐng)求在意轉(zhuǎn)換的空間被處理，然后解碼得到原始目標(biāo)點(diǎn)。

計(jì)算發(fā)出請(qǐng)求的user的H-value

找離user的H-value最近的K個(gè)點(diǎn)，再自解碼，即得解。

以上方法僅用單Hilbert曲線，單Hilbert曲線的2個(gè)缺點(diǎn)：

1. 有的點(diǎn)之間歐拉距離近，但是H-value值可能差很多，比如起點(diǎn)和終點(diǎn)（在第一級(jí)Hilbert曲線中）

2. 近似解集和最優(yōu)解集，最多會(huì)有一半的點(diǎn)不同。

雙Hilbert曲線方法：

原始空間O，經(jīng)過(guò)Hilbert變換為A，A旋轉(zhuǎn)90度為B（A、B對(duì)應(yīng)不同的SDK）。A、B分別算自己的KNN，然后得到2K個(gè)點(diǎn)，解碼后通過(guò)歐拉距離，取最短的K個(gè)點(diǎn)為解。

位置查詢也可擴(kuò)展為Text相關(guān)的內(nèi)容。

實(shí)際使用結(jié)構(gòu)（標(biāo)題blind在于發(fā)送的東西都不含真實(shí)信息，且Key只有user和可信第三方有）

Q：

1.?Hilbert Curve 理論基礎(chǔ)？