[發(fā)明專利]具有內(nèi)容隱藏的布隆過濾器的安全私有數(shù)據(jù)庫查詢

有效

• 申請?zhí)枺?/td>: 201380050145.6
• 申請日: 2013-09-18
• 公開（公告）號: CN104662556B
• 公開（公告）日: 2018-03-02
• 發(fā)明（設(shè)計(jì)）人: V·Y·柯勒斯尼科夫
• 申請（專利權(quán)）人: 阿爾卡特朗訊公司
• 主分類號: G06F21/62
• 分類號: G06F21/62
• 代理公司: 北京市中咨律師事務(wù)所11247
• 代理人: 楊曉光,于靜

政府權(quán)利聲明

本發(fā)明是關(guān)于經(jīng)由內(nèi)政部(DOI)合同No.D11PC20194通過先進(jìn)智能研究項(xiàng)目活動(dòng)(IARPA)而執(zhí)行的工作而做出的。

技術(shù)領(lǐng)域

本發(fā)明一般涉及用于安全私有數(shù)據(jù)庫的私密性保護(hù)技術(shù)。

背景技術(shù)

當(dāng)各方擁有共同關(guān)注的數(shù)據(jù)時(shí)，已經(jīng)利用安全匿名數(shù)據(jù)庫搜索。參見例如M.Raykova等在(2009年11月)云計(jì)算安全研討會(huì)(CCSW)上發(fā)表的“安全匿名數(shù)據(jù)庫搜索”(M.Raykova et al.,"Secure Anonymous Database Search,"Cloud Computing Security Workshop(CCSW)(Nov.2009))；以及V.Pappas等在(2011年12月)第27屆年度計(jì)算機(jī)安全應(yīng)用會(huì)議(ACSAC)會(huì)刊上發(fā)表的“在現(xiàn)實(shí)世界中的私人搜索”(V.Pappaset al.,"Private Search in the Real World,"Proc.of the 27th Annual Computer Security Applications Conference(ACSAC)(Dec.2011))。一般地，安全匿名數(shù)據(jù)庫搜索技術(shù)允許客戶端搜索駐留在服務(wù)器上的信息，而不向服務(wù)器披露客戶端身份或查詢內(nèi)容。同時(shí)，服務(wù)器被保護(hù)，即僅向被授權(quán)的客戶端授予查詢能力并且客戶端不會(huì)得知與查詢無關(guān)的任何東西。

在一個(gè)示例性實(shí)現(xiàn)中，服務(wù)器S采用用于每個(gè)條目的單獨(dú)密鑰來加密數(shù)據(jù)庫，并且向索引服務(wù)器IS提供經(jīng)過加密的數(shù)據(jù)庫。此外，服務(wù)器S創(chuàng)建也被提供給索引服務(wù)器IS的經(jīng)過加密的搜索結(jié)構(gòu)。當(dāng)客戶端C想要查詢數(shù)據(jù)庫時(shí)，客戶端C加密查詢，向索引服務(wù)器IS發(fā)送它，并且由索引服務(wù)器IS使用經(jīng)過加密的搜索結(jié)構(gòu)盲執(zhí)行查詢。

為了減少關(guān)于查詢和響應(yīng)的信息泄露，經(jīng)過加密的關(guān)鍵字的布隆過濾器(“Bloom filters(BF)”)已經(jīng)被用作搜索結(jié)構(gòu)。異構(gòu)元素(例如關(guān)鍵字)可以插入到布隆過濾器中。在稍后的時(shí)間，用戶可以通過檢查布隆過濾器的若干位被設(shè)置為1來檢查具體的元素是否插入到布隆過濾器中。

在利用布隆過濾器的安全匿名數(shù)據(jù)庫搜索系統(tǒng)中，由索引服務(wù)器IS存儲(chǔ)的每一個(gè)經(jīng)過加密的數(shù)據(jù)庫行具有關(guān)聯(lián)的經(jīng)過加密的布隆過濾器。利用布隆過濾器檢查(由客戶端C提供的)經(jīng)過加密的關(guān)鍵字允許索引服務(wù)器IS確定關(guān)鍵字是否與對應(yīng)的數(shù)據(jù)庫記錄關(guān)聯(lián)，并且返回需要的記錄。由于關(guān)鍵字被加密，索引服務(wù)器IS不會(huì)得知查詢內(nèi)容。

Eu-Jin Goh的“安全索引”，密碼學(xué)電子文庫：報(bào)告2003/216(Eu-Jin Goh,“Secure Indexes,”Cryptology ePrint Archive:Report 2003/216(http://eprint.iacr.org/2003/216))通過提出使用布隆過濾器樹來改進(jìn)這樣的安全匿名數(shù)據(jù)庫搜索系統(tǒng)的可擴(kuò)展性。一般地，二進(jìn)制樹建立在與數(shù)據(jù)庫行對應(yīng)的布隆過濾器上，其中內(nèi)部節(jié)點(diǎn)是如下的布隆過濾器——該布隆過濾器包括在子樹的布隆過濾器中的任意一個(gè)中所包括的全部關(guān)鍵字。因?yàn)橥ㄟ^沿著布隆過濾器樹往下來識(shí)別匹配數(shù)據(jù)庫行，所以現(xiàn)在可以更快地搜索數(shù)據(jù)庫。

仍然需要可以處理比只是關(guān)鍵字搜索更復(fù)雜的查詢的安全匿名數(shù)據(jù)庫搜索系統(tǒng)。特別地，仍然需要可以處理需要公式評估(例如公式、范圍查詢、否定和近似)的查詢的安全匿名數(shù)據(jù)庫搜索系統(tǒng)。還有，對這樣的安全匿名數(shù)據(jù)庫搜索系統(tǒng)的另一需要仍然存在：該搜索系統(tǒng)可以處理需要公式評估的查詢而不披露布隆過濾器是否匹配公式的每一項(xiàng)。

發(fā)明內(nèi)容

一般地，提供方法和設(shè)備以用于具有內(nèi)容隱藏的布隆過濾器的安全私有數(shù)據(jù)庫查詢。根據(jù)本發(fā)明的一個(gè)方面，服務(wù)器提供在數(shù)據(jù)庫上由客戶端進(jìn)行的安全私有數(shù)據(jù)庫查詢，用于具有在至少兩個(gè)關(guān)鍵字A和B上的公式評估的查詢，通過：從數(shù)據(jù)庫接收包括經(jīng)過加密的布隆過濾器的布隆過濾器樹，其中該經(jīng)過加密的布隆過濾器包含經(jīng)過加密的關(guān)鍵字，其中，在布隆過濾器樹中的每一個(gè)布隆過濾器分別由隨機(jī)掩碼墊P來掩碼；從客戶端接收關(guān)鍵字A和B的經(jīng)過加密的版本；獲得用于關(guān)鍵字A和B的經(jīng)過掩碼的布隆過濾器索引；與客戶端一起參與安全功能評估(SFE)，其中服務(wù)器具有輸入，其包括用于關(guān)鍵字A和B的經(jīng)過掩碼的布隆過濾器索引，以及其中客戶端具有包括隨機(jī)掩碼墊P的輸入，以及其中安全功能評估包括以下步驟：由服務(wù)器從經(jīng)過掩碼的布隆過濾器索引輸入移除隨機(jī)掩碼墊P；確定是否存在用于關(guān)鍵字A和B中的每一個(gè)的匹配布隆過濾器；應(yīng)用公式評估從而確定是否滿足公式；以及生成結(jié)果。