英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
一种生成难以反转的负数据库的细粒度算法
摘要：负数据库(NDB)是一种新的隐私保护和信息隐藏技术。它通过存储互补集而不是原始数据来隐藏信息。为了保护隐藏的信息，NDBs应该是难以逆转的。在本文中，我们提出了K-hidden算法来生成难以反转的NDBs(称为K-hidden-NDBs)。K-hidden算法比现有的负数据库生成算法可以用一种更细粒度地方式进行控制。此外，在基于局部搜索策略的SAT求解器方面，我们正式证明了K-hidden-NDBs比典型p-hidden算法生成的NDBs更难以反转。此外，我们证明当NDBs的大小相同时，K-hidden-NDB(根据局部搜索策略)可以比q-hidden-NDB(由q-hidden算法生成的NDBs)更难以反转。最后，对于单元子句的启发式求解，我们证明了K-hidden-NDB可以和q-hidden-NDB一样难以逆转。
关键词：隐私保护；信息隐藏；负数据库；K-SAT
引言
近年来，数据安全和隐私问题受到广泛关注。受到生物免疫系统的负选择机制的启发，负数据库(NDB)首先由Esponda和他的同事首先提出[1，2]。负数据库(NDB)是一种新的隐私保护和信息隐藏技术。存储实际数据的传统数据库叫做正数据库(DB)。NDB存储原始数据补集而不是DB中的信息。因此DB中的信息被负数据库中大量的信息隐藏。此外，反转NDB已经被证明是NP-hand问题[1，3]。与传统的加密方案相比，负数据库的一个优势是支持一些数据库操作[4]和计算[5]。此外，负数据库能够被有效的产生和操作[2,4,6]。
目前，负数据库已经被应用于隐私保护[2，6]，信息隐藏[7]，认证系统[8]，敏感数据收集[9]，生物模版安全[10]，安全多方计算[5]，隐私保护数据挖掘[11]和隐私保护数据出版[12]。如果一个NDB能够在多项式时间内被逆转到隐藏的DB，就称之为易解的，否则成为难解的。在很多应用中，负数据库需要是难解的。简单来说，那些包含K个确定值的条目称为K-NDBs。目前为止，一些生成负数据库的算法已经被提出[2,6,13-15]。然而，这些算法中大多数不能用一种细粒度地方法控制生成NDBs的特征（例如：不同类型条目在负数据库中的分布），然而这在实际应用中非常重要。目前为止，仅仅q-hidden算法[6,17]被用于生成 的K-NDBs。在q-hidden算法中，不同类型条目的分布由唯一参数q控制。当时，q-hidden算法是p-hidden[14]算法的特例。
在本文中，我们提出K-hidden算法生成难以逆转的K-NBDs（简单称作K-hidden-NDBs）。K-hidden算法比q-hidden算法更加细粒度因为个参数被用来控制不同类型条目的在NDBs中的分布。这一优势表明在实际应用中K-hidden-NDBs的安全性和效用能够用一种更加细粒度地方式控制。总的来说，我们的贡献如下：
- 我们提出算法生成难以逆转的。当时，算法退化为p-hidden算法，但是p-hidden算法只能用于产生。当，q-hidden算法是K-hidden算法的特例。
- 我们分析了用局部搜索策略逆转K-hidden-NDB的难解性，并且证明K-hidden-NDBs能够比p-hidden-NDB(p-hidden算法生成的NDB)更加难以逆转。此外，我们的经验证明，当参数r固定(r决定NDBs的大小)时，K-hidden-NDB能够比q-hidden-NDB更难以反转(针对局部搜索策略)。
- 我们用单元句子（UC）启发分析了反转K-hidden-NDB的难解性，并且证明了K-hidden-NDB能够和q-hidden-NDB一样难解。
相关工作
为了隐私保护和信息隐藏[2，7]NDB被提出以负的形式存储和操作数据。通常，给定一般集合和一个当，NDB存储中的信息。如果一个NDB覆盖了U-NDB中所有的二进制串，则成为完备的，否则成为不完备的。由于通常有太多的二进制字符串需要显式地表示或存储在NDBs中，通配符“*”被用来压缩NDBs。符号“*”可以匹配0和1，被称为不确定值（0和1被称为确定值）。因此NDB中的每一项v都是由0，1和*组成的字符串。v的那些0或1的位置称为确定位，*的位置称为不确定位。在表Ⅰ中，和是可能的两个负数据库。使用“*”的另外一个好处是能够从同一个DB产生不同的NDBs。从[2,3]中可以看出每一个NDB对应一个SAT实例，并且从反转NDB恢复到DB是一个NP难问题。
目前为止，一些生成NDBs的算法已经被提出。通常，前缀算法是第一个生成NDBs[2]的算法，但是生成的NDB是容易反转的。然后RNDB算法被提出生成难以反转的NDBs[2]，但是它不能确定和控制生成的NDBs的不可逆性。前缀算法和RNDB算法生成的NDBs的条目具有不同数量的指定值。在[6]中，Esponda和他的同事应用了q-hidden算法[17]用于生成难解的K-SAT实例，去从一个串（称为隐藏串）生成难以反转的K-NDBs。q-hidden算法用一个参数q控制生成类型1hellip;K的条目（类型i的条目具有i个不同于隐藏串的指定值）。q-hidden算法非常高效，它能产生对于基于局部搜索策略的SAT求解器难以逆转的NDBs,例如WALKSAT[16]。在[13]中，刘然，罗文坚和岳丽华等将前缀算法与q-hidden算法结合使用，可以从单个字符串生成完整且难以反转的NDBs。然后，在[14]中他们提出了p-hidden算法从一个串生成难以逆转的3-NDBs。p-hidden算法使用两个参数p1和p2控制生成类型1,2,3条目的可能性，扩展了难以反转的NDBs的搜索范围。在[14]中，实验结果表明p-hidden算法能够生成比q-hidden算法更加难解的3-NDBs（针对WALKSAT）。
此外，在[20]中提出了实值负数据库和它的生成算法框架。
表Ⅰ. 负数据库的一个例子
|
DB |
U-DB |
|
|
|
000 |
001 |
1** |
10* |
|
010 |
*1* |
0*1 |
|
|
011 |
**1 |
1** |
|
|
100 |
|||
|
101 |
|||
|
110 |
|||
|
111 |
另一方面，一些生成SAT实例的算法已经被提出[17,19,21-23]。通常，0-hidden算法[17,19]生成随机子句（没有参数控制不同类型子句的分布）。0-hidden算法用于生成SAT实例来评估完整的SAT求解器[17,19]。然而，使用0-hidden算法[19]生成的SAT实例评估不完全SAT求解器非常困难。这是因为，当求解器没有发现任何解决方案，很难验证这些求解器是否失败或这些SAT实例是否无法满足。解决此问题的一种自然方法是通过只接受预定义解决方案满足的子句来隐藏预定义解决方案[17,19]。该算法称为1-hidden算法，在[21,22]中可以找到一些基于1-hidden算法的复杂模型。然而，已有研究表明，由1-hidden算法生成的SAT实例通常很容易被基于局部搜索策略的SAT求解器所求解[17,19]。在[23]中，提出了用子句分布控制方法生成难以满足的3-SAT实例，但仅用一个参数控制不同子句的比例。后来，2-hidden算法[19]被提出来生成难解并且满足SAT的实例。2-hidden算法不仅隐藏了预定义的解A，还隐藏了它的补集。然而，[17]中的研究表明2-hidden算法生成的SAT实例对于一些基于局部搜索策略的SAT求解器也可能是易解的。之后q-hidden算法被提出用于生成不仅对于基于局部搜索策略的求解器难解，而且对于基于单元句子启发[17]也难解的满足SAT的实例。注意，这些算法可以很容易地用于生成NDBs，因为每个SAT实例都可以转换为一个NDB[2,3]（0-hidden算法不能用于生成与预定义的非空DB对应的NDBs）。
K-hidden算法
- 动机
尽管一些负数据库生成算法已经被提出，它们中的大多数不能根据现实世界应用程序中可变的安全性和实用需求来任意控制或调整NDBs中不同类型条目的分布。p-hidden算法可以任意控制3-NDB中的分布，但当字符串长度固定时，其最大安全强度受到限制。通常，我们将一个算法的自由度(DoF)定义为控制NDBs中不同类型条目分布的独立参数。新NDB生成算法的自由度与生成具有不同安全性和实用性的NDBs的能力有关。有人认为当自由度越高时，算法对生成的NDBs的安全性和有效性控制越细。众所周知，算法或机制中的细粒度控制非常重要，为工程应用提供了灵活性和可靠性。在涉及系统或数据的安全性和私密性的应用程序中，对安全性和实用程序的细粒度控制还可以实现多样化和个性化的需求，从而增强用户体验。因此，我们提出了K-hidden算法，它可以使用Kminus;1个概率参数任意控制不同类型条目的分布，从而生成难以反转的K-NDBs。经典的NDB生成算法的自由度如表Ⅱ所示。数据显示K-hidden算法当的时候实现了最高的自由度，并且它的自由度是可以调整的。然而，在下面的章节中，我们将证明K-hidden算法在局部搜索策略上比p-hidden算法和q-hidden算法可以生成更多的难以反转的NDBs。我们也会讲到，对于单元句子启发，K-hidden-NDB能够和q-hidden算法生成的NDBs一样难以反转。K-hidden算法也可以用于生成用于评估SAT求解器难解的SAT实例，这些SAT实例的求解难度与K-hidden-NDBs的难度相当。
- K-hidden算法
在本小节中，我们将介绍K-hidden算法，用于从字符串生成难以反转的K-NDBs。算法1给出了K-hidden算法的细节。
一个m比特的字符串s时将被K-hidden算法隐藏的数据，它作为一个输入参数。另一个输入参数r用于控制由K-hidden算法生成的NDBs中的条目数量。参数用来控制生成K类条目的概率，从而控制K类条目的分布。这K种类型的条目定义如下。
- 所有类型的项都有K个指定的位。
- 类型的条目有i个值不同于隐藏串s的确定位。
在K-hidden算法中，NDBs首先被初始化为空集。在步骤2中将NDBs中的期望项数N设为。然后在步骤4-9中创建N个条目并迭代地添加到NDBs中。在每次迭代中，首先生成一个区间内的随机值rnd。然后，步骤6-7找到比rnd大的最小，并生成类型i条目v。显然，类型i条目是在每次迭代时以概率pi生成的。最后，包含项的NDBs作为输出返回。
不难看出，q-hidden算法和p-hidden算法都能看成K-hidden算法的特例。当K=3时，K-hidden算法退化为p-hidden算法。当，K-hidden算法退化为q-hidden算法。
表Ⅱ 一些NDB生成算法的自由度
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[235330]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
|
算法 |
自由度 |
|
1-hidden算法[17,19,21,22] |
0 |
|
2-hidden算法[19] |
0 |
|
q-hidden算法[17] |
1 |
|
p-hidden算法[14] |
2 |
|
前缀算法[2] |
0 |
|
RNDB算法[2] |
0 |
|
算法 |
|
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
