原文来自 Hu et al. - 2018 - Searching an Encrypted Cloud Meets Blockchain A Decentralized , Reliable and Fair Realization
【翻译】
可搜寻加密贯串区块链 去焦点化、可托且平正的完结
概要 直接正在加密数据上施行搜寻是一项有远景的本领 它利用户恐怕更无效天时用数据(这些数据普通加密后外包给云办事供给商等远程办事器)。到今朝为止 大普遍现有的束缚规划都是针对于狡猾但猎奇(honest-but-curious)的办事器 而针对于好心(malicious)办事器的安全妄图还没有引起渊博的器重。
直到迩来 才有一些争论束缚了可验证妄图(verifiable designs)的课题 即数据一切者也许验证搜寻了局的齐全性。没有过 这些验证体制高度依附于一定的加密搜寻索引组织 并且没有支柱繁复的盘诘。所以咱们空洞一个通用的验证体制 使它也许合用于一切的搜寻规划。其余 当检测到一个没有狡猾(unfaithful)的办事器时 没有无效的对于策(如 奖励诈骗者)可用。
正在本文中 咱们研究了以太坊中的智能合约的潜力 以太坊是一种新兴的基于区块链的去焦点化本领 为可托以及透明的算计供给了一个新的表率(paradigm)。
经过用一个留心妄图的智能合约更换宗旨办事器 咱们构建了一个去焦点化的(decentralized)隐私损坏搜寻规划 数据一切者也许担心地领受正确的搜寻了局 而没有必耽心好心办事器的潜伏正确。为了更好地支柱理论利用 咱们还妄图了一个新的智能合约来完结搜寻组织的平正性 正在这个合约中 每个到场者(稀奇是正在多用户境况中)都失去了同等的周旋 并受到激发来按照正确的算计。这样 一个狡猾的人总能失去他应得的 而一个好心的人甚么也得没有到。最终 咱们完结了构建的底细 并将其摆设到一个个别摹拟收集以及一个官方的以太坊测试收集中。大度的测验以及评估证实了咱们的去焦点化隐私损坏搜寻规划正在加密数据上的有用性。
【弥补】狡猾但猎奇 办事器试图从保存的加密数据以及/或元数据中练习尽大概多的信息 但同时正确地施行可搜寻加密协议。
1、短序
因为保存以及算计资源须要的增添 如今的企业构造每每会把数据外包给云办事供给商等远程办事器。没有过因为外包数据大概蕴含敏锐信息 数据拥有者正在外包给办事器前每每都会挑选加密他们的数据(比如金融买卖信息、疗养病历等数据)。但这反过来又会阻碍数据的利用 例如会阻碍时常用到的搜寻操作。
自从正在可搜寻加密方面的开创性处事[1]以后 许多争论都努力于妄图无效以及高效的体制 使搜寻恐怕正在加密数据上施行。正在大普遍现有的处事中 远程办事器被建模为一个狡猾但猎奇(honest-but-curious)的实体[2][3] 它从没有试图偏离规矩的协议。然而 正在实际中 好心(malicious)办事器大概只前往全体搜寻文件 以至前往压根与搜寻了局没有匹配的文件(比如 因为随机障碍)。更重要的是 一切安全马脚以及内部打击者均可能作歹取得改动数据算计的权力。当主机被好心(malware)软件习染(比如 电子邮件附件、受习染的P2P媒体) 进而给了打击者一个高拜候权力时 就会产生这种状况。为领会决这些课题 急迫须要针对于好心办事器的安全妄图来匆匆进加密数据搜寻的精深利用。
迩来 一些争论一经正在妄图可验证的隐私损坏搜寻规划 个中数据一切者也许验证搜寻了局的齐全性。即使如许 它们的验证本领(比如利用MAC[4]或散列表[5])高度依附于一定的搜寻规划 并且今朝只支柱简捷的盘诘办法 如单个枢纽字搜寻。若何对于现有的支柱语义以及繁复数据组织的盘诘(如如同度搜寻[6]或图组织的数据[3][7])等多种搜寻规划推广可验证性 今朝尚未争论领会。更主要的是 现有的可验证搜寻规划都是针对于舞弊动作(cheating)的检测 却没有跟进无效的应付办法(如奖励舞弊者punishing the cheater) 这极小地妨碍了该规划的扩张利用。以通用的pay-peruse模子为例 正在最坏的状况下 数据一切者大概会正在亏空金钱的同时失去一个正确的了局 而好心办事器则经过诈骗赢利。这昭彰须要正在加密数据上完结更切实的搜寻规划 没有仅须要可验证性来检测好心办事器的正确动作 还须要内置的平正体制来损坏数据一切者的好处。
为领会决上述课题 咱们开始留神到大概呈现诈骗的主要缘由是焦点办事器太弱小却没有受到监督。所以 咱们提议选择智能合约(smart contract) 这是一种新兴的基于区块链的去焦点化算计范式 正在以太坊(Ethereum)[8]中 一切操作都是透明切实的。没有须要宗旨办事器 而是将搜寻盘诘外包给智能合约 咱们没有仅能借助它失去正确的、弗成改动的了局 而且没有须要数据一切者的进一步验证。只有以太坊的安全失去保险 它就能彻底清除咱们对于好心对手的疑惑(misgivings)。
为了完结这一目的 咱们首次提出了去焦点化的隐私损坏搜寻规划Π 并且利用了今朝精深利用的散布式平台 以太坊中的智能合约。为了给一个规范的实例 咱们基于典范的反向索引搜寻对于称加密规划[5][9],正在以太坊中妄图出了相映的智能合约来克服原规划生存的各类课题(比如 燃料限制gas limitation )。其余咱们还夸大 咱们的组织(framework)是一个通用的组织 许多支柱繁复的表达性(比如 如同度搜寻)以及组织化数据(比如 图)的搜寻规划也顺应咱们的规划 它们也也许被改动为去焦点化规划。
为了进一步削减外貌可行性以及理论的隐私损坏搜寻规划之间的分歧 咱们留神到 正在实际天下中这种利用法式面前的枢纽激发体制是 数据拥有者指望将算计价值辽阔的处事外包给工人(即 处于云境况下的远程办事器) 算作回报 工人将取得特定数额的钱币算作人为。所以 咱们发觉性地利用智能合约来建立了一个平正的互惠体制 正在这个体制中 数据拥有者只有狡猾地支拨钱币 就也许收到正确的搜寻了局 而工人只有老实地按照合约 就也许失去人为。
其余 咱们还思虑了一个更繁复的场景 即多用户境况[2][10] 数据拥有者大概宗旨于经过与合法用户共享数据库来赢利。所以 咱们提出了一个平正的隐私损坏搜寻规划 并妄图了一个新的智能合约 它恐怕正在多用户境况中追踪各方的钱币人为状况 席卷买卖用度。所以该体制也许确保只有数据拥有者揭示了剧本(transcipt)进而禁止其他用户搜寻数据库的文字纪录 那么他就能赢利 只有用户支拨了人为 那么他就也许失去正确的搜寻了局。
综上所述 咱们的主要奉献以下
• 运用以太坊(Ethereum)的智能合约(smart contract) 咱们首次提出了一种去焦点化的隐私损坏搜寻规划Π 保险数据一切者收到正确的搜寻了局 并且正在面对于好心对手时无需施行验证。
• 正在此根底上 咱们还发觉性地引入了平正(fairness)的概念 并提出了一个平正的隐私损坏搜寻规划Π-fair 这样每个到场者 稀奇是正在多用户境况下 都能失去平正的周旋以及激发 以按照正确的算计。
• 咱们完结了妄图的底细 不同把规划摆设到一个要地摹拟收集以及一个官方的以太坊测试收集上。经过大度的测验以及评估 验证了针对于加密数据的去焦点化搜寻规划的可行性。
二、背景学识
A. 以太坊的智能合约
① Ethereum
以太坊是一个很有远景的基于区块链的去焦点化算计平台[8][11]。它的安全性由一组谜题(或块)的明码链来维护。以太坊收集中的矿工正在开采新块时验证并认同买卖。他们经过乐成地束缚一个指定的明码难题来打包(开采)一个新的块 并且取得回生成的加密钱币算作人为 进而激发他们去开采更多的块。这种激发体制保险了收集的正确性。总的来讲 以太坊为咱们供给了两个优厚的个性
• 共鸣。整体收集都招供该收集中的法则 进而去验证每个买卖以及块。正在以太坊上保存的数据以及施行的算计必需正在分歧的矿工之间完毕统一共鸣 并且没有能改动或承认。
• 透明。以太坊是一个众人收集。一切保存的数据以及施行的算计对于一切用户都是秘密透明的。
所以 以太坊算作一个可托的根底 它的正确性以及可用性受到信赖 而隐私没有受信赖。
② Smart Contract
以太坊中的智能合约是正在区块链中保存状态的利用法式。这些法式也许简化、验证以及逼迫公约的施行历程。每个由寻常地方(a special address)标识的智能合约由剧本代码(script coded)、钱币余额(currency balance)以及大局为键(key)/值(value)的保存空间(storage space)组成。一旦建立并摆设到以太坊 智能合约的代码就永久没有能被改动 以至建立者也没有能。
③ Gas System
燃料系统是智能合约中一个很是实用的功能。它恐怕升高对于以太坊收集的推辞办事(DoS)打击。全部来讲 智能合约的剧本被编译成以太坊操作码(op codes)并保存正在区块链中。每个操作码将破费特定数目的事先定义的燃料gas[8]。当经过发送买卖来煽动智能合约时 买卖提议人必需指定支柱施行的可用的燃料下限(gas Limit) 和提议人承诺为每单元燃料支拨的相映的燃料人为(gas Price)。只要当提议人的余额大于gas Limit×gas Price时 买卖才会被乐成蕴含正在区块链中。
正在咱们的组织中 咱们利用了可变输入长度伪随机函数(PRFs) 它是多项式时光的可算计函数 没有能正在一切多项式时光的概率内被对手手从一些随机函数中识别进去。正在[12]中也许找到PRFs的正式定义。
三、打算处事
正在图1中 咱们总结了咱们的妄图架构(architecture)。咱们的规划由以下三种算法组成
•Setup(DB): 数据拥有者输入数据库DB 失去输出三元组(EDB、K、δ) 个中EDB是加密数据库 K是密钥 δ是数据拥有者的状态(state)。
•Search(K,δ,w;EDB): 数据拥有者输入密钥K 自身的状态δ 和一个搜寻枢纽词w∈{0,1}∗ 然后向智能合约输入加密过的数据库EDB。接着智能合约输出一组标识符(identifiers) 而数据拥有者没有输出。
•Update(K,δ,op, id, Wid;EDB): 数据拥有者输入密钥K 状态δ 操作op∈{推广add、节略del} 文件标识符id 以及一组分歧的枢纽字集中Wid 并向智能合约输入EDB。这些输入的操作示意经过标识符id 对于文件施行推广或节略操作。
为了便于领会 咱们没有正在后面的组织(framework)中揭示对于数据文件的全部加密操作 由于数据拥有者也许很轻易地经过传统的对于称加密规划来加密数据 然后将加密数据外包给一切去焦点化的文件保存收集(比如星际文件系统IPFS)。
一个数据库DB (idi,Wi) d i 1便是一组标识符-枢纽词对于(identifier-keyword pairs) 个中idi∈{0,1}l Wi⊆{0,1}∗。数据库DB的枢纽字集中为W ∪di 1Wi。给定枢纽字w∈W的文档集中为DB(w) {idi | w∈Wi}。咱们总是将m |W| 以及 N ∑w∈W |DB(w)| 不同设为分歧枢纽词的数目以及数据库中一切枢纽字-文档对于(keyword-document pairs)的数目。
Fairness平正。隐私损坏搜寻的平正性是本文争论的中心。咱们的当中结论是基于实际天下中此类利用面前的激发体制的经济性子。宽泛地说 咱们的平正观念将保险
• 只有数据一切者为矿工的搜寻处事付费 那么他就能失去正确的搜寻了局 只有矿工狡猾地按照协议 那么他就能取得人为。
• 正在多用户境况中 除上述要求外 其他用户只有为矿工的搜寻处事和对于数据一切者的数据拜候动作付费 那么用户就也许失去正确的搜寻了局。数据一切者只有揭示剧本(如 搜寻令牌ST)就也许赢利。
总之 平正保险了每一方都有能源去做正确的算计。假设一方违反(deviates)协议 那么他甚么也得没有到。
Soundness稳重性。这个属性示意假设办事器试图违反协议 它将被拿获。往日的争论常常是让数据一切者施行一系列的验证来到达稳重性。不过正在本文中 咱们扩充了这一概念 咱们默认领受到的搜寻了局是可托(reliable)且一致正确的(correct definitely) 所以数据一切者没有须要对于搜寻了局施行验证。
Confidentiality失密性。咱们应该确保数据文件(file)和盘诘枢纽字(keyword)是失密的 使它们没有被对手所知。其余 咱们的目的是供给另一个弱小的安全概念 更进一步的隐私(forward privacy).
四、妄图寻衅与对于策
直不雅地说 一切现有的隐私损坏搜寻规划均可以用智能合约更换宗旨办事器 进而直接建立去焦点化的境况。不过 一些保险智能合约的强健性以及安全性的改革特征反而成为现无方案与智能合约混合历程中的妨碍。正在这一全体中 咱们提出了一些主要的妄图寻衅 并正在较高的层次上归纳了对于策。
燃料系统Gas SystemGas Limitation燃料限制。正在以太坊中 正在挪用智能合约中函数时所施行的每一笔买卖都有一个消费燃料的下限 称为gas Limit 如第II-A节所述。每个操作 席卷发送/保存数据以及施行算计 都有流动的燃料老本。这就限制了所妄图函数的算计方法以及保存空间。所以 为了使正在大型数据库上施行隐私损坏搜寻变得可行 咱们宗旨于将数据库划分为更小的数据库并零丁办理它们。约略思维以下 正在构建大型加密索引( EDB)的Setup 指令中 咱们将加密索引划分为多少个块(blocks) 并将它们上传到拥有渊博多买卖的智能合约中 这样每笔买卖破费的gas就比gas Limit少。为了确保正确性 合约须要将数据罗列(align)正在一统 以前往一切匹配的了局。
Gas Availability燃料的可用性。正在智能合约中 每笔买卖还与一个gas Price相关 该代价指名了发送方承诺破费几许钱(以太币ether)来采办一单元gas。以太坊中须要煽动买卖的用户的帐户余额大于施行买卖的燃料老本(cost) 不然买卖将中途停止 并且已破费的燃料没法退还。所以 思虑到燃料老本 咱们应该很是提防地妄图智能合约。一方面 咱们要确保智能合约中的每项功能函数(如搜寻Search、更新Update)的燃料老本没有逾越发送方的账户余额 另一方面 咱们应该适时跟进每次指令(phase)施行所破费的燃料量(gas consumption) 这样才华最终保险平正。更多对于燃料可用性的要求 咱们正在第七节中的协议中施行了阐明。
验证者窘境正在以太坊中 矿工被要求验证买卖的无效性(validity)。然而 当智能合约中有大度繁复的表达式时 验证买卖大概须要破费很大的算计价值。所以对付理性(?)的矿工来讲 他们会宗旨于跳过那些价值辽阔的买卖验证方法 以便正在开采下一个区块的比赛中维持跨越。这种征象称为验证者窘境[13]。
为了削减这种打击 咱们指望尽大概地削减智能合约的算计负担(burden)。
咱们的第一个设法是 智能合约支柱字典(dictionary)数据类别 而主要的算计价值正在于Search指令。所以 咱们利用字典数据类别来保存加密索引(即 EDB) 进而使搜寻的时光繁复度为O(dw) 个中dw是枢纽字w曾经经(historically)被推广到数据库的次数。——w所蕴含的文件数目 |DB(w)|
咱们的第二个优化是运用打包办法(packing method) 这个灵感来自[9]。全部来讲 咱们也许打包多个明文 然后对于打包了局施行加密 进而取得一个巨细不异的密文。所以 最终的搜寻了局是打包块而没有是单个(individuals)。其余 打包也利于咱们潜伏以前提到的燃料限制 由于它大大升高了保存老本。没有过咱们留神到 即使[9]声称也利用了打包方式 但没有清爽形容该若何完结它 而咱们正在第五节给出了精细组织(construction)。
五、去焦点化组织
正在本节中 咱们建立了一个去焦点化隐私损坏搜寻规划Π 并且这个规划拥有稳重性(soundness)以及失密性(confidentiality)。Π 是建立正在现有的开创性的反向索引组织(如[5][9])之上的。咱们将正在第八节中阐明 咱们的妄图原理也也许利用于其他拥有表达性盘诘或繁复数据类别的加密搜寻规划。
图2给出了Π 的正式形容。
为了简捷起见 咱们令F:{0,1}λ×{0,1}∗→{0,1}λ,G:{0,1}λ×{0,1}λ→{0,1}∗是两个伪随机函数(注 对付分歧的输入密钥 应该有分歧的伪随机函数 。利用 || 来示意连贯(concatenation)操作。“[·]”是一个向下取整函数(floor function) “|·|”示意列表中元素的数目。对付字典数据类别 它席卷 推广(Add)以及节略(Delete)两种算法。咱们利用术语Get来猎取字典中指定的数据项。比如 给定一个字典数据类别γ 以及一个输入标签l Get(γ,l) 将输出相映的项目d || r 并剖析成d以及r。——根底元素label-data 对于 r是相映的伪随奥秘钥
正在Setup指令中 数据一切者把数据库DB (w) 分为α 1个块 每个块有p个项目。这边p是由数据一切者所树立的系统参数。咱们利用串联接(concatenation)把多个文件标识符(id)打包成一个。为了失密性 打包了局id~ 的比拿手度应该小于安全参数λ的长度。所以 咱们有p≤λ/l 个中l是文件标识符的比拿手度。其它还留神到 正在上传数据库以前 列表L应该按字母秩序罗列。不然 它将暴露相关输入的处置秩序的信息。为了避免超越gas Limit 咱们将加密的数据库划分为n个块 并利用n个分歧的买卖把它们逐个发送到合约。正在智能合约端 它们迭代地(iterative)领受这n个买卖并利用字典数据类别将它们放正在一统。一致地 搜寻历程也将经过R次买卖告竣 每个买卖至多前往step个项。个中n、R、step为众人系统参数 并由测验决定最好值。
正在Search指令中 每次盘诘时 数据一切者把蕴含搜寻令牌(search token)的买卖发送到指定的智能合约。留神 每个合约正在以太坊中都有一个专一的地方。智能合约运用令牌以及事先储藏的加密索引(EDB) 施行Search算法并把搜寻了局(即 文件标识符id)保存到智能合约的状态(state) 该状态是众人的(席卷数据一切者正在内)。
支柱动静更新(Dynamic Updates)Π 支柱动静更新。正在Add指令中 咱们没有再利用打包办法去加密文件标识符(id)。由于把多个id明文加密成一个密文会使智能合约难以判别哪个文件-枢纽字对于(file-keyword pair)已被先前节略 即 它是否生存于集中ID del中。其余 正在理论状况中 普通只须要对于一个或多少个文档施行增删操作 因而Update算法的gas cost比gas Limit低很多。所以零丁地处置文件id有利于施行Update操作。对付智能合约的协议 里面的买卖触发函数(triggering function)没有前往一切了局 一切函数的施行只会改革它的状态 固然这个状态会万世保存正在以太坊上。咱们的规划便是经过将搜寻了局遗失到状态 然后数据一切者去读取状态 进而失去搜寻了局。
前向隐私(Forward Privacy)更进一步的隐私是本文一个主要的安全妄图目的。它意味着对于手没有分解新推广的文件是否蕴含往日搜寻过的枢纽字。这个灵感是收到了文献[5]的启发 咱们的规划Π 也许很轻易地扩充去完结更进一步的隐私。枢纽思维便是经过陷门加密(trapdoor permutation) 使得搜寻令牌(search token)与更新令牌(update token)没法关连起来。全部来讲 当DB(w)中的第c个文件天生伪随机标签(label)时 咱们没有再利用一个计数器c来示意推广 而是经过一个陷门加密 π βc π-1 sk(βc-1)并且标签树立为l F (K,βc) ——底本是直接用计数c个中β0是一个随机挑选的整数。然后正在于智能合约端 它只可正在多项式时光内用公钥算计βc-1 πpk(βc) 而没有能算计βc 1 由于它没有私钥。鉴于新参加到DB(w)的第(c 1)个文件没有被搜寻过 因而就没有能从往日泄漏的搜寻令牌βc推导出它是否蕴含往日搜寻过的枢纽字。——对手用βc没法去搜寻第c 1个文件
这个革新的规划以及 Π有不异的通信繁复性度(communication complexity 并且数据一切者以及智能合约只推广一点由罗列(permutation)所形成的算计价值(overheads)。
六、安全证实
Soundness稳重性 直不雅地看 只有以太坊的安全性失去保险 那么咱们的规划Π 就拥有稳重性。这是由于假设智能合约正在以太坊上正确施行 那么搜寻了局将经过合约的状态而失去万世、秘密的保存。以太坊中的每个矿工均可以对于数据施行验证 并且它的共鸣(consensus)属性确保每个搜寻操作都能正确施行。
Confidentiality失密性 为了证实失密性 咱们遵守了可靠巴望的摹拟表率[9] 并正在咱们的组织中首次给出了三中状态暴露函数L (L1, L2, L3)的正式定义。
定理1. 假设G以及F是伪随机 那么咱们的规划Π正在非符合性打击模子中是L-secure的。
L是泄漏函数。
七、平正性
正在本节中 咱们将揭示若何利用智能合约来构建一个基于Π 的平正的隐私损坏搜寻规划。咱们对于平正的定义是对于安全多方算计[14]的一个变体 其灵感来自于迩来对于金融平正[15]的著作。咱们建指望到达这样一个目的 正在经济上激发每一方去施行正确的算计 假设没有狡猾的一方舞弊 那么他最终将一无所获。
单用户境况咱们对于隐私损坏搜寻规划中平正性的主要结论是 正在实际中 此类利用法式面前枢纽的激发体制是让工人(即正在云境况下的办事器)正在告竣依赖的搜寻义务后 恐怕取得金钱人为。鉴于此 一切现有的规划均可能碰到这样的状况 假设数据一切者先付钱 那么好心的(malicious)工人大概会违反协议 同时还赚到了钱。另一方面 贪欲的(greedy)数据一切者也大概会让工人施行搜寻义务而没有事先付费。了局 工人告竣义务后大概得没有就任何人为。
而咱们的规划Π 正在保险以前提过的稳重性以及失密性之外 也自然恐怕保险平正性。这是由于不管数据一切者想要施行甚么操作(比如 Search、Update) 他都必需先向工人(以太坊中的矿工)支拨一种名为Ether的加密钱币 这个钱币恐怕采办gas。智能合约正在每个矿机上主动施行 然后把正确的操作了局树立为状态 数据一切者去读取状态。
咱们要留神到 现有的可验证搜寻规划[4][5][16]没有支柱平正性。它们常常让数据一切者正在工人施行盘诘操作前就付款 然后再验证盘诘了局是否正确。然而 正在这种状况下 工人最终大概会正在没有按照协议的状况下赢利。这正在触及到金融课题的境况中显得尤为没有顺应。
多用户境况正在多用户境况中 数据一切者禁止第三方(即其他经过认证的合法用户)恐怕正在数据库中施行搜寻[2][10] 但这样办事就繁复多了。由于用户之间是互没有信赖的 而咱们须要确保每一方都失去平正周旋。全部来讲 咱们须要确保
数据一切者正在用户搜寻数据库时恐怕失去人为 用户付费后 恐怕失去正确的搜寻了局。为此 咱们改动了规划Π 构建了一个平正的隐私损坏搜寻规划Π-fair。
Overview总结. 图3给出了Π-fair的总结。鉴于智能合约上的每项义务都是秘密的 运用现有的本领(如广播加密[10]) 来推广或移除用户 使他们拥有搜寻权力是弗成行的, 由于这须要把私钥告知矿工。所以 咱们利用了文献[2]中规划的扩充版本 数据一切者领受用户的盘诘恳求 并天生相映的搜寻令牌 这样就以及他自身正在搜寻数据库一律了。
Notation符号. 这边给进去Π-fair主要用到符号示意。咱们利用$来示意加密钱币(即 以太币)。$Bowner以及$Buser不同是数据一切者以及用户的专一以太坊帐户余额。数据一切者为每次搜寻树立代价$offer 用户为每次搜寻支拨$deposit。施行搜寻操作Gsrch的gas cost是一个系统常数 查找操作GLsrch的gas limit以及每单元气鼓鼓体代价$gasPrice则由数据一切者指定。
Contract Design合约妄图. 图4揭示了Π-fair的合约妄图。Π-fair中的Search()全体与规划Π是全面不异的。为了简捷起见 这边咱们只将它用作一个子例程(subroutine) 并利用ST示意领受到的搜寻令牌 其他细节则节略。
为了保险平正性 咱们推广了时光限制T1 这个参数是由用户指定。正在T1时光内 数据一切者把搜寻令牌发送到合约中并赢利。逾越了T1 则用户的搜寻恳求过时 用户的押金将被退还。留神 禁止搜寻的一个主要条件是 押金(deposit)应该大于数据一切者的报价$offer与施行Search()函数的gas cost之以及。这是由于盘诘事情是由数据一切者提议的 并且gas cost也会从数据一切者的账户余额$Bowner中扣除。这是没有平正的 由于数据一切者仅仅触发了取代用户的盘诘事情。所以 用户必需支拨那些极度盘诘的用度 即gas cost。当搜寻处事停止时 数据一切者所破费的cost会被智能合约发送到账户$Bowner。其它还留神到 残余的押金则应该马上退还到用户帐户$Buser 以避让数据一切者带着退款跑路 方式是利用不异的搜寻令牌反复发送盘诘事情。
正在咱们的组织中 数据一切者也许经过线下(off-line)向用户发送搜寻令牌 并让用户自行提议搜寻买卖。正在这种状况下 公约须要稍作改动 $deposit只需大于$offer 并且令$cost只等于$offer。不过 咱们提议经过智能合约来传输以及纪录搜寻令牌 由于它会使一切诈骗动作显露正在大众中 而且假设数据一切者没有表露令牌 那么合约也许正在经济上奖励他。
八、组织的狭义化(generalization)
短期对于隐私损坏搜寻的争论都分散正在进步其表达力(expressiveness)上 比如支柱如同性搜寻[6]或开垦组织化加密(比如图形加密)[3][7]。但一切这些争论都面临重要的安全寻衅 好心的宗旨办事器正在一些时分大概只输出全体了局 以至输出没有正确的了局。针对于这个课题 只有束缚了咱们第四节提出的妄图寻衅 那些规划就均可以符合到咱们提出的去焦点化境况中去。
对付这种狭义化的最直不雅的查看是 智能合约理论上为咱们供给了一个切实且透明的“办事器” 没有过它的主要闭塞正在于若何处置智能合约中gas system的各类限制。而咱们提出的多少种对于策(如 把加密索引分块并零丁束缚它们、打包多个标识符并加密为一个)为若何束缚该课题供给了方便。利用了智能合约的规划 它就自然恐怕保险强健性 并且没有再须要与好心办事器打交道。其它 咱们正在图4中妄图的智能合约也为那些多用户境况供给了一个模板 以完结该境况下的平正性。基于此 咱们还恐怕根据一定的理论状况完满合约中的各类繁复多变的条件。比如 正在数据一切者指望与冤家共享他的照片的状况下[10] 代价$ offer也许树立为0 进而让其他人收费地搜寻数据库。
九、测验以及评介
咱们用5000多行代码去完结了规划Π 的底细(prototype) 席卷它的测试法式。咱们正在一台16GB内存 4个Intel当中i7-3770 运行Ubuntu 16.04.2的算计机上实例化了数据一切者。智能合约被摆设到一个要地摹拟收集TestRPC以及一个官方的以太坊测试收集Rinkeby上。数据一切者端以及智能合约不同利用Python语言编写 并利用Java script以及Solidity算作中间交互语言。咱们并没有稀奇揭示出规划Π-fair的了局 由于对付各类评介目标(比如,时光老本) 该规划的机能以及Π 一致 并且Π-fair也许经过对于Π 施加一系列的掌握条件进而很轻易地完结 而没有须要其他昭著的老本。
咱们用 HMAC-SHA256完结伪随机函数(PRF)以及随机预言机(random oracles)。鉴于以太坊今朝没有支柱HMAC实例化 咱们遵守了[12]中的HMAC规范组织 并不同利用Python以及Solidity来完结HMAC-SHA256。
为了避免超越gas Limit 正在Setup指令中 咱们把加密的数据库EDB分成了n个子集中 并不同发送到最终蕴含n个买卖的智能合约中。因为gas Limit随时光稳定 对付每笔买卖 咱们令列表L蕴含70个文件 每次打包的数目树立为p 8。其余 每次搜寻盘诘至多告竣了R个事情 每个事情至多前往step 47个文件。正在咱们的测验中 R 4可满意要求。
咱们利用了来自Enron电子邮件的数据集 它是一个纯文本文件的集中。咱们提取了电子邮件的一个子集 并从原始子分散挑选不停推广的子集算作文档集中 这些文档集中拥有分歧的编号(w, id)(即枢纽字/标识符)对于 表二归纳了这些数据集的枢纽属性。
摹拟收集测验为了揭示咱们规划的的可扩充性以及特殊的机能特征 咱们开始利用TestRPC正在要地构建了一个摹拟的以太坊收集。TestRPC是用默认配置初始化的 它很像可靠的以太坊境况 只没有过它的开采块的时光树立为0。这使得咱们也许埋头于智能合约上对于搜寻的机能 而没有思虑以太坊中那些耗时的开采历程以及繁复的收集境况(如广播迟延、买卖开采迟延)。
表三总结了分歧数据集上每个指令的时光老本以及买卖数目。这边D.O.以及S.C.不同代表“数据一切者”以及“智能合约”的时光老本。#Tx示意告竣相映指令所需的买卖数目。经过前往100个匹配的文件来评估搜寻时光。经过推广以及节略文件来揭示Update指令的价值 挑选该文件只会孕育一笔买卖。正在Setup指令中 与现有的数据一切者方主导效用的分散式搜寻规划分歧 智能合约的时光老本远远高于数据一切者。这是由于保存EDB须要告竣数千笔买卖 每笔买卖平衡破费4秒来操作。
为了揭示当中算法 图5(a) 给出了每次找到文件的搜寻时光随匹配纪录数目的改变图。咱们统计了30多个考察的平衡运行时光。失去的第一个结论是 较大的了局集的搜寻价值较小(正在每个匹配文档的根底上)。这归因于正在每次搜寻运行以前 将往日开采的块从磁盘加载到内存中的流动老本。这也注释了咱们的第二个结论 数据集越大 搜寻算法越慢。由于开采出的块越多 加载时光越长。
官方测试收集上的测验揭示咱们的规划的可行性 咱们把规划Π 摆设到以太坊的官方测试收集Rinkeby上 该收集也许效仿真正的损耗收集。因为余额有限 咱们只正在最小的数据库DB1上施行测验。咱们正在Rinkeby上的账户以及公约地方以下
• 0 x7aef688b95a1bee573d464766b3a6c0470b9b57b。
• 0 xece97a98da7f5dbeccb81e772dd04710e676aa96。
为了阐明开采历程对于效用的作用 咱们纪录了Setup指令中每笔买卖孕育的块数以及相映的gas利用量 如图5(b) 所示。总之 它蕴含350个买卖 每笔买卖都被开采到一个块中 块号从176 837到177 187没有等。挖矿的平衡时光是15秒 告竣整体Setup指令须要88分钟。这再次注释了为甚么树立的时光老本由智能合约掌握 而没有是像现有的焦点化搜寻规划那样由数据一切者掌握。其余 一笔买卖消费的平衡gas量为4,201,232。今朝 1 gas的老本约为1.8*10-8以太币 1以太币约合89美元。所以 每笔买卖的老本约为0.076以太(或6.7美元)。乍一看 对付只要盘诘须要的普通用户来讲 这些老本犹如有点低廉。没有过Π 仍然合用于许多可靠天下的场景。比如 集体的疗养档案对于每集体来讲都很主要。正确齐全的病史也许帮忙医生做出确切的疾病诊疗以及强健评估。正在这些高要求的状况下 为了猎取高度切实的数据而破费更多的钱依然值得的。
图6(a) 揭示了给定搜寻令牌后 施行搜寻所需的总时光(咱们轻视了天生搜寻令牌的老本 由于它是一个微秒级的小常数)。图中每个点都是10次施行的平衡值。它也领会地核剖判Π 的机能弊端 咱们也许看到搜寻时光随着匹配文件数想法推广而推广。但形成赶紧增添主要缘由是告竣搜寻义务所须要的买卖数目的推广。这说明开采每个买卖的时光老本占了每个搜寻的支出。相反 搜寻算法自己对于效用的作用是微小的。普通状况下 挖矿历程的时光老本是动静可调的。当区块链境况扩充到禁止更高的gas Limitation或更快的挖矿历程时 咱们的搜寻效用也会进步。
一致的状况呈现正在图6(b) 中 它揭示了随着推广/节略文件所需的买卖数想法改变而改变的时光老本。经过挑选分歧巨细的文件 咱们也许经过分歧数目的买卖来告竣Update。这再次说明 每笔买卖的开采历程是作用效用的主要因素。
十、结论
传统的隐私损坏搜寻规划依附于一其中央办事器来施行搜寻义务。而正在本文中 咱们借助区块链本领 组织了一个针对于好心对手的去焦点化规划。与现有的可验证规划分歧 咱们的搜寻了局自然是是正确的、弗成改动的 并且没有须要数据一切者施行验证。其余 咱们运用智能合约组织了一个平正的隐私损坏搜寻规划 个中每一个到场方 稀奇是正在多用户境况下 都恐怕受到平正周旋 并且受到激发去做正确的算计。正在摹拟收集上的测验了局阐明了该规划的可行性。
收起 进展全文