基于难以逆转的负数据库的隐私保护
作者：Fernando Esponda 、Elena S. Ackley、 Paul Helman ·Haixia Jia 、Stephanie Forrest
上传时间：2007年7月24日
出版社：施普林格出版公司 2007
摘要：一个关于数据元素的数据集（DB）可以用它的补集来表示，称为负数据库（NDB）。也就是不在数据库的元素被表达，而数据库本身的内容没有被显示存储。这种表示数据的方法有着一定的增强相关应用隐私的属性。本论文将简要的回顾负数据库存储一个负影像的表示方法，并且提出用一个负数据库集去表示一个单独的数据库，即为数据库的每一个记录都分配一个负数据库。这种方法在建立实践中难以逆转的负数据库上有着优势，很难从此当中还原原始数据库。这种结果是通过改进一种产生难以处理的3-SAT公式的技术获得的，最后我们建议使用潜在的应用途径。
关键字：负数据库 布尔可满足性 k-SAT 隐私 保护
符号列表:
s，y，v：二进制字符串
l：字符串中的位置数
DB：一组二进制字符串，称为正数据库
NDB：一组使用{0，1，*}组成的字符串的集合，被称为负数据库
NDB(s)：字符串s的负数据库。
NDBA：属于代理A的负数据库
Y：表示字符串中比特位位置的串
m：负数据库中的记录数量
r：负数据库中记录与字符串长度的比
k：字符串中确定位置的数量（非“*”符号）
c：附加到字符串的位数， 代码长度
1、简介。
控制信息的访问并且限制可以逆推导的推导类型获得的关注持续增加，对数据有效性的需求和对机密性的标准在持续进化，使保护敏感数据的任务复杂化。当前的加密术（对保护数据本身）和查询限制（对控制对数据的访问）帮助了机密性的确保，但是没有对所有应用都合适的解决方法。在加密的情况下，查找数据的能力被限制；在查询限制的情况下，单个记录容易受到内部攻击他们的安全可能被追踪攻击连累（见参考文献[16,17]）。进一步来讲，现有的方法依赖于单个假设的集合。举例来说，基本的因式分解就介绍了一个单点失败应该违反的假设。
在本文中，我们描述了一种可以处理一部分这些担忧并且提供一个新的起点给设计新应用的方法。做了一个涉及到外部实体可能需要查阅的包含个人纪录的数据库的激励性设想，举个例子，验证一个进入者在监视名单中。有一个可以支持查询类型限制、禁止任意的检查（即使是从内部）并且可以不向观察者泄露原始数据的变动的数据库是理想的。
图1、DB的不同示例，其对应的U -DB，以及可能的NDB代表U –DB
在我们的方法中，一个基本元素数据集的负影像被表达而不是这些元素本身（见图一）。首先我们假定一个有着确定长度串（或者记录）的全集U，所有串的长度是一样的，并且是都用二进制定义的。我们逻辑的将包含了二进制串所有可能的全集分为两个不相交的集合：数据库（DB）代表着正记录的集合（拥有人们感兴趣的信息）；U-DB表示着不在DB中的所有串的集合。我们假设所有DB中的数据为被压缩（每个记录都被清楚地达），但是我们允许U-DB以一种叫NDB的形式被压缩存储。我们称DB为正数据库，NDB为负数据库。从逻辑的角度看，两者任何一个都足以解答关于数据库的问题。然而，他们有着不同的优势。例如，在一个正数据库中，单个串的查询会提供有意义的信息；而单个“负”的串对于原始数据库的内容泄露的很少。考虑到正元组从来不会显示的存储，一个负数据库可以变得更加难以滥用。尤其是负数据库方法被推荐于通过隐瞒其大小和限制使用能被高效的回答的查询类型保护数据集隐私。此外，这种方法支持数据集的更新，并且允许选择它项目的子集，使负数据库在没有明确它包含的知识内容的情况下有意义的进行操作。
引用的文献[19，20]介绍了负数据库，并且理论基础已经建立在表达的某一性能上，尤其是在隐私和安全的层面上。本论文着重处理涉及负数据库安全和高效的更新负数据库的一些实际问题。我们将介绍一种新的可以更好地支持数据更新操作的存储方法，并且我们从其它的领域借鉴技术以创建实际中更加安全的负数据库。
接下来的部分回顾了负数据库的表示，提供了几个例子，并且如何去查询它。第三部分研究了关于保护隐私和安全的方法的影响，尤其是发现从负数据库逆转正数据库是NP难的问题[19,22,23]。然后我们提供了一种在实际中建立难以逆转的负数据库的方法，这种方法克服了之前方法更新不高效的问题。在第四部分，我们描述了一种强调性能的方案和对展望在应用领域的建议。最后，我们回顾了相关工作，讨论了结论的潜在影响以及概述了未来将研究的领域。
2、负数据库的表达。
为了创建一个大小合理的负数据库（NDB），我们必须在保留应答查询的能力的基础上压缩U-DB里面的内容。我们引进了一个额外的字符到二进制字符，叫做通配符，记为“*”。
在NDB的记录为长度L使用字符{0，1，*}的串。通配符有着一贯来的解释，在字符”*”出现的地方既可以表示0也可以表示1。串里被置为0或1的地方被称为“确定位”。这个符号使U-DB里面的庞大子集仅仅被NDB里的几条目录所代替（见图一）。
一个串s被赋给数据库当且仅当s与在NDB的所有记录都不匹配。这个条件仅在每个串yisin; NDB且s与y中至少一个确定位不一致时才完全被满足。
查询语句也用相同的字符被表达为串；一个串，Q，完全由连续的确定位组成----即完全由0和1组成----，被解释为“Q在DB中么？”，并且当我们提及它时把它当做一个简单的关系或者验证查询。回应这种查询需要检查在NDB中的匹配，就像上面描述的，可以在与|NDB|长度成正比的时间内完成。在引用文献[22]中的工作证明了布尔满足公式（SAT公式）和NDBs之间的一个高效的映射方式（见图二）。并且它表明NDB的逆转----即它的正影像----是NP难的，取决于DB是否是空的或者完全NP的。因此，回应一个复杂的含有不确定位“*”的查询是很棘手的。
图二、将SAT公式映射到NDB中：在这个例子中布尔公式被写做和取范式（CNF），并且定义了五个变量{x1,x2,x3,x4,x5}。当每个子句与一条负记录一致时这个公式能映射到NDB中，并且字句中的每个变量在否定时表现为“1”，不否定时为“0”，当某个变量不出现时表示为“*”。
可以很容易看出公式间的布尔满足，例如当{x1=false,x2=true,x3=true,x4=false,x5=false}时，与串“01100”是一致的，“01100”并没有表达在负数据库中，因此它是DB中的数据。
假设一个形式为{name，address，profession}的元组作为例子。“在DB中，lt;Tintan，69 Pine Street，Plumbergt;”（写成二进制字符串Q）很容易回答，同时检索DB中所有工程师的姓名和地址（表示为专业领域的查询字符串设置为“工程师”的二进制编码，其余位置为*）通常是难以处理的。然而不是所有的NDBs都有我们寻求的硬度性能。举个例子，构建一个具有具体结构可以使复杂查询高效回应的NDBs是可行的（查阅文献[19,22]）。事实上，在实践中构建一个难以逆转的负数据库是十分困难的。下一部分将处理这个问题并且提供一种创建只支持高效验证查询的负数据库的算法。
3、难以逆转的负数据库。
在引用文献[19,20,22,23]中给出的几个算法都被证明是容易逆转的，也就是说，总能找到一个高效的算法来还原DB，或者说创建一个难以逆转的实例是有弹性的但是还没有在试验中生成出它们。在文献[22]中表明逆转一个负数据库是一个NP难的问题，但是这是最坏的情况，提出了在实践中建立一个难以逆转的实例的挑战。
这一部分着重于创建一个在实际中难以逆转的负数据库。为了创建一个在实际中难以逆转的负数据库，我们依赖于负数据库和布尔满足公式（SAT公式）之间的关系（见图二），同时利用文献[2,33,34,47]中致力于创建困难的SAT公式实例的所做工作主体的优势。我们做中使用文献[33]中介绍的一个模型作为一个实例并且使用它作为创建负数据库的基础。它和文献[19,20,22,23]中描述的算法的区别主要在两个方面：首先，它为数据库DB的每一个串生成一个负数据库ndb；其次，它创造了一个不严格的U-DB的表示，意味着一些在DB之外的串不会被NDB匹配。
接下来的子部分描述了生成算法，概括了如何处理额外的串产生的问题，以及从经验上验证得到的数据库时难以逆转的。
3.1、使用SAT公式作为负数据库的模型。
在文献[33]中给出了一个创建SAT公式的算法，这是一个负数据库构造的基础。这个算法的目的就是为了创建一个所谓的可以被满足的公式，但是任何SAT求解器都不能其求解。在我们的构造中，我们会使用一个SAT公式去表示正数据库手中的每一条记录。这种方法开始于一个分配串（一个表示公式中变量的真值的二进制串），然后创造一个被它满足的公式----很像文献[19,20,22,23]中的算法，除了得到的公式也可能被其它分配串满足。通过这个分配串，这个算法随机生成文字tgt;0的子句以使每个子句被等比q^t的可能性满足，其中qlt;1（q是算法的一个实际参数，被用来使公式内子句的分配偏离）。这个方法的目的是为了平衡子句的分配以使公式和其它的公式达到统计无差别。这个工作会生成一个子句的集合，每个都被分配串s满足，这些子句可以容易的转换进负数据库。（见图二）
首先，我们使一个数据库（DB）的大小最最大为一（在3.4部分扩展了这个例子，使数据库不止一个记录），包含一个长度为L的二进制串s。我们通过以下步骤创建一个负数据库：
1、每条负数据库的记录都有正好三个指定的比特。
2、s不被负数据库的任何记录所匹配。
3、考虑到任何一个长度为L的串都很容易验证是否属于负数据库（通过时间与NDB的长度成正比）。
4、NDB的大小和s的长度呈线性关系。协调参数r=m/l决定着数据库的大小和它的逆转难度----l是串s的大小以及m是NDB里面记录的数目。
5、NDB的大小不取决于DB的内容，举个例子，当|DB|=1和|DB|=0时它有着同样的大小。
6、s“几乎”是“仅有的”和NDB不匹配的串，也就是说，s是几乎是仅有的被包含在NDB的正影像DBrsquo;里面的串。其它DBrsquo;里面的串与串s基于汉明距离是接近的（见3.2部分）。
7、负数据库NDB是难以逆转的，意味着没有已知的搜索算法可以在合理的时间量里找到串s（假设s的长度大于1000，如下所示）。
步骤1-5是根据3-SAT公式（见图2）生成的负数据库同构体和算法的特点确定的。第六点在接下来的部分进行叙述，并且完善负数据库的生成方案。第七点在3.3部分根据经验确定。
3.1.1、 算法
现在我们来详细叙述本论文生成负数据库的核心算法。该算法最初是在文献[33]中背景介绍作为一种生成布尔可满足性（SAT）公式的方法并且为了方便在图2中再现。图四描述了一个生成一个可以表示所有等长（空DB对应的NDB）的串的负数据的算法，是基于一个众所周知的用于创造不可满足的公式的方法。它和图三的算法相似，只是为了清除起见单独列出。SAT公式和负数据库的联系在在图2中被阐述，是所有这些算法的基础。
图3、生成难以逆转的负数据库的算法。 伪码解释了在文献[33]稍作修改的算法。 输入变量l表示全集域中的字符串长度; k为每个负记录的指定位数; q表示负记录中的每一位与s的相应位不一致的概率; r为期望的负记录到字符串长度密度（r决定输出NDB的大小）
图4生成表示空正数据库的难以逆转的负数据库的算法。 输入变量的含义与图3中的相同。
算法（图3）通过随机生成与正数据库字符串s不匹配的负数据库记录来进行处理 -- 请注意，对于任何特定的s都有很多可能的NDB表示，其中一个由算法概率性地选择。 每个负记录具有确切的k个指定位，其余位置设置为无关符号。
步骤2在当前记录中统一随机地确定哪些比特位置需要详细说明，然后步骤3当s在选定位置时将其初始化为相同的值。步骤4-7根据一个随机进程设置负记录的最终值 -- 注意步骤7需要确保没有负记录与s匹配。
在步骤6中，q用于概率性地确定将用于创建每条记录的k值; 恰当地选择q（q lt;1）重新平衡每个比特位置处的值的分布，使得它不清楚地表示s的值--概率q=0.5，由文献[33]建议使用，被本文使用。q（负数记录中的某一位与s中相应位不匹配的概率）和r（NDB中的字符串数与字符串长度的比率）之间的相互作用决定了NDB难以逆转的难度，以及多少额外的字符串将会被NDB无法匹配（参见3.2部分）。步骤8包括在负数据库中的结果记录。 尽管创建重复记录的机会很小，但必须考虑这些记录才能实现n个唯一条目; 为简单起见，我们忽略了这一规定。
增加r的值可减少多余的解决方案（参见3.2部分），并且如步骤0所示，这增加了NDB必须具有的负记录的数量。 由于输入字符串的长度也会影响数据库的大小，因此随着输入长度的增加，r的值会有变化。 我们使用了值为5.5的r，因为难以接近这个值（参考文献[33]）。 为了我们达到目前实验的目的，我们使用值为3的k值，然而，使用增加的k值可能没有用处，因为注意到r的值可能以某种方式随着k而变化。生成数据库的大小和逆转k值
全文共23657字，剩余内容已隐藏，支付完成后下载完整资料
英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[13708]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
