在通信網絡中，當我們要傳輸私密信息時，可能有一些非法用戶希望能獲取這些私密信息。在這裡，我們分別稱這個網絡模型模型和非法用戶為竊聽網絡和竊聽者。在本文中，我們希望在某些限制條件下，設計一種編碼來抵抗竊聽者。 / 為了保護私密信息，我們不會在網絡中直接傳遞它，而是傳遞一些加密過的信息，即密文。現在通行的一個方法是:用一些隨機生成的密碼給這些私密信息加密。即使竊聽者能獲取我傳遞的密文，也無法知道確切的私密信息。在本中文，我們考慮了兩種安全級別:完美安全和非完美安全。在完美安全中，密文和私密信息從統計上講是完全獨立的，也就是說竊聽者得到的是一些安全隨機的信息。在非完美安全中，竊聽者被允許獲得一部私密信息。這部分私密信息，是由竊聽者的信息模糊度來衡量的。如果信息模糊度的大小等於私密信息，那麼非完美安全等價於完美安全。 / 本文的重點在於如何以最小的代價保護私密的信息。我們用Ç =(V ， Σ) 來表示通信網絡。其中， ν是所有節點的集合，Σ 是所有信道的集合。一個竊聽者能夠監聽某些信道上的信息。在我們的模型中，每個竊聽者竊聽的信道的集合是固定的。所有這些被竊聽的信道構成了一個竊聽集。我們把所有竊聽集的集合記作A 。 / 在竊聽網絡中，如果考慮完美安全，現有的工作表明，當A是由所有大小為r 的 Σ的子集構成的時候，存在一個線性網絡編碼，在下面兩個標準下是最優的: / 1)私 密信息的長度最大化; / 2) 隨即密鑰的長度最小化。但是，當A 由任意的5 的子集構成的時候，關於性能界的結果很少。 / 在本文的第一部分中，我們著手研究這個方面的問題並得到了以下結論: / 1) 對於私密信息的長度，我們獲得了一個上界並提供了一個多項式算法去計算它。 / 2)對於隨機密鑰的長度，我們從分教覆蓋和分數包裝的為度進行分析，分別獲得了兩個下界。這兩個下界， 我們證明了他們之間存在一個對偶性。接下來，我們討論暸如何去計算這個下界，我們設計了一個暴力算法和一個關於 / 接下來，我們更關注於點對點系統中的非完美安全問題。我們推廣了一個經典的安全模型: II型竊聽信道。在經典的II型竊聽信道模型中，私密信息是通過若干端到端的信道發送的。在這個模型中，假設每個竊聽者只能竊聽A 中的一個竊聽集，其中A是由所有大小為r的信道集構成。在這裡，保護私密信息的策略也和竊聽網絡中一樣。更確切的，我們可以找到一個關於隨機密碼長度的下界，而且這個下界可以通過一個群編碼獲得。我們在推廣中假設A的構成是任意的，每個竊聽者被允許獲得一定的私密信息。在這個模型下，我們定義了關於私密信息，隨機密碼，每個竊聽者的信息模糊度的一個元組。關於這個元組，我們獲得了一個緊的區域。這個區域可以看成是竊聽網絡上關於割集的一個界。 / In a communication network on which a secure message is transmitted, there may exist illegal users who want to obtain information about the message. Here we refer to the network and those illegal users as the wiretap network and wiretappers, respectively. In secure network coding, we aim to find a network code which can protect the message against the wiretappers under certain constraints. / To protect the message we transmit a ciphertext which is a mixture of the message and a private random key, through the channels in the network. In this work, we consider two kinds of security levels: perfect security and imperfect security. In perfect security, the cipher-text is statistically independent of the message, i.e., the wiretapper can obtain only some randomly generated messages. While in imperfect security, the wiretapper can obtain partial information about the message which is measured by the wiretapper's equivocation. If the wiretapper's equivocation is equal to the message size, then the imperfect security reduces to perfect security. / The focus of our work is to protect the message at the minimum cost, which is measured by the size the key and the bandwidth of the network. Here we denote the network by Ç = (V; Σ), where V is the set of nodes and Σ is the set of point-to-point channels in the network. A wiretapper may access the information transmitted on a certain subset of Σ. In our model, it is assumed that the wiretapper can access any one but not more than one set of channels, called a wiretap set, out of a collection A of all possible wiretap sets. / In a wiretap network, if perfect security is required, existing works show that when A consists of all the r -subsets of Σ (i.e. subsets of size r), there exists a linear network code, which is optimal according to the following two criteria: / i) the size of the message is maximum; / ii) the size of random key is minimum. / But when A consists of arbitrary subsets of Σ, very little is known about the fundamental performance limit. / In the first part of our work, we investigate this problem and obtain some results on the above fundamental performance limits. In this work, we adopt the convention that the size of a random variable X is measured by its entropy H(X). / 1) For the size of the message, we derive an upper bound on H(M) and provide a polynomial algorithm to compute it. / 2) For the size of the key, we analyze it from the aspects of fractional covering and fractional packing, respectively, by which we obtain two bounds on H(K) and we prove the duality between them. n520 Then we discuss the algorithms to compute the lower bound, in- cluding a brute force algorithm and a polynomial algorithm in terms of / In the remaining part, we are largely concerned with imperfect security in a point-to-point communication system, where a classical security model referred to as the wire-tap channel II is generalized by introducing imperfect security. In wire-tap channel II, information is sent to the receiver through a set of point-to-point channels. It is assumed that the wiretapper can access any one but not more than one set in A which consists of all the subsets of the channel set with size r. The strategy to protect the private message is the same as that in the wiretap network. Specifically, a lower bound on the size of the key which can be attained by a group code was proved. In our extension, A is arbitrary and from each wiretap set in A, the wiretapper can obtain some partial information about the message. Under these settings, we define an achievable rate tuple in terms of the message, the key and the wiretapper's equivocation, and prove a tight rate region of the rate tuples. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Cheng, Fan. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 103-108). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Abstract --- p.ii / Acknowledgement --- p.ix / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Network Coding --- p.2 / Chapter 1.2 --- Secure Network Coding --- p.3 / Chapter 1.2.1 --- Perfect Secrecy System --- p.3 / Chapter 1.2.2 --- Imperfect Secrecy System --- p.8 / Chapter 1.3 --- Thesis Organization --- p.10 / Chapter 2 --- Basic Concepts and Tools --- p.13 / Chapter 2.1 --- Basic Concepts in Information Theory --- p.14 / Chapter 2.1.1 --- A Universal Approach for Bounds --- p.17 / Chapter 2.2 --- Information Inequalities for Joint Entropy --- p.18 / Chapter 2.2.1 --- Han's Inequalities --- p.18 / Chapter 2.2.2 --- Madiman-Tetali's Inequalities --- p.19 / Chapter 3 --- Performance Bounds on a Wiretap Network --- p.23 / Chapter 3.1 --- Problem Formulation --- p.24 / Chapter 3.1.1 --- Admissible Code --- p.25 / Chapter 3.1.2 --- Performance Measures of an Admissible Code . --- p.27 / Chapter 3.2 --- Related Works and Our Contribution --- p.27 / Chapter 3.3 --- Blocking Sets and Wiretap Sets --- p.29 / Chapter 3.4 --- An Upper Bound on the Message Size --- p.32 / Chapter 3.5 --- The Fractional Packing Bound --- p.34 / Chapter 3.6 --- An Alternative Bound --- p.37 / Chapter 3.7 --- A Duality Result --- p.38 / Chapter 3.8 --- Some Properties about the Lower Bound --- p.42 / Chapter 3.9 --- Algorithms for Computing the Lower Bound --- p.44 / Chapter 3.9.1 --- A Brute Force Algorithm --- p.44 / Chapter 3.9.2 --- A Polynomial Algorithm --- p.45 / Chapter 3.10 --- Tightness of the Lower Bound --- p.50 / Chapter 3.10.1 --- When the Best Lower bound is Zero --- p.52 / Chapter 3.10.2 --- Point-to-Point Communication System --- p.52 / Chapter 4 --- Imperfect Secrecy in Wire-tap Channel II --- p.63 / Chapter 4.1 --- Problem Formulation and Related Result --- p.64 / Chapter 4.1.1 --- Problem Formulation --- p.64 / Chapter 4.1.2 --- Related Result --- p.67 / Chapter 4.2 --- Rate Region of the Rate Tuple --- p.70 / Chapter 4.3 --- A Subregion of the Rate Region --- p.71 / Chapter 4.3.1 --- Converse --- p.72 / Chapter 4.3.2 --- Achievability --- p.76 / Chapter 4.4 --- General Rate Region --- p.85 / Chapter 4.4.1 --- Converse --- p.86 / Chapter 4.4.2 --- Achievability --- p.88 / Chapter 5 --- Conclusion --- p.91 / Chapter A --- Some Related Results --- p.97 / Chapter A.1 --- Definitions and Theorems in Linear Programming --- p.98 / Chapter A.2 --- An Equivalent Lower Bound --- p.101 / Bibliography --- p.103
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_328195 |
| Date | January 2012 |
| Contributors | Cheng, Fan, Chinese University of Hong Kong Graduate School. Division of Information Engineering. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography |
| Format | electronic resource, electronic resource, remote, 1 online resource (xiii, 108 leaves) |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0025 seconds