英语原文共 25 页，剩余内容已隐藏，支付完成后下载完整资料
低复杂度安全纠错窃听编码
Yuval Cassuto
School of Computer and Communication Sciences
ALGO
EPFL, Lausanne
Switzerland
Email: yuval.cassuto@epfl.ch
Zvonimir Bandic
Hitachi Global Storage Technologies
San Jose Research Center
3403 Yerba Buena Road
San Jose, CA 95135, U.S.A.
Email: zvonimir.bandic@hitachigst.com
摘要——本文提出了用于保证安全与纠错性能的新的编码机制。在无差错的主信道的情况下，构建了保证安全的具有最佳的编码复杂度的两类编码。在有错误的主信道情况下，研究了安全码和纠错码的两类串联结构。对于每一个串联结构的方案，能给出在窃听性能和纠错性能之间中最佳的串联编码结构。研究低复杂度安全纠错窃听编码的动机来自于数据存储的应用。由于不完善的物理擦除过程，重要的机密信息需要受到保护使其不会被窃听者从快速擦除中残留的部分信息里获得有用信息，同时也要防止合法用户在读取信息的过程中获得错误的信息。
第一节、介绍
信息安全最基础的根源是信息理论。香农的基本定理[5]实现了无条件的秘密通信的功能并且为其划定了界限。无条件保密性，在此之后被称为信息理论保密性，作为在信息安全等领域正在欣欣向荣地发展的安全性通讯的边界标志。但尽管如此，每当涉及到实际情况对系统安全性造成影响时，信息理论的贡献度仍次于计算机科学理论中对安全性的理论计算。
在本文中，我们进行信息安全性理论中一个分支的研究，它能够准确快速地应用于系统安全性。它解决的是在存储设备中机密数据物理擦除不完全的问题。无论特定的存储介质或技术，用于擦除数据的物理过程本身上就是不完全的。确保完全擦除所有的信息是不可能的，或者说需要很高的附带成本(例如，[7]中重复多次擦除的时间成本)。一个不完全消除过程的含义是，窃听者通过访问擦除后的存储设备能够提取到秘密信息并且危害到系统的安全性。本文的出发点是对于可以被看作是窃听信道[9]的不完全擦除问题的简单观测。在这种情况下，窃听信道是一个物理擦除过程，该过程是引入了对窃听者所观察到存储信息进行错误和抹除干扰。主信道是普通的存储信道通常可能会携带一些由于不完全的读写过程所造成的错误，而合法用户是凭借主信道是普通的存储信道这个条件在一个擦除操作之前读取存储的信息。窃听问题的设计目标是对信息进行编码使得它可以在主信道被合法完全地重组接收，同时不透露任何信息给窃听信道。Ozarow 和 Wyner[4]的第二代窃听信道就是为了解决窃听编码设计问题而开发的结构。二代的窃听信道可以被视为对应于信息理论中窃听信道的编码理论。在这个框架中，是在最坏的情况下考虑保证信息的安全性并且由窃听编码来提供具体的安全保障。鉴于实际安全实现的保守性质，在最坏情况下的安全保障是对于不完全擦除问题的最优解决方案。把两类编码保证安全性的能力作为他们的指标参数，允许系统设计师根据特定系统的属性和限制选择合适的安全编码方式。
近期的论文在两个方向上对二代窃听编码进行研究。首先，它试图构建具有尽可能低的编译码复杂性的窃听编码。其次，它提供了在有错误的信道条件下具有保证安全纠错功能的最佳结构。在此之前考虑到的有错误的主信道不能提供保证安全与纠错的功能[6]，或要求对偶互补的窃听信道编码[1]的情况。选择编码和解码的复杂性——而不是代码冗余——当做编码最优化主要标准的动机来至于在一个典型的只使用一小部分存储容量来存储秘密信息(例如加密密钥)的存储设备，同时这个秘密信息的读取和写入需要快速、频繁地执行。在第二部分中引入了由二代窃听框架扩展而来的结构之后，本文可分为两个部分。第1部分致力于在无错误的主信道情况下，在第三节提出了两种具有最优的编码和解码的复杂性类型的编码方式。考虑到窃听的安全参数，据说一个编码方式如果它的奇偶校验矩阵的密度是最低的可能性，则这个编码方式有最佳的编码和解码的复杂性。在第2部分中，我们将讨论在主信道有错误的情况下的编码结构，研究两种窃听编码和纠错编码的串联类型:外部纠错编码和内部窃听编码在第四节给出，内部的纠错编码和外部窃听编码在第五节给出。前者中，我们基于窃听编码提出一个具有最低退化可能的纠错性能的编码结构。在后者，我们提出一个在内部纠错编码前保留了外部编码的窃听安全性的编码构造。在第1部分中的这两种结构是第2部分中实现良好性能的必不可少的组成模块。
第二节、二代窃听信道
二代窃听信道构建在Wyner最初对窃听信道的构想基础[9]之上，是由Ozarow 和 Wyner在1984年提出的[4]，它专注于在最坏的条件下的编码安全性能。最坏的情况分析意味着对于任何有限的子集的码字位置在被窃听者所获取的情况下，编码方案是安全的。在本节中，我们简要地回顾[4]的定义和实施方案。这里使用的符号是对原始符号的改良。
- 问题陈述和模型定义
让作为秘密数据的数量符号。我们的目的是将个数据符号编码成个编码符号，这样一来窃听者就无法从他所选择的大小为符号子集中所观察到的信息里获得有关秘密数据的信息。
B.实施方法
对于无错误主信道的情况，总结了在[4]中提出的编码方案。在前面的小节中定义的参数，，。一个线性窃听码由一个每个子矩阵秩为的奇偶校验矩阵组成的系统性奇偶校验矩阵构成。给定一个符合上述性质的编码方式，所使用的编码系统是如下。
编码：随机地绘制个符号来从中编码一个随机的，长度为，码字为的码。个信息符号放置在一个行向量中。然后编码向量可以简单看做（其中0的个数为）：
（1）
另一种考虑编码函数方法是，从陪集中选择一个随机的元素对应于秘密信息向量。
解码：考虑到长度为的向量，合法用户计算来恢复秘密数据向量，其中表示一般的向量和矩阵转换运算符（其中0的个数为）。
窃听：给出任何mu;已知符号的编码向量，窃听者必须要解出这个线性系统的形式:
（）
（2）
窃听者的目标是当已知的情况下（通过计算已知的各符号得到）找到，并且向量未知。如果设计任意一组坐标系对应一个秩为的子矩阵，则对于任意一个向量这个线性系统都有一个解决方案（向量的形式为）。因此，依据已知的一部分，在[4]中有提到，窃听者从获得秘密数据中的无价值信息。请注意，如果子矩阵秩小于，然后某些不会有相应的的解的方式，并且窃听者可以排除出潜在的秘密价值，从而危及信息的安全。
一个简单的构建方式示例是使用奇偶校验代码获得并且的窃听编码。详情请参阅[4]。
上面描述的方法是本文的第1部分包括二代无错误窃听方法的编码结构。然后在第2部分的代码结构解决有错误的主信道的情况。
第1部分:无差错的主信道
第三节、最理想复杂程度的窃听编码
如在第二部分中所述，针对从窃听者已经接触到任何个编码符号额情况下最好的窃听安全性，编码的奇偶校验矩阵被要求具有所有的秩为的子矩阵。这个编码的性质等价于被要求最小汉明距离至少为mu; 1[8]的双重编码的要求。为了说服自己相信上一个事实，观察到如果(且仅当)代码具有最小汉明距离为，或者更小，那么存在一个矩阵秩小于的生成矩阵的子矩阵(这样一个的非零码字有对应这个子矩阵所有的个零坐标)。从此找到好的窃听编码的问题被简化为编码理论中最具计划性的问题:寻找具有高维度和极小汉明距离的线性分组码。然而，当窃听编码中编码和解码的复杂性被考虑进来，具有极小汉明距离的传统编码方式可能次于尽可能完美的窃听编码。在提出现行的低复杂度编码之前，我们讨论一般性的编码和解码的复杂性。
- 编码和解码的复杂性
如果秘密信息将要被编入码字中，并且从高速率通道中恢复出来，则必须将注意力放在窃听编码的编码和解码的复杂性上。与基于有噪信道的编码不同在于，窃听编码的解码操作是一个简单的线性码计算而不需要在收到的陪集中找到陪集首。因此窃听编码的编码和解码的复杂性分别直接与编码器和奇偶校验矩阵密度相关。回想一下，在小节II-B中是需要有一个允许简单编译器方程(1)的系统性奇偶校验矩阵算法表示。当在系统形式中被给出时，编码和解码的复杂性都可以从的密度来确定。每一个信息符号的编码和解码复杂性都被引证，因此一般用行平均密度来度量适当的矩阵密度，在下面给出定义。
定义1：矩阵的(行)密度是非零元素的数量除以它的行数。对于一个给定的窃听安全参数，最小化系统性的奇偶校验矩阵的密度因此最小化窃听方案中码字的编码和解码复杂性。
结构1：设为1到k 1（包含）之间整数的集合，并设有为从A得到一组的无序组合，并有。让为列间距与的元素相对应矩阵；在指定的位置，每列刚好有两个由一对给定列定义的i，j（另一个k-1元素为零）。窃听编码的奇偶校验矩阵是从通过擦除任何单个行而获得。
定理1：结构1中的编码方式是一个的二进制窃听编码。
证明：矩阵中的每一行都有k个二进制符号。假设存在一个秩小于的子矩阵。由于是系统化的，任何一组的列至少有一列在行具有一个单独的元素。的列数有一个元素在行上，其他的元素在剩下的个行中为。如果我们从所选的子矩阵中删除行，则必有一个只含有单独元素的列。然后通过归纳法我们可以继续排除和删除行，直到没有更多的行因相应的组合而留下。
由结构1给出的矩阵每行中有k个元素。因此的密度为k。恰好k是中只有单一元素列的个数，因此在系统的形式中能被给出。考虑到的窃听安全，其次结构1被发现有最佳的密度(i.e.有micro;给出的最低可能密度)，并且因此同时具有最优译码和最优编码的复杂性。
命题1：任何一个具有奇偶校验矩阵的的窃听编码方式的密度至少为。
证明：如果矩阵的密度远远小于，然后在矩阵中存在一个具有个或更少的非零元素的行。因此，如果我们挑选关于矩阵的行上的元素全为零的的子矩阵，这个矩阵的秩明显要小于，这与窃听用的要求相悖。
注解：一阶Reed-Muller规范[2,Ch.13]在他们的窃听安全性中也享有最优密度，但在他们的码字尺寸上长度是指数性的，这使它们在同等介数中，码字长度为的情况下只适应现实情况下较少的情况。
例1：当时，我们有，并且有
则可得出矩阵为：
在擦除第一行后等到：
（3）
矩阵在公式（3）中定义了一个的窃听码，码的密度为4。
为了更好的窃听安全性具有略高的（最优的）密度，我们加入了以下的结构。
结构2：设为从1到（包含）之间所有整数的集合，并且设为从集合中得到的无序的三元组合的集合，并且。设为对应中的元素的的矩阵：每一列都恰好有三个元素，由给出的三行确定（其他的列都的元素是零）。窃听编码的奇偶校验矩阵是通过矩阵删除任意两行得到的。
定理2：当时，从结构2中得到的编码是一个二进制的窃听编码。
证明：这个证明将展示当时，奇偶校验矩阵中行的任意线性组合能够得到一个汉明重量至少为的矢量，也是奇偶校验矩阵中个别行的重量。下一个引理表示行的线性组合重量是线性组合中行和的一个函数。
引理1：设为奇偶校验矩阵中行的线性组合，并且。则的汉明重量通过以下公式给出：
（4）
奇偶校验矩阵中行的线性组合重量只取决于，为组合中行的个数，是由上面的函数给出的。
证明：向量的位元是二进制，假设由奇偶校验矩阵中行得到，在列中含有一个或三个二进制符号。在一组已经由行给定的仅有唯一一个二进制符号的列的数量相当于（4）中的往左被加项。
在上面的引理中给出的行排
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[150094]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
