[發(fā)明專利]弱泄露的高效揭序加密方法

有效

• 申請?zhí)枺?/td>: 201711345316.4
• 申請日: 2017-12-15
• 公開（公告）號: CN108234108B
• 公開（公告）日: 2021-06-22
• 發(fā)明（設(shè)計）人: 黎源;趙運(yùn)磊;朱揚(yáng)勇
• 申請（專利權(quán)）人: 復(fù)旦大學(xué)
• 主分類號: H04L9/06
• 分類號: H04L9/06
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;陸尤

本發(fā)明屬于密碼技術(shù)領(lǐng)域，具體為一種弱泄露的高效揭序加密方法。本發(fā)明包含初始化、加密和比較算法三元組，將其表示為；對于每個揭序加密方案來說，都會伴隨一定的明文信息量的泄露。其中，滿足理想安全性的揭序加密所泄露的信息則是密文對應(yīng)明文的大小關(guān)系。本發(fā)明在滿足高效性的基礎(chǔ)上，將泄露的信息盡可能的減少，即只泄露明文大小關(guān)系、明文最高不同比特位相等模式和明文最高不同比特位的部分信息。方案的構(gòu)造僅使用了偽隨機(jī)函數(shù)和哈希函數(shù)兩種高效的密碼學(xué)原語，使整個方案得以高效執(zhí)行。

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

本發(fā)明屬于密碼技術(shù)領(lǐng)域，具體涉及私鑰加密中的揭序加密方法。

背景技術(shù)

預(yù)備知識和符號標(biāo)示：

哈希函數(shù)H是一個從定義域到值域的映射，即H：{0,1}^m→{0,1}ⁿ。其中，該定義域可以任意長度的比特串集合{0,1}^*，或者是某個長度固定的比特串集合{0,1}^m，值域則往往是某個固定長度的比特串集合{0,1}ⁿ。這里，要求m比n大，即體現(xiàn)出哈希函數(shù)的壓縮性。一個哈希函數(shù)具有抗碰撞性，則要求從定義域中找到兩個不同的值x和x'，使得滿足H(x)＝H(x')是計算不可行的。一個哈希函數(shù)具有單向性(又稱抗原像攻擊)，則要求對于從值域中任意給定的y，找到x并使得滿足H(x)＝y(tǒng)是計算不可行的。有幾個哈希函數(shù)在密碼學(xué)中被廣泛使用：比如MD5將任意長度的數(shù)據(jù)轉(zhuǎn)換為一個128-位的0-1串，而另一個常用的哈希函數(shù)SHA的輸出是160位的0-1串。哈希函數(shù)范圍可以非常廣泛：從一個簡單的混合(mixing)函數(shù)到一個具有偽隨機(jī)輸出性質(zhì)的函數(shù)。具有偽隨機(jī)輸出性質(zhì)的哈希函數(shù)在密碼學(xué)分析中常被理想化為一個“隨機(jī)預(yù)言機(jī)(random oracle)”。常用的偽隨機(jī)函數(shù)也出于此。一個帶密鑰的函數(shù)F：{0,1}ⁿ×{0,1}^m→{0,1}ⁿ是偽隨機(jī)函數(shù)，則需要滿足對任意多項(xiàng)式時間的敵手都無法區(qū)分F_k和f_n，其中k為從{0,1}^m中均勻隨機(jī)選取，而f_n則是從定義域和值域都為n的函數(shù)集中均勻隨機(jī)選取。

揭序加密和保序加密的主要應(yīng)用方向?yàn)榘踩珨?shù)據(jù)庫系統(tǒng)，如Popa提出的CryptDB。有了這兩種密碼學(xué)工具，范圍搜索和排序等基于大小關(guān)系的數(shù)據(jù)庫操作能直接作用于密文之上，從而提供了滿足安全性要求的數(shù)據(jù)庫系統(tǒng)。保序加密先于揭序加密被提出，其中，提出揭序加密方案的初衷是為了繞開保序加密中的一個否定結(jié)論，即不存在高效且滿足理想安全性的保序加密方案。揭序加密最早由Boneh等人提出，然而該方案基于多線性映射的構(gòu)造以及目前多線性映射技術(shù)的不成熟導(dǎo)致其方案毫無效率可言。隨后，Chenette等人構(gòu)造了一種高效的揭序加密方案，但是其泄露的信息量較多，包括明文大小和最高不同比特位。為減少方案泄露信息量，即提高方案的安全性，Cash等人利用雙線性映射構(gòu)造了一種揭序加密方案，該方案泄露的信息量包括明文大小順序和最高不同比特位的相等模式，嚴(yán)格少于Chenette等人的方案所泄露的信息量，但在比較算法中大量的使用雙線性映射操作降低了方案的效率。因此，基于在加密數(shù)據(jù)庫上重要的應(yīng)用，揭序加密最近幾年受到了眾學(xué)者廣泛的關(guān)注。

一個揭序加密方案包含初始化、加密和比較三個算法元組ORE＝(ORE.Setup,ORE.Encrypt,ORE.Compare)，分別滿足下面三個性質(zhì)：

ORE.Setup(1^λ)→sk。該算法輸入一個安全參數(shù)λ，輸出一個私鑰作為加密算法中的密鑰。

ORE.Encrypt(sk,m)→ct。該算法輸入私鑰和明文，生成一個密文c并將其作為算法的輸出。

ORE.Compare(ct₁,ct₂)→b。該算法輸入兩個密文，輸出一個比特b∈{0,1}用于表示密文對應(yīng)明文的大小關(guān)系。