Adaptive Codes for Physical-Layer Security

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Adaptive Codes for Physical-Layer Security João Paulo Patriarca de Almeida Programa Doutoral em Telecomunicações Orientador: Doutor João Francisco Cordeiro de Oliveira Barros, Professor Associado com Agregação do Departamento de Engenharia Eletrotécnica e de Computadores da Faculdade de Engenharia da Universidade do Porto 24 de Julho de 2014 c João Paulo Patriarca de Almeida, 2014 Adaptive Codes for Physical-Layer Security João Paulo Patriarca de Almeida Programa Doutoral em Telecomunicações Aprovado em provas públicas pelo Júri: Presidente: Doutor José Alfredo Ribeiro da Silva Matos, Professor Catedrático da Faculdade de Engenharia da Universidade do Porto Arguente: Doutor Matthieu Bloch, Assistant Professor, School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, USA Vogal: Doutor Mikael Skoglund, Associate Professor, School of Electrical Engineering, KTH Royal Institute of Technology, Stockholm, Sweden; Vogal: Doutor Adriano Jorge Cardoso Moreira, Professor Associado do Departamento de Sistemas de Informação da Universidade do Minho; Vogal: Doutor Jaime dos Santos Cardoso, Professor Associado com Agregação do Departamento de Engenharia Eletrotécnica e de Computadores da Faculdade de Engenharia da Universidade do Porto 28 de Maio de 2014 Dedicated to Inês, Aurora and to what the future holds. In memory of Kika. i ii Acknowledgments The work presented in this thesis is a testament to how much I owe to my family, friends and professors. The following lines will certainly follow short on acknowledging how deeply grateful I am of being inspired by so many wonderful people. First and foremost, a word to Prof. João Barros, the first responsible for having me started on this journey. From the moment we met, João put a high expectation on me and gave me the confidence to pursue any goals I was set out to reach. Among the many things I could thank him for, I choose to thank him for his faith on my work and skills, for the freedom he gave me to work on any research topic I would fall in love with and for always stimulating me with his curiosity and enthusiasm. It was indeed a pleasure to share these last years with him. Second, I would like to thank the committee members, Professors Matthieu Bloch, Mikael Skoglund, Adriano Moreira, Jaime Cardoso and José Matos, for their availability to be part of the defense jury, but mostly for allowing me to be part of a great discussion on physical-layer security. I would also like to thank the opportunity given by Professor Matthieu Bloch and Professor Muriel Médard for allowing me to spend some time with their research groups at Georgia Tech Lorraine and MIT, respectively. The experiences have been both rewarding and fulfilling. Additional thanks to Professors Cristiano Torezzan and Willie Harrison who visited us in our lab and from whom I learnt so much! While the journey to the Ph.D. was long and weary, all my colleagues from the Networking and Information Security group at Instituto de Telecomunicações (IT-Porto) made it a lot more bearable. A salute to the groups former students João Vilela, Lu isa Lima, Mate Boban and Sérgio Crisóstomo and best wishes for all of you who are waiting in line: Hana, João Rodrigues, Mari, Pedro, Rui Meireles, Saurabh and Susana. I was fortunate enough to meet some of my best friends while working at NIS. They are role models in every aspect I can think about and will forever stay in my heart. Thank you Diogo for your spirit, your enthusiasm, for letting me train my parenting skills with you and for being always a great friend. Thank you minino Lato for having the patience to teach me how to do research, for setting the bar so high and specially for sharing so many memorable and crazy moments, even those that we do not remember. Thank you Paulo, for always putting doubts in my mind with respect to anything possibly imaginable. While it was always a source of constant laughing, it made me revisit many things which I would otherwise miss. To Rui, for always taking me back to the roots of greatness and reminding me never to settle for less. For sharing his passion for science and discovery and the constant seek for elegance. To Tiago, for teaching me so many things and showing me that everything can be built from even the smallest example. For being a constant reference in principles and values that should always be a part of any scientist. To all iii iv of you, I owe this thesis. Not only for the help you provided me with when I was stuck in technical details, but also for your faith in the problems I tackled and for the constant reminders of what we were set out to get when we all started this journey! Of course that I am also in debt to many of my friends outside work. To all of you, my sincere thanks. A special thank you to Eliana, André, their daughter Mafalda and their son Benjamim, for always reminding the values for which we should guide our lives with and for keeping in my mind that there is nothing more important than living fully, even among times where the hardest sacrifices are needed. To my parents Vitorino and Belarmina, and my brother Zé , whose sacrifice, endurance, guidance and example led me to finish this tough path. Without you support, it would be impossible to be who I am today. Lastly, to my wife Inês and my daughter Aurora. We have taken huge steps these last years, suffered great losses, overcame many obstacles and built so many beautiful things. Last time I wrote down we were going to write many stories. Eventually we were able to write the most beautiful fairy tale. Thank you for your infinite love and support. Thank you for the endless joy I felt from the moment we met. For being my future. With the greatest gratitude and love, João Almeida Resumo Os sistemas de comunicação vêem tomando um papel cada vez mais importante no nosso dia-a-dia. O uso difundido da Internet e sistemas de comunicação sem fios não só alteraram a forma como comunicamos, mas também o tipo de informação que comunicamos. Dado que a maior parte do canais de comunicação são susceptíveis a escutas, e frequentemente é pretendida a transmissão de dados sensíveis, existe uma clara necessidade de mecanismos que garantam confidencialidade de comunicação. Tradicionalmente, a confidencialidade de dados é gerida na camada de aplicação, usando primitivas criptográficas. No entanto, nos últimos anos, outros métodos de segurança foram desenvolvidos. Em particular, os métodos de segurança na camada física podem actuar como um complemento (ou alternativa) a soluções baseadas em criptografia. De uma forma geral, a ideia subjacente a estas técnicas é a utilização do ruído inerente aos canais de comunicação como fonte de aleatoriedade, um elemento essencial no desenho de sistemas de comunicação segura. O tópico fundamental desta tese é precisamente o desenvolvimento de esquemas de segurança para a camada física. Neste contexto, são exploradas várias alternativas ao estado-da-arte na construção de códigos seguros. Em particular, são fornecidas construções explícitas para fontes contínuas e discretas, com enfoque em códigos de tamanho finito. Primeiro, é desenvolvido um quantizador escalar com restrições de segurança. A ideia principal nesta construção é desenhar um código conjunto de fonte-canal que garanta que um atacante tenha uma distorção acima de um determinado limite. Tal objectivo é atingido usando um desenho cuidado dos parâmetros do quantizador escalar, nomeadamente as fonteiras de quantização e o número de níveis de quantização. Em seguida, é proposto o uso de mapeamentos de expansão de largura de banda para canais de wiretap com ruído Gaussiano aditivo. Tais mapeamentos são caracterizados pela existência de erros anómalos, quando o ruído de canal se situa acima de um dado nível. Estes erros tipicamente levam a estimativas afectadas por uma grande distorção. A ideia aplicada na construção é desenhar um código que garanta que um atacante é afectado por erros anómalos com elevada probabilidade. Para isso, é usada uma construção denominada Torus Layer Spherical Codes, que permite um controle intuitivo do nível a partir do qual erros anómalos surgem. Finalmente, é proposto o uso de puncionamento aleatório como meio de obter segurança em canais com apagamentos. O prícipio subjacente a esta construção é a interpretação da técnica de puncionamento aleatório como uma técnica de introdução de ruído artificial. Neste sentido, é possível utilizar o puncionamento aleatório para saturar o canal de um atacante com apagamentos, fora¸ndo-o a operar com elevada equivocação. Duas instâncias do sistema são consideradas. Primeiro é assumido que o padrão de v xii LIST OF FIGURES 4.8 Map of parametrizations for which there exists a solution to the reliability and secrecy constraints with n=2...................... 73 4.9 P(knbk ≤ d/2)and P(knek>d/2)as a function of distance d, for dimensions n=2,3,24and48. .......................... 75 5.1 Wiretap model of a coding scheme that uses puncturing to obtain secrecy. Two cases are considered: to the left the puncturing pattern is public, whereas to the right the the puncturing pattern is a shared secret between thelegitimateparties............................. 78 5.2 Operational interpretation of random puncturing, when the pattern is public (top figure) or secret (bottom figure). . . . . . . . . . . . . . . . . . . 79 5.3 Bipartite graph with n=7 variable nodes (represented by circles) and n−k=3 check nodes (represented by squares). . . . . . . . . . . . . . . 80 5.4 Example of a peeling decoder that is able to recover the transmitted codeword. .................................... 85 5.5 Example of a peeling decoder that is not able to recover the transmitted codeword................................... 86 5.6 Maximum puncturing probability γ∗as a function of the channel erasure probability δfor the ensembles C1,C2and C3when using a BP and a MAPdecoder................................. 98 5.7 Normalized equivocation rate for a publicly known puncturing pattern as a function of the wiretap channel erasure probability εusing a BP decoder. 99 5.8 Normalized equivocation rate for of a publicly known puncturing pattern as a function of the wiretap channel erasure probability εusing a MAP decoder.................................... 99 5.9 Rate-equivocation region and achievable rate-equivocation pairs for the ensembles C1,C2and C3, when using the largest admissible puncturing probabilities for varying values of ε.....................101 5.10 Equivocation rate for the legitimate receiver for codes C1,C2and C3with block-length n=12 as a function of the main channel erasure probability δ.102 5.11 Normalized equivocation rate for the eavesdropper for codes C1,C2and C3with block-length n=12, as a function of the wiretap channel erasure probability ε. The considered puncturing probabilities γare equal to εMAP,γ1and γ2................................103 5.12 Rate-equivocation regions of the considered models and the rate-equivocation pairs for codes C1,C2and C3for both the asymptotic and finite blocklength case. Wiretap model parameters are δ=0 and ε=0.25.......104 5.13 Simulated average bit error rate for the code C4as a function of the wiretap channel erasure probability ε, when the main channel erasure probability takes values from δ∈ {0,0.1,0.25}..................106 5.14 Simulated average bit error rate for the code C5as a function of the wiretap channel erasure probability ε, when the main channel erasure probability takes values from δ∈ {0,0.1,0.25}..................106 5.15 Bounds on the equivocation of simulated error probability for the code C4 as a function of the wiretap channel erasure probability ε, when the main channel erasure probability takes values from δ∈ {0,0.1,0.25}. .....107 LIST OF FIGURES xiii 5.16 Bounds on the equivocation of simulated error probability for the code C5 as a function of the wiretap channel erasure probability ε, when the main channel erasure probability takes values from δ∈ {0,0.1,0.25}. .....107 5.17 Shannon Cipher System with erasures. . . . . . . . . . . . . . . . . . . . 109 xiv LIST OF FIGURES List of Tables 2.1 Examples of secrecy criteria . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Comparison of code families . . . . . . . . . . . . . . . . . . . . . . . . 29 3.1 Performance of Lloyd-Max and channel-optimized scalar quantizers for a BSC(δ) ................................... 38 4.1 Performance of spherical codes for the wiretap channel with n=2. . . . . 73 5.1 Equivalence of rate-equivocation regions as a function of the disclosure strategy and nature of the puncturing pattern. . . . . . . . . . . . . . . . 95 5.2 Degree distributions of LDPC code ensembles C1,C2and C3........ 97 5.3 Puncturing probabilities of LDPC code ensembles C1,C2and C3with prescribed level of equivocation. . . . . . . . . . . . . . . . . . . . . . . 100 5.4 Degree distributions for the LDPC code ensembles C4, and C5. ......105 xv xvi LIST OF TABLES Notation XAlphabet or set pXProbability distribution of X X∼pXRandom variable Xfollows distribution pX pX|YConditional probability distribution of Xgiven Y EXExpected value over X H(X)Entropy of X H(X|Y)Conditional entropy of Xgiven Y I(X;Y)Mutual information between Xand Y 0,1nBinary vector of length n RField of real numbers FGalois Field λLagrangian multiplier ∇Gradient function N(µ,σ2)Gaussian distribution with mean µand variance σ2 knkNorm of vector n S1Sphere in the Euclidean space δSBDistance between folds in a curve δTDistance between two tori xvii xviii Notation Abbreviations AWGN Additive White Gaussian Noise BCC Broadcast Channel with Confidential Messages BER Bit error rate BDC Binary Deletion Channels BEC Binary Erasure Channel BEWC Binary Erasure Wiretap Channel BP Belief Propagation BSC Binary Symmetric Channel CO-SC Channel-Optimized Scalar Quantizer CSI Channel State Information CSNR Channel Signal-to-noise Ratio KKT Karush-Kuhn-Tucker LDPC Low-Density Parity Check LM-SC Lloyd-Max Scalar Quantizer MAP Maximum a Posteriori ML Maximum Likelihood MSE Mean Square Error MMSE Minimum Mean Square Error OPTA Optimum Performance Theoretically Achievable PDF Probability Density Function SC Spherical codes SK Shannon-Kotel’nikov SNR Signal-to-noise Ratio TLSC Torus Layer Spherical Codes WTC Wiretap Channel Model WTC-SK Wiretap Channel Model with a Shared Key xix xx Abbreviations Chapter 1 Introduction Devising schemes for secret communications has been an object of study almost since the invention of the first alphabets. In ancient civilizations, where the first forms of encryption appeared, they were mostly used to create an aura of mystery around messages written in tombstones [1]. However, they soon became an essential tool for military purposes across the ages. The ability to encrypt (or hide) the contents of messages was a crucial advantage in preparing field operations, as well as for secret diplomatic communication [1]. On the other hand, the competence on performing cryptanalysis, i.e., the ability to break an encryption scheme and obtaining the respective contents of a hidden message, became an even greater advantage, as it revealed plans and information from adversaries, allowing to properly adopt any necessary counter-measures. While in the past the arts of cryptography and cryptanalysis where mostly restricted to the domain of military and diplomatic communications, the evolution of computer networks has changed this paradigm, establishing security as a ubiquitous concern. In modern communication systems, entities interact using devices as proxies and communication takes place through channels that may be remotely eavesdropped/tampered. Such outline suggests a broad scope of security concerns [2]. For instance, communicating entities should be able to corroborate the identity of each other, which implies some sort of mechanism should provide for identity authentication. Users should be able to corroborate the source of a given received message, as well as being able to verify if that message have not been subject to changes. Therefore, mechanisms that guarantee message authentication and data integrity are imperative. It could also be the case that the origin or reception of a given message needs to be proven, for which schemes that ensure non-repudiation are required. Another relevant question is how to prevent unauthorized users from accessing some resource, which could be tackled with appropriate access control mechanisms. These examples illustrate some of the security objectives that should be met, if required by the communicating entities. Notwithstanding the emergence of these new security concerns, data confidentiality is still one of the most crucial security prob1 8Introduction one but rather with arbitrarily high probability. While this does not constitute a problem per se, care should be taken when specific codes are employed since they may not provide the level of secrecy one was expecting. Furthermore, the security notions are asymptotic by definition. Since any implementation of a physical-layer security system requires the use of finite block-lengths, one should proceed with caution when moving from code constructions based on asymptotic analysis to the finite block-length regime. In summary, security schemes based on the information-theoretic model may provide several benefits over schemes based on the computational model, either in terms of measurable secrecy and computational efficiency (secrecy is obtained via coding, which is already implemented in any communication system for reliability purposes). However, it also has some disadvantages which may not be neglected such as strict assumptions on channel models or the need to restrict the transmission rate to account for secrecy. That being said, it is certainly true that such schemes could be used to enhance the security at the higher layers of the protocol stack. For instance, physical-layer security schemes can be coupled with cryptographic schemes and guarantee that, with high probability, an adversary will have access to a cipher-text that contains errors [16]. Clearly, the task of a cryptanalyst is made harder since cryptographic attacks are generally designed under the assumption of a correct cipher-text. They can also simplify the task of key distribution, since they do not require a secure channel a priori. One can use the principles of physicallayer security to develop key agreement schemes based on the fact that an eavesdropper receives a signal that is different from the legitimate receiver [17]. Both these aspects suggest that a cross-layer approach to secrecy may be desirable in many cases. Along these lines, physical-layer security can be useful to enhance the security levels of current systems or to simplify the design of secrecy systems. This represents a departure from the complex security architectures that are currently employed, which make use of third parties for key distribution. It also provides the means to effectively assess the security of a system, by filling the lack of secrecy metrics that currently exists. 1.2 Motivation While the problem of coding for secrecy under the information-theoretic model is still unsolved in general, code designs that achieve secrecy capacity are in fact known. Many practical code constructions have been developed under the notion of weak secrecy proposed by Wyner [13]. Most of these code constructions share the same guideline, which is to map every message to possible multiple codewords and randomly choose a message within this set for transmission [15]. This principle can be put into practice using codes with a nested structure, where a codebook is partitioned onto several sub-codebooks, each one associated with a message to be transmitted. When the transmitter wishes to send a 1.2 Motivation 9 given message m, he randomly selects a message m0from the sub-codebook that is associated with mand transmits it. A sufficient condition to guarantee weak secrecy is to design the sub-codebooks to be capacity-achieving over the wiretap channel [3, Chapter 6]. Due to this seemingly simple constraint, nested codes became the prevailing practical code construction for physical-layer security. Consequently, most of the research efforts on coding for physical-layer security focus on finding codes, based on nested structures, that satisfy this condition. While useful from a theoretic and practical perspective, the application of nested codes can be limited by the operational environment [15]. These constructions have several requirements, some of which we list next. First, codes must have an arbitrarily large block-length. Second, channel state information (CSI) for the main and wiretap channel is required to properly dimension the codebook. Third, the code is dependent on such channel state information. The following observations, connected to these requirements, motivate the need for alternative code designs for secrecy: •In any communication system the employed codes must have a finite block-length. This remark has several ramifications: a) source-channel separation theorems may not hold, meaning that the optimal coding scheme for a communication system could involve solving a joint source-channel coding problem; b) the secrecy performance of a code may be far from the performance predicted by its asymptotic analysis; and c) the objective of achieving secrecy capacity becomes unreachable which may justify using alternative secrecy metrics. •While legitimate users may cooperate in order to characterize their communication channel, it may be very hard to obtain the CSI for the wiretap channel in practice. Therefore, code constructions should provide a good secrecy performance either for a large range of channel parameters or, if some estimate of the quality of the wiretap channel is available, under the circumstances of channel mismatch. •Depending on the communication environment, it may be the case that channel statistics vary over time. Since codes with nested structures vary the sizes of their sub-codebooks according the main and wiretap channel statistics, a change in channel condition may imply the design of a new code. Consequently, nested codes may be unfit for time-varying channels. The code designs proposed in this thesis attempt to circumvent the aforementioned issues. More precisely, the proposed code constructions are of finite block-length. Consequently, the secrecy analysis associated with these codes will reflect this fact. A key point is that the proposed codes do not strive to achieve the secrecy capacity, but rather ensure that the eavesdropper’s ability to estimate the sent messages is greatly impaired. We do require that this impact can be quantified through information theoretic quantities. 10 Introduction However, the secrecy criteria employed on the eavesdropper’s side may not necessarily be the eavesdropper’s equivocation, but could be, for instance, distortion. A second aspect is that the proposed codes are deterministic. This contrasts with the common approach used to design secrecy codes, which considers the use of stochastic encoders through instances of local randomness. The reason is that stochastic encoding is useful to cancel out the information leaked to the eavesdropper, but this requires CSI for the wiretap channel. Therefore, if such information is not available, it is not clear how to use the local randomness at the encoder to satisfy the secrecy constraints. Thus, our general approach to the problem of code design for secrecy focuses on meeting a certain reliability constraint while providing a best-effort approach with respect to secrecy. While deterministic constructions generally have a worse performance (in terms of secrecy) when compared to stochastic codes, they allow for a simplified design which is sufficient for the purposes we intend (design codes that provide a prescribed level of security for a large range of channel parameters). We do note that the proposed schemes can also be extended to include nested-like structures. Finally, we distinguish code constructions according to the type of source. We consider two types of sources: a) sources that are discrete in time and continuous in amplitude (herein referred as continuous sources) and b) sources that are discrete in time and amplitude (herein referred as discrete sources). While there exists a large body of research that addresses discrete sources, secrecy codes for continuous sources are almost non-existent5. The reason lies in the fact that, if source-channel separation theorems hold, the secrecy capacity may be achieved by using an optimal source encoder followed by an optimal wiretap code, and hence secrecy is achieved on the discrete part of the problem [18]. As mentioned before, these arguments may not hold and even if they do, both components may be extremely hard to design, thus motivating a different approach to the design of secrecy codes for continuous sources. 1.3 Outline and Main Contributions In this thesis we propose three coding schemes for the problem of confidential data transmission. The first two schemes are directed towards continuous sources, while the third focuses on discrete sources. Within the domain of continuous sources we propose a jointsource channel coding scheme based on scalar quantizers and a coding scheme based on bandwidth expansion mappings. The objectives in each of these constructions are distinct. The former construction forces eavesdroppers to operate bellow a desired performance 5Continuous sources arise in many situations. Audio and video signals can be represented by continuous variables that are subject to digitalization prior to transmission. The coefficients of Fourier and other related transforms are also generally represented by continuous variables. For instance, the discrete cosine transform (DCT), that is widely used in image coding standards, outputs real-valued coefficients. Signal processing techniques make ample use of continuous random variables (filtering, signal acquisition, ...). Additionally, natural sources (e.g. the quantities measured by a sensor) or artificially induced sources (e.g. sources induced from channel gains) can be represented by continuous variables. Thus, many applications could benefit from secure coding schemes that operate over continuous alphabets. 1.3 Outline and Main Contributions 11 threshold while the latter tries to ensure that the eavesdropper is bound to operate in a regime of anomalous errors, which greatly impacts the distortion of his estimates. Within the domain of discrete sources we propose a scheme based on randomly punctured LDPC codes. The scheme uses puncturing as a mechanism to introduce artificial noise to create a saturated channel from the eavesdropper’s perspective. It also tries to explore the lack of bit-level synchronization at the eavesdropper’s side to obtain higher secrecy gains. This is accomplished by allowing the puncturing pattern to be secret. The scheme also takes advantage of the fact that rate-compatible codes enable the adaptation of codes to channel conditions, without the need to design a new code. The main contributions of this thesis are as follows. •Scalar Quantization under Secrecy Constraints: We propose a joint sourcechannel coding approach to secrecy that is based on solving an optimization problem. The main idea is to find a joint source-channel code that minimizes the distortion at the legitimate receiver, subject to a distortion constraint on eavesdropper. The process involves finding the boundaries of a scalar quantizer as well as finding the optimal index assignment (channel code) that satisfies the above constraints. Our results demonstrate that such an approach can effectively bound the distortion at which the eavesdropper can operate, even when the channel to the eavesdropper is better than that of the legitimate receiver. •Piecewise Torus Layer Spherical Codes for Secrecy: We propose code constructions for the transmission of continuous sources without the need for quantization. The main technique employed is the transmission of curves over several layers of torus, which are obtained via spherical codes. By exploiting the geometrical properties of this construction, we find the code parameters which, with a desired probability, ensure decoding errors at the eavesdropper’s end that induce a large distortion. The construction has the additional advantage of transmitting messages over a dimension that is double the dimension of encoding and decoding. This feature can be used to obtain higher secrecy gains since the noise affecting the eavesdropper possesses more components. •Randomly Punctured LDPC Codes for Secrecy: We propose a coding scheme based on the principles of rate-compatible codes, where random puncturing is used to adapt both to the channel conditions as well as for secrecy purposes. We consider two scenarios: 1) the puncturing pattern is publicly known and 2) the puncturing pattern is a shared secret between the legitimate parties. We analyze the equivocation rate achieved by LDPC codes when the legitimate receiver has access to a belief propagation (BP) decoder or a maximum a posteriori (MAP) decoder. Our results indicate that using public puncturing patterns while allowing MAP decoding 12 Introduction leads to maximum equivocation for the eavesdropper (albeit at an increase in terms of rate - which prevents us from achieving perfect secrecy), while only allowing BP decoding results in a smaller equivocation for the eavesdropper but also a smaller transmission rate. Finally, it is shown that if the puncturing pattern is a shared secret, it is possible to achieve high equivocation rates for the eavesdropper, even for very small block-lengths. The effort to share the puncturing pattern depends on the puncturing probability. Hence, for large enough puncturing probabilities, the required secret rate can be deemed small. The rest of this thesis is organized as follows. Chapter 2introduces more formally the wiretap model, its fundamental limits and the state of the art in coding for secrecy. In Chapter 3we present a methodology for the design of scalar quantizers with secrecy constraints that bound the performance achieved by an eavesdropper. We pose the problem of secrecy as a constrained optimization problem and derive necessary conditions for locally optimal encoders and decoders (under a mean square error distortion criterion). We then present numerical results highlighting the distortion behaviour of the eavesdroppers optimal estimates under several scenarios. Bandwidth expansion mappings are introduced in Chapter 4, as well as a particular construction of these mappings that is based on mapping a source onto a set of curves over several layers of tori. We provide a characterization of the different types of errors that may occur in such construction. Then, assuming the main and wiretap channels are additive white Gaussian noise (AWGN), we use the geometrical properties of these codes to characterize the error probabilities associated with each type of error. Using these probabilities, we find the code parameters that ensure the eavesdroppers will suffer from the decoding errors that induce a distortion of largest magnitude. We then present several numerical results that relate to the code parameters, as well as the distortion behaviour of the eavesdropper. Chapter 5addresses the design of randomly punctured LDPC codes. We present wiretap channel models that take puncturing into account, derive the eavesdropper’s equivocation under these models and characterize their rate-equivocation regions. We also derive bounds on the allowed puncturing probabilities based on the code’s thresholds. We characterize the eavesdropper’s maximum likelihood decoder and present simulation results for specific code instances based on the derived decoder. We further present numerical results with respect to the eavesdropper’s equivocation rate, in particular asymptotic results for public puncturing patterns and finite block-length results for secret puncturing patterns. Chapter 6presents the conclusions of this thesis, discussing several directions for future work. Chapter 2 Coding for Secrecy In this chapter we will introduce some of the notions regarding the theory and practice of secrecy systems based on the information-theoretic security model. We assume familiarity with the basic definitions and results from information theory. For the sake of completeness, a necessary set of results that are used in this thesis are summarized in Appendix A. We will first formally introduce the definitions of wiretap channel and wiretap code, followed by possible definitions of reliability and secrecy constraints. We then move towards the characterization of the fundamental limits of secure communication under some of these constraints. We also review the design of state-of-the-art wiretap codes based on nested structures. 2.1 The Wiretap Channel Model The basic problem we wish to solve is how to transit some source message to a legitimate receiver that is able to correctly decode such message while keeping it secret from unintended recipients. Thus, we wish to solve a communication problem with two constraints: a reliability constraint for communication between the legitimate party and a secrecy constraint with respect to the eavesdropper’s observations. In the context of physical-layer security, this problem can be modelled using the socalled wiretap channel model, illustrated in its generalized form in Fig. 2.1. It incorporates three users: a sender (Alice), a legitimate receiver (Bob) and an eavesdropper (Eve). Both Bob and Eve receive the messages transmitted by Alice through a broadcast channel, which comprised of two parallel channels. The channel from Alice to Bob is called the main channel, while the channel from Alice to Eve is called the wiretap channel. For simplicity, we will assume throughout this thesis that both channels are memoryless and the noise is assumed to be independent for Bob and Eve. It is also possible to consider the case where noise the main and wiretap channels do not have independent noise. In these cases, one generally obtains less secrecy, reason for which one should try to use 13 14 Coding for Secrecy Alice Encoder P Yn|Xn(yn|xn)Decoder Bob PZn|Xn(zn|xn)Eve M XnYn˜ M Zn Figure 2.1: Wiretap channel model. alternative techniques such as interleaving in the attempt to create independent channels. Formally, the wiretap channel can be defined as follows. Definition 1 (Wiretap channel).A wiretap channel (X,Y,Z,pY Z|X(y,z|x)) is characterized by a quadruple that consists of one input alphabet X, two output alphabets Yand Z and a transition probability matrix pYZ|X(y,z|x). As noted in Section 1.1, secrecy can be ensured through coding. Hence, to communicate over the wiretap channel, Alice chooses a message Mthat she wishes to securely transmit to Bob. She then encodes this message onto the channel input vector Xnusing some wiretap code. Through the main channel, Bob observes a possibly noisy codeword Yn, while Eve observes also a possibly noisy codeword Znthrough the wiretap channel. Since the main and wiretap channel are memoryless, we have that pYnZn|Xn(yn,zn|xn) = n ∏ i=1 pYZ|X(yi,zi|xi). The wiretap code is responsible for ensuring that reliable and secure communication is possible. By reliable it should be understood that Bob can reproduce the source message with negligible error, while by secure it should be understood that Eve’s estimates of the source message are erroneous. How one can exactly measure the reliability and secrecy performance of a particular code will be briefly addressed. Let us first formally introduce wiretap codes. A (discrete) wiretap code can be defined as follows. Definition 2 (Discrete wiretap code).A (2nR,n) code Cnfor a wiretap channel consists of •A countable message set M= [1,...,2nR]; •An encoding function (possibly stochastic) f:M → X n, mapping source messages onto channel codewords; •A decoding function g:Yn→ M∪{?}, mapping channel observations to the source message set or an error message. 2.2 Reliability and Secrecy Metrics 15 Note that the wiretap code needs to introduce sufficient redundancy so that the legitimate user is able to decode the messages without any errors. This redundancy also provides the eavesdropper useful information. Therefore, allowing the encoder to be stochastic is essential to achieve full secrecy. The introduced randomness provides the means to cancel some information leakage that may occur while using a particular codebook for transmission. On the other hand, as discussed before, unless we have some knowledge about the wiretap channel, it is not clear how one can use this randomness. This problem can be circumvented by designing deterministic secrecy codes, which simply rely on the randomness provided by channel. They do incur in some information leakage, and therefore do not achieve full secrecy. However, if codes are carefully designed, such leakage may be small enough that no meaningful information can be extracted from it. 2.2 Reliability and Secrecy Metrics Recall that our main objective is to design coding schemes that allow two parties to communicate reliably, while preventing an eavesdropper from acquiring any meaningful information about the transmitted messages. Thus, as mentioned earlier, the system should guarantee two constraints: a reliability constraint and a secrecy constraint. Such constraints may take many forms, although ultimately they aim at the following general goals: an admissible (preferably negligible) error probability for the legitimate party (reliability) and statistical independence between the transmitted messages and the eavesdropper’s observations (secrecy). The reason why statistical independence is relevant from a security perspective is that it reduces the best attack strategy of an eavesdropper to random guessing. 2.2.1 Reliability Constraints The most common measure used for reliability is the average error probability of the wiretap code Pe(Cn),Pr{˜ M6=M|Cn},(2.1) which measures the average probability that the legitimate receiver estimates the wrong message. In the discrete case, Pe(Cn)amounts to Pe(Cn) = 1 d2nRe d2nRe ∑ m=1 Pr{˜m6=m|Cn}.(2.2) 16 Coding for Secrecy Commonly, we wish that legitimate parties communicate with negligible error. Then, the reliability constraint to be satisfied is formulated as lim n→∞Pe(Cn) = 0.(2.3) However, it may be the case that the average error probability is hard to analyze for a given wiretap code. Alternative metrics can be used in such cases, like the average biterror rate (BER) [19,20]. The BER is an approximate estimate of the bit error probability, thus capturing a similar idea to the average error probability. The reliability constraint can be defined in a similar manner to (2.3), by requiring that BER for the legitimate receiver to approach zero in the limit of large block-lengths. Finally, distortion can also be used to characterize the reliability of a wiretap code. A distortion formulation of the problem of secure communication was provided in [18] and extended in [21]. The main motivation was to understand how allowing a prescribed level of distortion for the legitimate receiver could provide a positive impact on the secrecy of the system. The reliability constraint to be satisfied can be formulated as E{d(M,˜ M)} ≤ ˜ D+ε,(2.4) where Edenotes expectation, d(·,·)is a distortion function and ˜ Dis the prescribed level of distortion. The formulation of reliability is terms of distortions bears an additional challenge, which is to find an appropriate distortion measure, that reflects the cost of choosing the representation of the source message by its reconstruction point. For instance, for some sources squared error distortion may be a good candidate, while for others not. The choice of a particular measure for reliability does not require an extensive justification. As noted before, the general requirement is a vanishing error probability, be it in any type or form. However, the choice of a particular measure for secrecy should certainly be more judicious. 2.2.2 Secrecy Constraints The first information-theoretic secrecy metric, introduced by Shannon [9], was unconditional security, also known as perfect secrecy. To obtain perfect secrecy exact statistical independence1is required with respect to the source message and the eavesdropper’s observation. Assuming the wiretap code Cnis known to all parties, perfect secrecy is defined as follows. H(M|Zn) = H(M)(2.5) 1We note that statistical independence could be measured in terms of any distance between joint probability distributions. In this thesis we focus on the Kullback-Leibler divergence, which is equivalent to the mutual information. 2.2 Reliability and Secrecy Metrics 17 or alternatively I(M;Zn) = 0.(2.6) Systems that provide perfect secrecy have demanding constraints which in practice are very hard to meet. To circumvent this issue, it is possible to relax the secrecy constraint. Rather than requiring exact statistical independence between Mand Zn, consider the case of asymptotic statistical independence. The secrecy constraint then becomes lim n→∞I(M;Zn) = 0.(2.7) This constraint is commonly referred as strong secrecy and implies that the total amount of information leaked to the eavesdropper goes to zero as the size of the codewords goes to infinity. While the strong secrecy constraint is less restrictive than perfect secrecy, designing codes for the strong secrecy constraint is still very challenging. Most practical code constructions adopt an even less restrictive constraint. Instead of requiring a total leakage of zero, they require the leakage rate to the eavesdropper to be vanishing, as the size of the codewords goes to infinity. This constraint can be formalized as follows. lim n→∞ 1 nI(M;Zn) = 0.(2.8) It should be noted that the same coding rates are achievable under the strong and weak secrecy constraints [22], although current coding schemes still incur in rate losses to ensure strong secrecy [23]. All of the above criteria depend on the ability to analyze the equivocation of Cn. In some cases, most notably when Cnis a code of finite block-length, it may be hard to exactly analyze the code’s equivocation. To circumvent this issue, several researchers have adopted the code’s average error probability or the bit error probability as a secrecy criterion. In such cases, it is required that the eavesdropper’s estimates of the source message suffer from an arbitrarily high error probability (or alternatively the error probability is bounded above a prescribed threshold). This secrecy formulation was used to analyze the secrecy of punctured LDPC codes [19] or lattice codes [24] over Gaussian wiretap channels. The analysis of the secrecy constraint is simplified by using density evolution techniques in the former case and geometrical arguments on the latter. We stress that error based metrics do not guarantee secrecy in an information-theoretic sense, i.e. a high error-rate does not imply a high equivocation. That being said, the errorrate could, in fact, be a pointer to the secrecy performance of a particular code. Moreover, since the equivocation of a code can be bounded with respect to the decoding error [25], this constitutes an alternative way to find codes that may be interesting from a secrecy 24 Coding for Secrecy This results can be interpreted as follows: if distortion ˜ Dis allowed at the legitimate receiver, then a code attaining the rate-distortion function R(˜ D)will induce an uncertainty 1 log|M|[H(M)−R(˜ D)], while the channel will induce the remaining part. This further indicates that this pair can be achieved by concatenating an optimal source code and an optimal wiretap code [18]. Intuitively, relaxing the reliability constraint allows us to achieve a larger transmission rate. It also impacts secrecy, as the distortion allowed at the legitimate receiver will also increase the equivocation of the eavesdropper by the difference between the source entropy and the rate-distortion function. The price to pay in this case is an increase in the probability of error of the legitimate receiver (more precisely increased distortion). Lastly, consider the case where the legitimate receiver are allowed a maximum distortion ˜ Dand the eavesdropper is imposed a minimum distortion of ˆ D. Theorem 4. ([27, Corollary 4]) Consider a wiretap channel (X,Y,Z, pY Z|X(y,z|x)) such that the wiretap channel is physically or stochastically degraded w.r.t the main channel. Define the set RWT d(pX)as RWT d(pX) = ((R,ˆ D):R≥1 nI(Xn;Yn) min zE{d(X,Y,z)} ≥ ˆ D). Then, the rate-distortion region for this wiretap channel is closure of all the above tuples, i.e. RWT d=[ pY|X RWT d(pX).(2.14) This last case considers a relaxation of both the reliability and secrecy constraints. As in the previous case, the transmission rate can be increased by allowing a distortion ˜ D. In particular, the allowed transmission rate is larger than the channel capacity. On the other hand, the eavesdroppers equivocation is no longer bounded by the distortion allowed at the legitimate receiver, but instead a pre-fixed value for distortion is assigned. This may further allow an increase in transmission rate as this condition may be less stringent than the one stated in Theorem 3. In this case, the price to be paid in an increase in the distortion of the legitimate receiver’s observations, as well as in the amount of information leaked to the eavesdropper. Almost all practical code constructions strive to achieve either the weak or strong secrecy capacity. In fact, to the best of our knowledge, there are no practical code constructions designed specifically for regions defined in Theorems 3and 4. However, with respect to the case of weak/strong secrecy with lossy reconstruction, we point out that the rate-equivocation regions can be achieved by the concatenation of an optimal source code 2.5 Practical Code Constructions for the Wiretap Channel 25 ≈2nI(X;Y) codewords ≈2nI(X;Z) codewords per bin ≈2nI(X;Y|Z) bins Figure 2.2: Binning structure. and an optimal wiretap code [18] and, therefore, practical weak/strong secrecy achieving codes can be used within this context. As mentioned in Section 1.2, these code constructions are typically based on nested structures. The following section provides an overview of this design strategy and its connection to the fundamental limits of secure communication. 2.5 Practical Code Constructions for the Wiretap Channel Most of the practical constructions of secrecy codes draw inspiration from the following random code construction. Let there be 2n(R+R1)codewords with symbols generated independently according to a distribution PX. Divide the set of codewords into approximately 2nR bins of size greater or equal than 2nR1and associate a source message to each bin. Then, to securely transmit some source message, select (at random) a codeword from the bin that corresponds to that same source message. Using typicality arguments [3, Chapter 3.4], it is possible to show that reliability is achieved if R+R1<I(X;Y)−εand R1<I(X;Z)−ε. On the other hand, it is possible to show that the leakage rate 1 nI(M;Zn)of this code construction is upper bounded by 1 nI(M;Zn)≤I(X;Z)−R1+ε. Therefore, it suffices to choose R<I(X;Y)−I(X;Z)and R1=I(X;Z)−εto ensure reliable communications with a vanishing leakage rate (weak secrecy). An example of a binning structure with such an instantiation for Rand R1is shown in Fig. 2.2. 26 Coding for Secrecy m m0 Figure 2.3: Nested code structure. Such random code constructions are not useful in practice, since they require exponentially large memory for storage. However, it is possible to implement a similar idea using the notion of nested codes. Nested codes can be roughly described as codes that are formed by the union of several sub-codes. More precisely, a nested code Ccomposed of d2nResub-codes can be defined as C= d2nRe S i=1 Ci, where each sub-code has 2nR1codewords. Hence, nested codes are somewhat analogous to the previously described binning structure (in the sense that we can interpret each bin as a sub-code). Transmission is achieved by choosing a message m∈[1,...,2nR]and an index m0∈[1,...,2nR1]uniformly at random and transmitting the m0-th codeword in from the sub-code Cm. This strategy is illustrated in Fig. 2.3, where now a particular bin is seen as a row of the nested code. It is possible to show that the leakage rate of a nested code is bounded by 1 nI(M;Zn)≤ 1 nI(Xn;Zn)−H(M0)+H(M0|MZn)≤1 nnCe−H(M0)+H(M0|MZn), where Cedenotes the capacity of the wiretap channel (a possible proof is provided in Appendix B). Note that H(M0)denotes the rate of each sub-code and H(M0|MZn)denotes the uncertainty of the eavesdropper with respect to m0for a given sub-code. Then, it is sufficient to choose sub-codes that are capacity-achieving over the eavesdroppers channel in order to obtain weak secrecy, since in this case we have that 1 nH(M0)≈Ceand 1 nH(M0|MZn)≈0. This seemingly simple guideline motivated the design of several explicit nested code constructions. These code constructions mostly differ in the way that nesting is implemented, by relying on different properties of the constituent codes. In [15], the general principles of practical code constructions are described as well as detailed constructions of many codes. For the sake of completeness, we will briefly review some of the possible code constructions. In [29], the authors design nested codes using the cosets of duals of LDPC codes for a wiretap model composed of a noiseless main channel and a binary erasure wiretap channel. The code construction relies on the following property. Let a coset code Cbe formed by taking the cosets of a (n,n−k) binary linear code C0with generator matrix G0 and parity check matrix H0, i.e. C=S s C0(s), where C0(s),{x∈ {0,1}n:H0x=s}. If any sub-matrix of µcolumns of G0has rank µit is possible to show that any sequence x0 2.5 Practical Code Constructions for the Wiretap Channel 27 of length nwith µunerased positions will be consistent2with all cosets of C. Moreover, the number of sequences that are consistent with x0is the same for all cosets. Thus, a necessary and sufficient condition for perfect secrecy when an eavesdropper observes sequences with µunerased positions is that any sub-matrix of µcolumns of G0has rank µ. This property can be leveraged in the following way. If the wiretap channel is a binary erasure channel with erasure probability ε, with high probability, we have µ=1−ε. Consider an LDPC code Cwith a parity check matrix H, drawn from an ensemble with abelief propagation (BP) decoding threshold α∗3. It is possible to show that, if we randomly select a nαcolumns of H, with α<α∗, then, with high probability, the rank of this matrix will be nα. Hence, to satisfy the aforementioned conditions on the generator matrix, we can use the parity check matrix of an LDPC code with a BP decoding threshold α∗as a generator matrix for our coset code, or in other words, we can use the dual code C⊥and its cosets, to ensure perfect (weak) secrecy for a binary erasure wiretap channel with erasure probability ε>1−α∗. In [30], a coset coding solution based on punctured LDPC codes is proposed for the AWGN wiretap model. While in the previous code construction the nested code structure was induced by coset encoding and the code was constructed using code properties inherited from the LDPC decoding thresholds, in [30] the nested structure is induced explicitly by the puncturing operation and the code is constructed directly using the capacityachieving properties of LDPC codes. The construction is as follows. Consider an (n0,l) LDPC code C0, with parity check matrix H0of the from H0= [H1,H2], where H2is a (n0−l)×(n0−l)lower triangular matrix. The codewords of C0can be thought of as vectors of the form x= [m,m0,c], where |m|=k,|m0|=l−kand |c|=n0−l, with k<l. Moreover, for fixed mand m0,c= [m,m0]H| 1(H−1 2)|. We can induce a nested code structure using C0by creating an (n,k)code Cthat consists of all punctured codewords of the form [m0c], where Cis partitioned according to the punctured bits m. Hence, mindicates which sub-code will be used for its transmission. The random choice of a codeword in the sub-code can be performed by randomly choosing the l−ksymbols of m0. The transmitted codeword is then given by x0= [m0,c]and weak secrecy can be achieved if C0is designed such that the resulting sub-codes are capacity approaching. Another possible nested code construction based on two-edge type LDPC codes was proposed in [31]. Two-edge type LDPC codes provide a natural way of implementing a nested structure, since their parity-check matrices are of the form H="H1 H2#, where H is a n(1−R)×nmatrix and H1is an n(1−R1)×nmatrix, with R1>R. In particular, 2A sequence x0with µerasures is said to be consistent with a sequence xif the values of the unerased positions in x0match with the values of the same positions in x. A sequence x0is said to be consistent with a coset if the coset possesses at least one sequence that is consistent with x0. 3The BP decoding threshold is the largest erasure probability such that a BP decoder can ensure vanishing bit error probability. It will be formally defined in Chapter 5 28 Coding for Secrecy the linear code Cdefined by the matrix His a sub-code of the linear code C1defined by the matrix H1, and the distinct cosets of Cin C1form a partition of C. Each coset of C in C1consists of the solutions of the equation Hx = [H1x H2x]=[0 m]for some m. To encode a secret message mwe randomly choose a solution xfrom all the solutions of the equation above. This can be explicitly accomplished by creating a generator matrix G0="G∗ G#, where Gis the generator matrix associated with H,G∗is a matrix composed of linearly independent rows and G0forms a basis for the code with parity check matrix H1. Then, xcan be computed as x= [m,m0]"G∗ G#, where m0is a vector of nR random bits. Consequently, to achieve weak secrecy we only need for the cosets charaterized by Hto be capacity-achieving for the eavesdropper’s channel. Finally, polar codes have also been used to design nested structures [32,33,34]. The basic idea behind polar codes is to use a specific linear transformation to encode the messages, such that when each bit is transmitted over its respective bit channel, it polarizes (i.e. it becomes either almost noise free or almost noisy). Moreover, these bit channels always polarize in the same direction, hence if the quality of the channel is measured, one can identify the set of bits that will become noise free (also known as good bit channels) and the set of bits that will become noisy (bad bit channels). Additionally, it can be shown that the fraction of good bit channels converges to the channel capacity. Now suppose that the wiretap channel is degraded with respect to main channel. Using the above results its possible to identify three sets of channels: the set of bits channels that are only decodable by the legitimate receiver, the set of bit channels that are decodable by both receivers, and the set of bit channel that are not decodable by the legitimate receiver. Then, the secret bits can be sent over the set of channels that is decodable only by the legitimate receiver, while random bits are sent over the bit channels that are decodable by both and frozen bits are sent onto the channels that are not decodable by any. The nested code structure is implicit in the choice of the set of channels, since partitioning the bit channels induce a coset code. While in general, the above constructions only achieve weak secrecy, it is possible to show that under additional constraints they may achieve also strong secrecy. For instance, [23] shows that the duals of LDPC codes with large girth are able to ensure strong secrecy. However, this is achieved at the cost of the achievable rate. If the main channel is noiseless, polar codes can also offer strong secrecy in [32]. Table 2.2 (from [15]) summarizes the state-of-the-art in coding for secrecy. 2.6 Discussion 29 Table 2.2: Comparison of code families Constituent codes Secrecy Main channel Eavesdropper’s channel Duals of LDPC weak [29]noiseless erasure Duals of LDPC strong [35,23]noiseless erasure Two-edge LDPC codes weak [31,36]erasure erasure and degraded Polar codes weak [32,34,33]binary symmetric binary symmetric and degraded Polar codes strong [32]noiseless symmetric 2.6 Discussion In this chapter we reviewed the basic principles underlying the information-theoretic security model. In particular, we reviewed the definitions of the generalized wiretap channel and wiretap codes. We provided the characterization of the fundamental limits of secure communications for this channel model under multiple reliability and secrecy constraints, as well as examples of common secrecy code constructions for achieving weak secrecy capacity. In the light of these results, let us revisit some of the design choices stated in Section 1.2. Throughout this thesis, the proposed wiretap codes are deterministic. We have seen that stochastic encoding can achieve a leakage rate 1 nI(M;Zn)≤1 nI(Xn;Zn)−H(M0) + H(M0|MZn). In this case, the randomization over the choice of M0provided a simple guideline to design codes with vanishingly small leakage: choose a code such that 1 nH(M0≈1 nI(Xn;Zn)to cancel the leakage of information to the eavesdropper and such that 1 nH(M0|MZn)≈0. If codes are deterministic, the leakage rate 1 nI(M;Zn)≤1 nI(Xn;Zn). This means that the leakage rate of a deterministic code will be less or equal to the channel capacity of the wiretap channel. From an operational perspective, it is still possible to achieve a vanishingly small leakage rate with a deterministic code if somehow one is able to reduce the wiretap channel to a channel with a vanishingly small capacity. On the other hand, 1 nI(M;Zn) = 1 nH(M)−H(M|Zn). This definition suggests the following obvious observation: reducing the rate of source messages H(M)also reduces the leakage to the eavesdropper. Therefore, the rate of source messages can be used to bound the leakage rate. Of course that reducing the rate of source messages affects negatively the legitimate party. However, it suggests that it is possible to control the leakage rate to some extent, if the difference between H(M|Zn)and H(M|Yn)is exploited properly. These two aspects support the intuition behind the proposed code designs. More precisely, the coding scheme presented in Chapter 3uses the idea of restricting the source rate to ensure that an eavesdropper has a lower bound on his distortion, while allowing the legitimate receiver to lower its own distortion when the channel to the eavesdropper becomes poor. The coding scheme in Chapter 4uses the idea of emulating a poor wiretap channel by designing 30 Coding for Secrecy a code that is unfit for that channel. In particular, it uses the noise of the main channel to design a code that operates with negligible error only below this noise threshold. If the wiretap channel in noisier than the main channel, then it is possible to parametrize the code to induce large errors on the eavesdroppers estimates. Chapter 5also uses the idea of emulating a poor channel to the eavesdropper by considering a random puncturing strategy, where puncturing is essentially used to introduce erasures. Therefore, a new (artificial) wiretap channel is created, trying to ensure this channel has a vanishingly small capacity. Another aspect that is present in this thesis is the separation of codes according to the source type (continuous or discrete). With this respect, we note that wiretap codes (possibly stochastic) can also be defined for continuous random variables. They have the same structure as the codes defined above, though defined over continuous sets. For example, assuming that sources take values from the set of the real numbers R, the message set would be defined over the support set of the source outputs (i.e. M ⊆ R). The encoding function would operate over these continuous variables and the decoding function would map channel outputs also onto continuous variables (i.e. g:Ym→ M ⊆ R∪ {?}). As noted before, such construction can be avoided if separation theorems hold and assume the existence of practical optimal source and wiretap codes [37,38]. For this reason, practical code constructions for continuous sources are almost non-existent in their own. For instance, [37] proposed the use an optimal vector quantizer, whose outputs are coded using a wiretap code. To achieve a graceful SNR degradation when there is an SNR mismatch, the authors also superimpose the coded message with a scaled version of the quantization error. In [38], the authors propose a scheme that does not use an explicit quantization of the source, but a rather pre-coding stage where the encoded message is added with a properly scaled version of the source message and then encoded using a wiretap code. In both cases, a fixed leakage rate is assumed and the authors study the impact of channel mismatch on the distortion of the legitimate user. In contrast with this approach, our goal is to design codes with finite block-lengths, where the above separation arguments may not hold. Consequently, we explore two strategies for designing codes for continuous sources. The first is a (digital) joint source-channel code based on scalar quantizers and the second is a (fully) continuous code based on bandwidth expansion mappings. The objectives of each construction are different. While the first tries to explore quantization (and channel) noise for secrecy, the second tries to explore the mapping between the source and the channel space to guarantee secrecy. Clearly, the performance of these codes cannot be assessed in the same manner as discrete codes. While for discrete codes we can measure efficiency through the code rate R=1 nlog|M|, in the continuous case the efficiency of the code should to be measured by other characteristics, such as the bandwidth expansion. Furthermore, the metrics that are used in assessing the secrecy performance of wiretap codes for discrete sources may lose their meaning when moving towards continu- 2.6 Discussion 31 ous sources. For instance, the continuous representation of equivocation is the differential entropy, which does not have the same operational meaning has its discrete counterpart (and in fact could be negative). In particular, for continuous sources we adopt distortion as a secrecy metric as it is a measurable quantity and provides some operational meaning to secrecy. Recall that Chapters 3and 4address the case of continuous sources, while Chapter 5 addresses the case of discrete sources. 32 Coding for Secrecy Chapter 3 Scalar Quantization under Secrecy Constraints Scalar quantization generally refers to the process of partitioning a continuous interval onto a finite set of disjoint sub-intervals, indexed in an arbitrary manner. The main idea is that one can represent the values in each sub-interval through its associated index, thus compressing the representation of an infinitely large set of values to a finite (or countably infinite) one. This partition can be characterized by a set of thresholds (or quantizer boundaries) defining each of the sub-intervals. Obviously, scalar quantization can be used as a building block to a communication system where the source is continuous. In particular, it is possible to partition the support set of the source into index sub-intervals for which some channel codeword is assigned. Then, each source value falling in a given sub-interval will be mapped onto the channel codeword associated with the sub-interval’s index. If the quantizer is of fixed rate (meaning that each index can be represented by a binary sequence of the same length), then the rate of the quantizer is a function of the number of partitions though the relationship R=dlogNe, where Ndenotes the number of partitions. Decoding can then be accomplished as usual by estimating which source value was transmitted given that a particular codeword was observed. The quality of a quantizer can be assessed through a distortion measure comparing the original source value with its estimate. Then, designing a good scalar quantizer is the matter of finding a good trade-off between the allocated rate and a prescribed distortion. In general, the distortion associated with a scalar quantizer is a function of the quantizer boundaries. If this quantizer is used in a communication system subject to noise, it is also a function of the chosen index assignments. This contrasts with the case where scalar quantization is used in a source coding context, which essentially sees channels as being noiseless. Thus, designing a scalar quantizer that performs optimally for a given channel amounts to finding the optimal partitions as well as the optimal index assignments. Consequently, scalar quantizers for channels of different quality may differ in both these 33 40 Scalar Quantization under Secrecy Constraints In this context, we provide a methodology for the design of a scalar quantizers with secrecy constraints in the spirit of [39]. More precisely, we formulate the problem of quantizer design as an optimization problem, where the goal is to minimize the legitimate receiver’s distortion subject to a lower bound on the distortion of the eavesdropper, i.e. D(Γ,Ψ)>∆. This secrecy constraint controls the rate-secrecy trade-off and ultimately defines the secrecy level of the system. In the following, we will assume that channel codewords have binary representations, i.e. xi n∈Fn 2for all i, and we will focus on the case where the distortion criterion amounts to the mean square error, i.e. D(Γ,Φ) = E{(˜u−u)2}and D(Γ,Ψ) = E{(ˆu−u)2}, which is a widely accepted distortion metric. However, we note that the problem formulation is sufficiently general to allow for other channel input alphabets as well as distortion metrics1. 3.2.1 Problem Statement The general problem we aim to solve is a non-linear constraint optimization problem of the form minimize D(Γ,Φ) subject to D(Γ,Ψ)>∆.(3.3) One way to solve (3.3) is to translate it into an unconstrained optimization problem using Lagrange multipliers [43, Chapter 5]. To this purpose we define the following Lagrangian function L(Γ,Φ,Ψ,λ) = D(Γ,Φ)−λ(D(Γ,Ψ)−∆),(3.4) where λis the Lagrange multiplier as well as the Lagrange dual function g: dom(λ)→R such that g(λ) = min Γ,Φ,Ψ{L(Γ,Φ,Ψ,λ)},(3.5) Let us denote the optimal solution (if it exists) of the problem with tuple (Γ∗,Φ∗,Ψ∗,λ∗), giving rise to the solution L(Γ∗,Φ∗,Ψ∗,λ∗). Under certain conditions it is possible to directly obtain the necessary conditions for optimality. For instance, if L(Γ,Φ,Ψ,λ), D(Γ,Φ)and D(Γ,Ψ)are differentiable and D(Γ,Φ)−g(λ) = 0, i.e. if the duality gap is zero, then the Karush-Kuhn-Tucker (KKT) conditions can be employed [43, Chapter 5]. 1The reason for stating such assumptions at this point is due their implications with respect to what we may state about the optimality of the proposed approach. 3.2 Scalar Quantizers under Security Constraints 41 In particular, if (Γ∗,Φ∗,Ψ∗,λ∗)is an optimal solution, then we have that D(Γ∗,Ψ∗)−∆≥0 λ∗≥0 λ∗(D(Γ∗,Ψ∗)−∆) = 0 ∇D(Γ∗,Φ∗)−λ∗∇(D(Γ∗,Ψ∗)−∆) = 0, where ∇is the gradient function. However, in the context of our quantization problem, the Lagrangian function is not differentiable in general. For instance, if the MSE is used as a distortion criteria, L(Γ,Φ,Ψ,λ) is not differentiable with respect to the encoder parameters (boundary thresholds)2. Thus, if we are to use the method of Lagrange multipliers, we are bound to obtain a sub-optimal solution. Nevertheless, such solution still satisfies our secrecy constraint (it is a local minimum with respect to the distortion at the legitimate receiver). If we wish to minimize the objective function given by (3.3) we can find the solution to the following problem argmax λ argmin Γ,Φ L(Γ,Φ,Ψ,λ),(3.6) where λ∈[0,∞[. We do not need to consider optimization of Ψsince we assume the eavesdropper will always use its optimal decoder. We will employ an iterative optimization strategy, similar to that of the Lloyd-Max algorithm [41], [42], in which the encoder and decoder are alternately optimized until convergence (or some stopping criterion is met). An overview of the strategy adopted to solve (3.6) is provided next. 3.2.2 Overview of the optimization strategy Starting with an encoder/decoder pair Γand Φwe iteratively compute the optimal encoder Γ∗(assuming a fixed decoder) and the optimal decoder Φ∗(assuming the previously found encoder). This procedure is repeated until convergence is achieved, at which point Γ∗and Φ∗are output. The encoder optimization procedure makes use of the Lagrange dual principle (as described in Section 3.2.3) and tackles the problem of finding the optimal encoder as a function of the Lagrange multiplier λ. To achieve this, the optimal encoder is found for a fixed λand then the optimal value of λis found numerically through the Lagrange dual function. This two-stage procedure may incur in a loss of global optimality, since the solution to the Lagrangian dual function only provides, in general, a lower bound to the optimal solution. 2Changing the encoder parameters leads to an effective change on the size of the associated intervals. Since this change might lead to the disappearance of some other boundary, a discrete change in the number of quantization intervals occurs, which reflects as a non-differentiable points in the Lagrangian function. 42 Scalar Quantization under Secrecy Constraints Initial Γ,Φ Converges? Output Γ∗,Φ∗ Encoder Optimization Decoder Optimization Realizable regions as function of λ Find Γ∗(λ) Find λ∗Γ∗(λ∗) Φ∗ no yes Lagrange dual principle Figure 3.4: Overview of optimization procedure. In the context of our problem, there is a further aspect that has to be taken into account. The encoder is a function of λ. In particular, the value of λaffects the encoder structure, in the sense that different values of λmay change for instance the number of quantizations intervals, as noted before. Accordingly, before finding the optimal encoder as a function of λ, we first find the regions for which the encoder structure is not changed as a function of λ, denoted as realizable regions. Then, the above two-stage procedure is used for each of these realizable regions. Consequently, the optimal encoder and the solution to the Lagrangian dual function must be found among all the individual solutions for each realizable region. An illustration of the flow for the complete optimization procedure is depicted in Fig 3.4. 3.2 Scalar Quantizers under Security Constraints 43 3.2.3 Encoder Optimization Following the principles from [39] we wish to develop the necessary optimality conditions for the encoder Γ, given a fixed decoder Φ, i.e. for the problem argmax λ argmin Γ L(Γ,Φ,Ψ,λ).(3.7) To reduce the complexity of the problem (which involves optimizing both Γand λ) we can decouple the optimization in two stages, which can be approached subsequently. The encoder can be written as a function of of λ, i.e. Γ=Γ(λ)and (3.5) can be simplified as g(λ) = min Γ{L(Γ,Φ,Ψ,λ)},(3.8) where Φand Ψare considered to be given. From the Lagrange dual principle, we have that L∗≥max λ≥0{g(λ)}.(3.9) If equality holds in (3.9), the global optimal solution (Γ∗,λ∗)is given by Γ∗=Γ∗(λ∗),(3.10) where Γ∗(λ) = argmin Γ {L(Γ,Φ,Ψ,λ)}(3.11) and λ∗=argmax λ≥0 {g(λ)}.(3.12) Consequently, the solution to (3.7) is L∗=L(Γ∗,λ∗). If equality does not hold, then (3.9) merely presents a valid lower bound for L∗and the derived solution reflects, at most, a local optimal solution. Equations (3.10)- (3.12) suggest the following two-step procedure: 1) derive the encoder setting Γ∗(λ)and 2) derive λ∗leading to the solution Γ∗=Γ∗(λ∗). 3.2.3.1 Encoder Optimality Conditions for Fixed λ Let us assume that λis fixed. Using the definition of the distortion function we can define the objective function as a function of λsuch that L(λ) = L(Γ,Φ,Ψ,λ). In particular, we 44 Scalar Quantization under Secrecy Constraints have that L(λ) = D(Γ,Φ)−λ(D(Γ,Ψ)−∆) =E{(˜ U−U)2}−λ(E{(ˆ U−U)2}−∆) =E{(˜ U−U)2−λ(( ˆ U−U)2−∆)} = ∞ Z u=−∞ E{(˜ U−u)2−λ(( ˆ U−u)2−∆)|U=u}· pU(u)du. The quantization step is deterministic. Therefore, E{(˜ U−u)2−λ(( ˆ U−u)2−∆)|U= u}=E{(˜ U−u)2−λ(( ˆ U−u)2−∆)|Xn=xn i}. Since pU(u)is non-negative, then L(λ) is minimized if E{(˜ U−u)2−λ(( ˆ U−u)2−∆)|Xn=xn i}is also minimized, for all i∈ I. Thus, to find the optimal quantization regions and the corresponding channel code we need to find the optimal partition of uand the respective quantization indices, for all i∈ I. We will denote as B(i,λ), the optimal partition such that a source symbol uminimizes E{(˜ U−u)2−λ(( ˆ U−u)2−∆)|Xn=xn i}, if u∈ B(i,λ). Consider a pair of quantizer indices j,k∈ I with j6=kand assume that λis fixed. The region B(j,k,λ)of all u’s that should be encoded onto jrather than kis given by B(j,k,λ) = {u:E{(˜ U−u)2−λ(( ˆ U−u)2−∆)|Xn=xn j} ≤E{(˜ U−u)2−λ(( ˆ U−u)2−∆)|Xn=xn k}}.(3.13) Define εj,k,λ,δj,k,λand ϑj,k,λrespectively as εj,k,λ,E{˜ U2−λˆ U2|Xn=xn k}−E{˜ U2−λˆ U2|Xn=xn j}(3.14) δj,k,λ,E{˜ U−λˆ U|Xn=xn k}−E{˜ U−λˆ U|Xn=xn j}(3.15) ϑj,k,λ,1 2·εj,k,λ δj,k,λ .(3.16) Then, B(j,k,λ)can be found by solving the inequality 2uδj,k,λ≤εj,k,λ. As before, ϑj,k,λ represents the threshold on the source samples ufor the set associated with the pair of indices jand k. The quantization region B(j,k,λ)is given by B(j,k,λ) =              ]−∞,ϑj,k,λ], if δj,k,λ>0 [ϑj,k,λ,∞[, if δj,k,λ<0 R, if δj,k,λ=0 and εj,k,λ≥0 /0 , otherwise. Note that B(j,k,λ)is either a one-sided open interval, the real line or the empty set. Therefore, the overall quantization regions B(j,λ)can then be derived by subsequently 3.2 Scalar Quantizers under Security Constraints 45 intersecting the intervals given by B(j,k,λ)according to B(j,λ) = \ k∈I:k6=j B(j,k,λ).(3.17) Since B(j,λ)is obtained by a subsequent intersection of intervals, it will be a single interval or the empty set. In case the intersection results in a single interval, we define the lower endpoint ϑl j,λand the upper endpoint ϑu j,λsuch that B(j,λ) = [ϑl j,λ,ϑu j,λ].(3.18) It is important to point out that there might be cases where ϑl j,λ≤ϑu j,λdoes not hold. For such cases it is possible to conclude that there is actually no value of uthat should be encoded onto xn j, thus B(j,λ) = /0. The optimal quantization regions for our scalar quantizer are then given by B(j,λ) =      /0 , if ∃k:δj,k,λ=0 and εj,k,λ<0 R, if ∀kδj,k,λ=0 and εj,k,λ≥0 [ϑl j,λ,ϑu j,λ], otherwise The partition induced by B(j,λ)provides us with the optimal encoder subject to our constraints, for a particular value of λ. Thus, the optimal encoder is given as follows. Lemma 3. Let the quantization step be an injective function. For a fixed λand decoder Φ, the optimal encoder Γ∗(λ)is given by Γ∗(λ),Γ(u,λ) = xn j,u∈ B(j,λ),j=1,2,...,|XN I|,(3.19) where xn jis the j-th channel input vector. The encoder given in Lemma 3satisfies the necessary conditions for optimality for a fixed decoder and λ. To find the final quantizer design, we should solve (3.12) with some care since the value of λmay affect the configuration of the encoder. In particular, some regions of λmay result in configurations that are not possible (upper boundaries are below lower boundaries) or may be contained in some other region of λand therefore do not necessarily need to be accounted for. As noted in Section 3.2.2, it is possible to identify these changes as a function of λ, and therefore efficiently obtain the realizable quantization regions, for which the aforementioned maximization problem can be solved individually. 46 Scalar Quantization under Secrecy Constraints 3.2.3.2 Realizable Quantization Regions To simplify the problem it is possible to partition the range of λinto smaller intervals for which the encoder setup, i.e., the number of thresholds and index assignments, remains unchanged for a smaller λinterval. In particular, the quantizer arrangements can be identified as a function of λand the intervals can be computed in a structured way, by considering the ordering relationships between the index assignments (and the respective quantization regions). The following definitions and propositions aim at providing the basis for finding the λintervals in an efficient manner. Definition 13 (Well-defined Quantization Region).A quantization region B(j,λ)is welldefined if B(j,λ)is non-empty, for j∈ I. Definition 14 (Index Ordering).We say that the index j∈ I lies to the left of k∈ I if E{˜ U−λˆ U|Xn=xn j} ≤ E{˜ U−λˆ U|Xn=xn k}. We denote this relationship by j<k. Definition 15 (Quantization Region Ordering).The quantization regions B(j,λ)and B(k,λ)are ordered if B(j,λ)lies to the left of B(k,λ). Let there be an arrangement of indices in Isuch that each index j=0,1,...,|I| − 2 is left of the index kaccording to Definition 14. Additionally, let the regions B(j,λ) and B(k,λ)be well-defined according to Definition 13, i.e. B(j,λ) = [ϑl j,λ,ϑu j,λ]with ϑl j,λ≤ϑu j,λand B(k,λ) = [ϑl k,λ,ϑu k,λ]with ϑl k,λ≤ϑu k,λ. Proposition 1. If the index j ∈ I lies left of the index k ∈ I and B(j,λ),B(k,λ)are well-defined, then the quantization region B(j,λ)lies to the left of B(k,λ). Proof. If B(j,λ)and B(k,λ)are well-defined, then B(j,λ)is to the left of B(k,λ)if ϑu j,λ≤ϑl k,λ. Let l∈ I be an arbitrary index such that B(l,λ)is well-defined. To find the upper threshold ϑu j,λwe simply need to consider those indices such that l>j, i.e. the ones for which δj,l,λ>0. Hence, we have that ϑu j,λ=min l>jϑj,l,λ≤ϑj,k,λ. To find the lower threshold ϑl k,λwe simply need to consider those indices such that l<k, i.e. the ones for which δk,l,λ<0. Consequently, we have that ϑl k,λ=max l<kϑk,l,λ≥ϑk,j,λ. By definition we have that ϑj,k,λ=1 2·εj,k,λ δj,k,λ=1 2·−εj,k,λ −δj,k,λ=1 2·εk,j,λ δk,j,λ=ϑk,j,λ. From the above expressions we can see that ϑu j,λ≤ϑu j,k,λ=ϑu k,j,λ≤ϑl k,λand hence, B(j,λ)is to the left of B(k,λ). Proposition 2. If the region B(j,λ)is well-defined, index j lies to the left of index k and ϑu j,λ=ϑj,k,λfor some k ∈ {j+1,...,L−1}, then 3.2 Scalar Quantizers under Security Constraints 47 1. For all indices l ∈ {j+1,j+2,...,k−1}the regions B(l,λ)are not well-defined; 2. The region B(k,λ)is well-defined; 3. The upper endpoint of B(j,λ)corresponds to the lower endpoint of B(k,λ)and is equal to ϑj,k,λ, i.e. ϑu j,λ=ϑl k,λ=ϑj,k,λ Proof. To prove point 1) note that the indices j,kand lare ordered such that j<l< k. Consider an arbitrary index m6=ksuch that m>j. By definition ϑu j,λ=min m>jϑj,m,λ and by the proposition conditions we have that ϑu j,λ=ϑj,k,λ. This implies that ϑj,k,λ≤ ϑj,m,λfor any mand, in particular, that ϑj,k,λ≤ϑj,l,λfor l∈ {j+1,...,k−1}. Now consider an index m06=ksuch that m0≥l>j. The upper threshold ϑu l,λis such that ϑu l,λ= min m0>lϑl,m0,λ≤ϑj,k,λ=ϑu j,λ(otherwise ϑu j,λwould be ϑj,m0,λ). On the other hand, the lower threshold ϑl l,λ≥ϑu j,λsince jis to the left of land if B(l,λ)was well-defined it would be to the right of B(j,λ)(Proposition 1). Consequently, we have that ϑl l,λ≥ϑu j,λ≥ϑu l,λand we can conclude that B(l,λ)is not well-defined. To prove point 2) consider an arbitrary index m. We have that ϑu k,λ=min m>kϑk,m,λ≥min m>kϑj,m,λ≥ϑj,k,λby the same arguments as above. On the other hand, we have that ϑl k,λ=max m<kϑk,m,λ≤ϑk,j,λ=ϑj,k,λ. Hence, we have that ϑl k,λ≤ϑj,k,λ≤ϑu k,λand the region B(k,λ)is well-defined. Finally, to prove 3) consider again an arbitrary index m. We have that ϑl k,λ=max m<kϑk,m,λ≥ϑj,k,λ=ϑu j,λ. At the same time, we know from above that ϑl k,λ=max m<kϑk,m,λ≤ϑj,k,λ=ϑu j,λ, which implies that ϑl k,λ=ϑu j,λ. Propositions 1and 2allow us to identify the order of the quantization regions B(j,λ) from left to right along the real line and efficiently sort-out the regions B(j,λ)that are not well-defined. Moreover, we know that starting with a well-defined region, it is possible to derive all other well-defined regions to the right. Thus, we are able to identify the quantizer thresholds that will effectively be used in the final quantizer design. Considering the aforementioned relationships, we can now identify the ranges of λ that do not change the encoder setup, i.e. the ranges of λsuch that the ordering of indices is preserved. Assume that j<k. According to Definition 14 we have that E{˜ U−λˆ U|Xn=xn j} ≤ E{˜ U−λˆ U|Xn=xn k}. Then, with respect to λwe have λ[E{ˆ U|Xn=xn k} − E{ˆ U|Xn= xn j}]≤E{˜ U|Xn=xn k}−E{˜ U|Xn=xn j}and therefore j<kif λ≤E{˜ U|Xn=xn k}−E{˜ U|Xn=xn j} E{ˆ U|Xn=xn k}−E{ˆ U|Xn=xn j}.(3.20) 48 Scalar Quantization under Secrecy Constraints Let ηj,k=E{˜ U|Xn=xn k} − E{˜ U|Xn=xn j}and γj,k=E{ˆ U|Xn=xn k} − E{ˆ U|Xn=xn j}. The set of values of λfor which an index j∈ I lies to the left of k∈ I is then defined as Λ(j,k) =                  0,ηj,k γj,k, if γj,k>0, ηj,k γj,k,∞, if γj,k<0, R, if γj,kand ηj,k≥0 /0 , otherwise. To obtain the ranges of λthat do not change the encoder setup consider the following definition. Definition 16 (Sequence of Indices).A sequence of all indices in Iis a vector iI= (i1,i2,...,i|I|)containing each index in Iexactly once, i.e. iIis a permutation of (0,1,...,|I|− 1). Definition 17 (Ordered Sequence of Indices).A sequence of indices iIis ordered if the position of the indices in iIalso reflect the order defined in Definition 14, i.e., for all j∈ {1,...,|I|},ij<ij+1where ijand ij+1are the j-th and (j+1)-th indices in iI. Given a sequence iIof all indices in I, let the set of all λ’s for which iIis ordered be denoted as Λ(iI). Then, Λ(iI)can be derived by subsequently intersecting the intervals for which adjacent indices are ordered: Λ(iI) = |I|−1 \ j=1 Λ(ij,ij+1),(3.21) Since Λ(iI)is obtained by subsequent intersection of the intervals, we conclude that Λ(iI) is a single interval in cases where iIis ordered, or the empty set, otherwise. This provides us with the means to test if a certain sequence is ordered and, at the same time, provides us with the values of λfor which the ordering of the sequence is preserved. To solve (3.12) we need to find a set of sequences which covers the complete range of λ. Let Sdenote a set of subsequences iI. Then, Scovers the whole range of λif [ iI∈S Λ(iI) = [0,∞[.(3.22) Such a set can be found recursively by exploiting (3.21) with the method described next. Consider a single-index sequence iI=ia, with ia∈ I and a∈ {1,...,|I|−1}. Clearly, for such sequence we have that Λ(iI)=[0,∞[. Now consider the possibility of adding to the sequence iIan index ibsuch that ib∈ I\iI. Let us denote the new subsequence i0 I= (iI,ib). If Λ(i0 I) = /0 it means that this sequence is not ordered, and thus adding 3.2 Scalar Quantizers under Security Constraints 49 further indices will also result in unordered sequences. On the other hand, if Λ(i0 I)6=/0 it means that this new sequence is ordered for some value of λ. We can now repeat the process by taking iI=i0 Ias the basis for the next step. By recursively applying the procedure until all the indices have been added or we reach some unordered sequence and repeating the procedure with the initial single-index sequence to take all possible values from Iwe can obtain all the valid index arrangements for the quantization regions together with the respective values of λfor which they remain valid. Having established the realizable quantization regions it is useful to explicitly find the quantization thresholds from the ordering relationships defined above. 3.2.3.3 Quantizer Thresholds We know from the previous discussion that we can find the thresholds by comparison. Let us start by considering a well defined region B(j,λ),j∈ I. The upper endpoint of B(j,λ)takes the form of ϑj,k,λ, where j<k. All the regions that are to the left of B(j,λ) should have their respective thresholds to the left of B(j,λ). Then, we have to determine for which values of λthe following inequality holds: ϑj,k,λ≤ϑj,l,λ.(3.23) If the quantization indices are sorted according to Definition 14 such that j<k<l, equation (3.23) can be written as a quadratic inequality κλ2+τλ +υ≤0,(3.24) where κ=E{ˆ U2 2|Xn=xn k}E{ˆ U2|Xn=xn l}−E{ˆ U2 2|Xn=xn j}E{ˆ U2|Xn=xn l} −E{ˆ U2 2|Xn=xn k}E{ˆ U2|Xn=xn j}−E{ˆ U2 2|Xn=xn l}E{ˆ U2|Xn=xn k} +E{ˆ U2 2|Xn=xn j}E{ˆ U2|Xn=xn k}+E{ˆ U2 2|Xn=xn l}E{ˆ U2|Xn=xn j}, τ=E{ˆ U2 1|Xn=xn j}E{ˆ U2|Xn=xn l}+E{ˆ U2 2|Xn=xn j}E{ˆ U1|Xn=xn l} +E{ˆ U2 1|Xn=xn k}E{ˆ U2|Xn=xn j}+E{ˆ U2 2|Xn=xn k}E{ˆ U1|Xn=xn j} +E{ˆ U2 1|Xn=xn l}E{ˆ U2|Xn=xn k}+E{ˆ U2 2|Xn=xn l}E{ˆ U1|Xn=xn k} −E{ˆ U2 1|Xn=xn j}E{ˆ U2|Xn=xn k}−E{ˆ U2 2|Xn=xn j}E{ˆ U1|Xn=xn k} −E{ˆ U2 1|Xn=xn k}E{ˆ U2|Xn=xn l}−E{ˆ U2 2|Xn=xn k}E{ˆ U1|Xn=xn l} −E{ˆ U2 1|Xn=xn l}E{ˆ U2|Xn=xn j}−E{ˆ U2 2|Xn=xn l}E{ˆ U1|Xn=xn j} 56 Scalar Quantization under Secrecy Constraints Figure 3.8: SNR of legitimate receiver and eavesdropper for a scalar quantizer with secrecy constraints for the degraded scenario. The quantizer resolution is Q=3. wiretap channel (third scenario), then we start be reducing the number of levels until the eavesdroppers performance is dominated by its channel properties. That is the point at which we are able to fully use the available resolution to the advantage of the legitimate receiver. 3.4 Discussion In this chapter we considered the design of channel-optimized scalar quantizers for secure communications, by extending the work of Farvardin and Vaishampayan [39] to a system with three users comprised by a sender, a legitimate receiver and a wiretapper. To the best of our knowledge, this work represents the first approach to the design of scalar quantizers with secrecy constraints. The proposed scheme looks at the problem of designing a scalar quantizer as an optimization problem where the goal is to minimize the distortion of the legitimate receiver, subject to a lower bound on the eavesdroppers distortion. We note that the proposed strategy can be employed for other secrecy constraints of similar type. We derived the necessary conditions for a locally-optimum system and proposed a methodology for the quantizer design under an MSE criteria. Numerical results for quantizers obtained via the iterative optimization procedure assuming binary symmetric main and wiretap channels were presented. The results highlight several properties that can be obtained by our system when employed both over degraded and non-degraded channels. 3.4 Discussion 57 Figure 3.9: Number of levels of final quantizer design for the three wiretap instances when ∆= 0.3981. In particular, our design ensures SNR advantage for the legitimate parties while bounding the quality of the eavesdroppers channel when the main channel is better and ensures a leveraged SNR for both users when the channel statistics of the eavesdropper are better than those of the legitimate receiver. The problem formulation allows to fine tune the design of the scalar quantizer to specific secrecy levels, which is a useful property for many applications. Given the nature of our results, the proposed scheme may find applications within the domain of wireless sensor networks and near field communications, since these are applications where quantization is generally a requirement and the physical proximity of the communicating entities practically allows for the legitimate party to enjoy a better channel than the eavesdropper. 58 Scalar Quantization under Secrecy Constraints Chapter 4 Continuous Spherical Codes for Secrecy In the previous chapter we have seen how to design channel-optimized scalar quantizers to meet some distortion constraint on a third-party. Such construction involved creating a set of discrete points to be mapped onto discrete channel input sequences. However, it is possible to communicate discrete time continuously-valued sources without requiring source discretization. More precisely, it is possible to project the (continuous) source space onto a (continuous) lower dimensional subspace [45] or a (continuous) higher dimensional space [46]. The former mappings constitute a form of compression (or source coding), whereas the latter constitute a form of channel coding. Hence, the encoding operations can be defined through linear or non-linear functions that map source samples onto the channel space. In particular, non-linear functions project source samples onto curves defined over the channel space, providing a geometrical interpretation to the problem of communication (as will be seen in Example 2). These mappings are also known as Shannon-Kotel’nikov mappings [47]. Formally, both source and channel coding can be defined as follows. Consider a continuously-valued discrete-time memoryless source u∈R. If we wish to compress this source (dimension reduction) we may take a vector of msource samples and take the projection of this m-dimensional vector onto the channel space Rn, with n<m, using a mapping S:Rm→Rn.Scan be seen as an n-dimensional locally euclidean manifold embedded in Rm. On the other hand, if we wish to perform error control coding (dimension expansion), we may take a vector of msource samples and map it onto the channel space Rn, with n>m, using a similar mapping S:Rm→Rn, such that this mapping is injective. In both cases, we may see Sas a continuous or piecewise continuous linear or non-linear transformation between the spaces Rmand Rn, which can be realized through a parametric function. Let us introduce a simple example of a 1:2 bandwidth expansion mapping, which will be of help in determining some important characteristics of these mappings. Example 2. Suppose we wish to transmit a source uthat takes values in the interval 59 60 Continuous Spherical Codes for Secrecy Figure 4.1: Examples of 1:2 bandwidth expansion mapping. [0,1]. Since we are performing a 1:2 bandwidth expansion we are considering mapping of a one-dimensional line onto a two-dimensional square. One possible way of doing this would be a linear map of the source values such that uis mapped onto the point (u,u). This mapping is represented on the left side square of Fig. 4.1. On the other hand, we can use a non-linear mapping similar to the one on the right side square of Fig. 4.1 (this picture appears originally in [45]). In the latter case, the original line was stretch and twisted to occupy a larger portion of the channel space. Suppose that these mappings are used to communicate uover a noisy channel. For simplicity, assume that we are operating in the high-SNR regime. Then, a decoder that minimizes the Euclidean distance between the received vector and the line or curve is approximately optimal in a mean-square sense [47]. With respect to a linear mapping, the magnitude of the error vector will remain unchanged after decoding, as the mapping is simply a rotation of the source vector. With respect to the non-linear mapping, the magnitude of the error vector will change after decoding. More precisely, the magnitude of the error vector can decrease if the original error vector does not send the received vector closer to another curve fold, or increase otherwise. The increase and decrease in the error magnitude is mainly due to the need for re-scaling after decoding, which depends on how much the line is stretched. The above example is useful to illustrate the virtues and limitations of linear and nonlinear mappings. While linear mappings have a constant error profile, non-linear mappings introduce a sort of threshold where below that threshold the magnitude of error decreases and above that threshold the magnitude of error increases. Hence, the existence of these anomalous errors that induce a threshold implies that non-linear mappings have some limits as to how much they can stretch the source space. It also illustrates the two main criteria involved in the design of specific curves. On the one hand, the length of the curves should be maximized (for a given power constraint) in order to reduce the magnitude of the error vector. On the other hand, the stretching achieved by the mapping must be limited to avoid any anomalous errors (which induce a high distortion). These two constraints are at odds with each other. When compared to other strategies for communicating continuous sources such as 4.1 Torus Layer Spherical Codes For Continuous Alphabets 61 channel-optimized scalar quantizers, bandwidth expansion mappings compare favourably in terms of performance and complexity, when operating in the high-SNR regime [47]. Additionally, these techniques incur in low complexity and delay in comparison with other schemes performing error correction, while allowing control over the bandwidth expansion (or reduction). From a secrecy perspective, they allow us to take advantage of other types of code characteristics. In particular, they introduce some geometrical meaning to the process of communication which may be used from a secrecy perspective. In this chapter we will focus on a particular construction of these bandwidth expansion mapping called Piecewise Torus Layer Spherical Codes, introduced in [48] for discrete sources. In essence, these mappings are curves defined over several flat tori. They provide a basis for efficient encoding/decoding while guaranteeing a good bandwidth expansion performance. Moreover, their geometrical properties allow us to control the distances between folds, thus providing means to easily control the code’s error thresholds. In this context, we aim at designing codes guaranteeing, with high probability, that the eavesdroppers error vector will be above the noise threshold defined by the anomalous errors, described in Example 2. If one can achieve this, the distortion of the eavesdropper is bound to be small. With respect to reliability, we wish that the legitimate party operates below this error threshold, and therefore does not incur in fold errors. Thus, the proposed codes are based on finding a suitable parametrization that satisfies the reliability and secrecy constraints. Formally, we define these constraints achieving an arbitrarily small probability of anomalous errors (reliability) and an arbitrarily large probability of anomalous errors (secrecy). However, these conditions can be relaxed to allow for a specific fraction of anomalous errors. This allows us to find a balance between the distortion experienced by the legitimate receiver and the eavesdropper explicitly. 4.1 Torus Layer Spherical Codes For Continuous Alphabets Torus Layer Spherical Codes (TLSC) were recently introduced in [48] as a new class discrete spherical codes and were extended in [49] to account for continuous sources. The codes in [49] essentially perform a 1 : 2nbandwidth expansion by mapping source values u∈Ronto several curves that are defined over a flat tori contained in the unit sphere S2n−1. Fig. 4.2 serves as an informal illustration of how these codes generally operate1. The signal interval is divided into Mpartitions. Each of these partitions is then mapped onto a curve defined over a flat torus. Hence, the channel space is divided onto non-intersecting hyper-surfaces which, ideally, are densely packed. If we choose a proper distance between torus (a distance such that the probability of anomalous errors 1For an easier visualization the depicted torus is not necessarily flat, since embedding a flat torus in 3 dimensions requires repeatedly corrugating a regular torus [50]. For our purposes, it is sufficient to illustrate the construction and its properties on non-flat tori. 62 Continuous Spherical Codes for Secrecy Figure 4.2: Example of a mapping between the line [0,1]and curves over several tori. is arbitrarily small), the error of the estimates will be bounded by the size of the signal partition. A dense packing of tori implies smaller partitions and, consequently, smaller decoding errors. The considered curves are (v1,...,vn)-type knots over the torus. These knots have maximal length for a pre-defined fold distance (so it is possible to fulfil the principles previously discussed). These notions will be formalized next. 4.1.1 Flat Tori An n-dimensional flat torus Tis a closed surface defined as the Cartesian product of n circles S1in R2, where the sum of the squares of the radii of these circles sum up to one. A particular flat torus can be defined through Cartesian coordinates as follows. Let cn= (c1,...,cn)∈Rn, such that ci≥0, i=1,...,n. Then, the flat torus Tcnis the subset of points on the unit sphere Sn−1that is given by Tcn={(x1,...,x2n)∈R2n:x2 2i−1+x2 2i=c2 i,1≤i≤n}(4.1) Alternatively, we can define a flat torus through parametric equations. Consider the application Φcn:Rn→R2n, defined as Φcn(vn) = c1cos v1 c1 ,c1sin v1 c1 ,...,cncos vn cn ,cnsin vn cn,(4.2) with vn= (v1,...,vn)∈Rn. The torus Tcncan then be seen as the image by Φcn. Tcnis also the image of an injective n-dimensional hyperbox Pcn,{vn∈Rn: 0 ≤vi<2πci}.(4.3) 4.1 Torus Layer Spherical Codes For Continuous Alphabets 63 This can be seen by establishing classes of equivalence between points in Rn. In particular, two points x= (x1,...,xn)and y= (y1,...,yn)are equivalent by Φif Φ(x) = Φ(y). Consequently, for Φcn,xand yare equivalent if xi=yimod 2πci. Now note that Pcnis the fundamental parallelotope of a lattice Λgenerated by the vectors vi= 2πciei,1≤i≤n, where {ei}is the canonical basis of Rn. Then xi=yimod 2πciis equivalent to x−y∈Λ. Since, the image by Φcnis a flat torus Tcnand Φcnis well defined in the quotient Rn/Λ, the flat torus Tcnis also the image by Φcnrestricted to the hyperbox Pcn[51]. Finally, we note that Φcnis a local isometry between Rnand Tcn, implying that distances are preserved by Φcn, whenever Φcnis injective. Both representations are useful for code construction. For instance, the canonical representation of the torus by Φis useful to characterize the code’s distance properties, while the hyperbox representation is useful to design the curves over the torus. Geometrical distances will play an important role in code design, as they directly relate to the existence of anomalous errors. The following properties will be useful to our analysis. Proposition 3 ([48]).The minimum distance between two points in different flat tori Tcn and Tbnis given by dmin(Tcn,Tbn) = kcn−bnk= n ∑ i=1 (ci−bi)2!1 2 .(4.4) Proposition 4 ([48]).The distance between two points x and y in the same torus Tcnis given by d(Φcn(x),Φcn(y)) = 2 n ∑ i=1 c2 isin2xi−yi 2ci!1 2 .(4.5) Proposition 5 ([48]).Let cξ=min 1≤i≤nciand suppose that 0<||x−y|| ≤ πcξ 2. The distance in (4.5)is bounded in terms of the pre-image distance ||x−y|| by d(Φcn(x),Φcn(y)) ≥sin kx−yk 2cξ!2cξ.(4.6) Having defined flat tori and some of their properties, we will describe how these can be used to define a piecewise continuous code. 4.1.2 Piecewise Torus Layer Spherical Codes Consider a collection of flat tori T={T1,...,TM}, where each torus is defined over S2n−1 using Mnon-negative n-dimensional unit vectors cn i= (ci,1,...,ci,n), 1 ≤i≤M. These M 64 Continuous Spherical Codes for Secrecy unit vectors equivalently define a spherical code SC ⊂ Sn−1with Mnon-negative codewords cn i, 1 ≤i≤M. From herein, without loss of generality, we will consider only non-degenerate tori, i.e. tori generated by vectors whose coordinates are non-zero2. These flat tori can be used to design both discrete and continuous spherical codes. For instance, we may fill each flat tori with a suitable n-dimensional code (e.g. a lattice code) and take its image by (4.2) to obtain a spherical code in R2n[48]. The minimum distance of this discrete spherical code is given by the minimum distance between any two tori in T. A similar strategy can be used to design a piecewise continuous code, where instead of a discrete set of points, we fill each hyperbox Pcn iwith continuous curves [53,49]. A curve can be defined as follows. Let s:[a,b]→Rn,a,b∈R, be a mapping of a real valued signal uwithin the interval [a,b], onto an n-dimensional point s(u)defined over the real numbers. If sis a continuous mapping, then srepresents a curve in Rn. The stretch S(u)of sis the function k˙s(u)k, where ˙s(u)is the derivative of s(u),u∈[a,b]. The length of the curve is given by L=Rb aS(u)du. For a given point s(u)in the curve s, the Voronoi region V(u)of s(u)is the set of all points of Rnsuch that these points are closer to s(u) than any other point in the curve. We can define the small-ball radius of a curve sas the largest radius r>0 such that Br(s(u))∩H(u)⊂V(u), where Br(s(u)) is an Euclidean ball of radius rcentred at s(u)and H(u)is the hyperplane orthogonal to sat s(u). A pictorial representation of a small-ball radius would be an n-dimensional cylinder of radius rthat is placed along the curve and does not intersect itself. Hence, the small-ball radius can be seen as a measure of the minimum distance between the folds of a curve [54]. Evoking the previous insights for good bandwidth expansion mappings, a code for transmission of continuous sources should be a mapping of substantial length, capable of guaranteeing, with high probability, that curve folds are sufficiently apart as to avoid anomalous errors. For our piecewise codes, this translates onto finding a curve of maximum length on the unit sphere, such that the small ball radius is greater than a given δSB, which relates to the noise affecting the communication channel3. The encoding and decoding operations associated with a piecewise TLSC are as follows. For simplicity, assume that the support set of uis restricted to the interval [0,1]. Split the interval [0,1]into Msub-intervals Ik, 1 ≤k≤M. Each of these sub-intervals Ikis then stretched and mapped onto a curve on the i-th torus Ti. We will consider uniformly spaced intervals and equally stretched sub-intervals. These can be obtained using 2Degenerate tori can also be seen as embeddings in lower dimensional boxes, where the reduction in dimensions is equal to the number of zero coordinates [52]. 3Alternatively, one could consider mappings of a certain resolution, i.e. consider a curve of fixed length L, and try to maximize the small-ball radius for this given length. 4.1 Torus Layer Spherical Codes For Continuous Alphabets 65 a bijective function fksuch as fk:Ik→[0,1) fk(u) = u−∑k−1 j=1lj/L lk/L, where Ik=∑k−1 j=1lj L,∑k j=1lj Land L=M ∑ k=1 lk, with k=1,...,Mand where lkis the length of the curve defined over the torus Tcn k. Note that other mappings can be considered. The mapping between the stretched sub-intervals and the torus curves can be described as follows. Define ˆvn k=cn k◦vn k, where ◦represents the Hadamard product and vn k∈Rn. The full encoding map scan be defined composing f(·)and Φ(·)as sk(u):=Φcn k(fk(u)2πˆvn k),for u∈Ik.(4.7) In principle, vn kcould be any real-valued vector. However, not having a constraint could lead to knots that have multiple components, meaning a non-negligible probability of anomalous errors. We are interest in curves that form torus knots, i.e. knots that have a link with one component only. A sufficient condition for such curves is to guarantee that the elements of vn kare co-prime. This ensures that the curve defined over the torus does not have any self-intersections. The full encoding process is illustrated in Fig. 4.3 for a dimension of n=2. The upper line illustrates the partition of the signal interval, while below we show the restretched interval associated with Ik. After mapping uon the stretched (and normalized) line through fk(·), the final value for skis computed according to (4.7), by considering the application of Φcn krestricted to the chosen curve vn k. The hyperbox in the bottom of the figure illustrates an hyperbox for the torus Tkdefined by ck= (ck,1,ck,2)and the associated curve defined by vk= (vk,1,vk,2). Note that vkis a (vk,1,vk,2)torus-knot. Hence, the curve skwill turn vk,1times around the axis of rotational symmetry of the torus and vk,2times around a circle in the interior of the torus, which can be seen through the number of intersections of the image of the curve with the sides of the hyperbox. On the other hand, maximum likelihood decoding of a piecewise TLSC (in the high SNR regime) attempts at minimizing the Euclidean distance between the received point and any other point on the curves of the considered set of tori. Let the vector x= (x1,...,x2n)∈R2nbe the channel input that results from encoding uand let y= (y1,...,y2n)∈ R2nbe the received vector that is corrupted by channel noise. In particular, if the channel is an Additive White Gaussian Noise (AWGN) channel with zero mean and variance σ2, the likelihood function is defined as fˆ U|u(ˆ U|u) = 1 2πσ2n exp ky−sT(u)k 2σ2[55]. The ML 72 Continuous Spherical Codes for Secrecy (a) n=2 (b) n=24 (c) n=2 (d) n=24 (e) n=2 (f) n=24 Figure 4.7: P(knbk ≤ d/2)and P(knek>d/2)as a function of distance d, for dimensions n=2 and n=24. 4.3 Numerical Results 73 (a) σ2 m=10−3and σ2 m=10−2(b) σ2 m=10−4and σ2 m=10−3 Figure 4.8: Map of parametrizations for which there exists a solution to the reliability and secrecy constraints with n=2. the distance between folds and εthe distance between tori. Thus, it is expected that increasing αdoes not provide much impact with respect to the legitimate receivers distortion, whereas increasing εmay reduce the distortion of the eavesdropper by a considerable amount. Let us focus on the case of n=2, which is the case that does not allow a parametrization with vanishing αand ε. Fig. 4.8 draws a map of the parametrizations that allow for a solution as a function of αand εfor the first and third cases (10dB of channel SNR advantage). The red area shows the pairs where a solution is found, whereas the blue area shows the pairs where a solution is not found. We can see that an increase in the channel conditions for both users actually allows for a broader selection of parameters. The reason is that both cumulative noise distribution curves are shifted in opposite directions, which allows to cover a broader range of parameters. Table 4.1: Performance of spherical codes for the wiretap channel with n=2. CSNRE20 25 30 30 35 35 40 40 40 45 45 45 α0 0 0 0.01 0 0.09 0.01 0.1 0.3 0.1 0.25 0.5 ε0.02 0.02 0.08 0.01 0.4 0.02 0.19 0.08 0.04 0.42 0.27 0.15 δSB 0.058 0.058 0.058 0.024 0.058 0.018 0.024 0.018 0.014 0.018 0.015 0.012 δT0.131 0.073 0.061 0.034 0.059 0.019 0.025 0.019 0.015 0.019 0.016 0.013 SNRB108 85 112 59 69 58 75 57 32 40 35 31 SNRE10 13 15 16 21 18 21 20 20 26 25 24 In Table 4.1 we show the performance of spherical codes for several parametrizations of σ2 w(reflected on the channel SNR of the wiretap channel, CSNRE), as well as αand εfor a dimension of n=2. Throughout the table we fix σ2 m=10−5, i.e. a channel SNR of 50dB. The mapping strategy above is used to choose the reported parameters αand 74 Continuous Spherical Codes for Secrecy ε. For smaller value of CSNREwe see that both αand εmay take small values. On the other hand, for values of CSNREcloser to the main channel CSNR, a relaxation of ε(or α) is required. It is interesting to see how the distances δSB and δTvary according to these parameters. While for the cases of lower CSNREit is possible to obtain distances δSB and δTthat are already some distance apart, the same is not true with respect to the cases where CSNREincreases. The reason is that for such values of wiretap CSNR, the cumulative curves have a very sharp decay. Moreover, as CSNREapproximates the main channel CSNR, the cumulative noise distributions become almost complementary curves. Thus, in such cases one must increase the code’s dimensions in order to be able to exploit the distance diversity. Fig. 4.9 illustrates this point. Here we fix the main channel CSNR at 50dB and the wiretap channel CSNR at 45dB and let the dimension increase. As it increases, we see that the cumulative noise distributions have a less sharp decay. Moreover, the difference between channels becomes more noticeable, as the cumulative distributions are longer complements of each other. Under such conditions it is now possible to use α and βto provide for trade-offs that have the desired consequence of ensuring that δSB and δTare sufficiently far apart. Table 4.1 also shows that the eavesdropper’s output SNR, although increasing with the wiretap channel SNR, is constantly kept small. We note that there are two effects under play. When δSB and δTare not similar, the eavesdropper’s distortion is mostly affected by torus errors. However, when both are similar, there is also a large distortion contribution from fold errors. This can be seen in the largest values of CSNRE, where we allow a larger value of ε, but still the eavesdropper as a low output SNR. From the legitimate receiver’s perspective, we see that when δSB and δTare closer, the distortion is greatly impacted. While the fraction of torus errors for the legitimate receivers is residual, the fact that the considered values for δSB are very small impacts negatively on its distortion, especially in such low dimensions. 4.4 Discussion We have proposed the use of spherical codes based on flat tori as the foundation of a coding scheme for the Gaussian wiretap channel with continuous inputs. The scheme inherits the advantages of spherical codes: efficient encoding/decoding, good performance in the high SNR regime and bandwidth expansion. We show that a careful parametrization of these codes (which takes into account their geometrical properties) enables legitimate users to communicate under a small distortion, while forcing the eavesdropper to operate at larger distortions. Moreover, the proposed construction provides a simple mechanism to trade-off reliability with secrecy. 4.4 Discussion 75 (a) n=2 (b) n=3 (c) n=24 (d) n=48 Figure 4.9: P(knbk ≤ d/2)and P(knek>d/2)as a function of distance d, for dimensions n= 2,3,24 and 48. 76 Continuous Spherical Codes for Secrecy Chapter 5 Randomly Punctured LDPC Codes for Secrecy Rate-compatible coding [57,58,59] is an error-control strategy that allows to adapt the rate of a given code to the channel statistics. The design principle behind these codes is to use a low-rate code whenever channel conditions are not favourable and a high-rate code embedded in the low-rate code whenever channel conditions improve. Hence, ratecompatible codes use the same underlying structure regardless of channel conditions. One of the most efficient ways of implementing rate compatible codes is through puncturing. This technique consists in selecting only a subset of the encoded bits from the original codewords for transmission. The bits that are not selected are said to be punctured. Typically, the puncturing operation is deterministic in the sense that puncturing patterns are agreed upon a priori for the desired rates. However, the puncturing operation can also be stochastic, i.e. bits can be randomly punctured. The latter approach however, requires some sort of mechanism to inform the receiver of the positions of punctured bits. In the context of physical-layer security, the first secrecy strategy that used puncturing was developed in the context of the Gaussian wiretap channel [19]. The authors showed that, under belief propagation decoding, the eavesdropper will experience bit error rates (BER) close to 0.5 if its signal to noise ratio is lower than a given threshold. Consequently, the eavesdropper’s observations contained nearly i.i.d errors, and non-decodability could be ensured. With respect to secrecy metrics, [19] introduces a new secrecy metric called the security gap, which attempts at measuring the point at which decoding is successful for the legitimate receiver and fails for the eavesdropper. Then, puncturing distributions are optimized in order to reduce the security gap. The idea is that, if the security gap can be reduced to zero, then any stochastically degraded channel will be enough to ensure non-decodability. Puncturing has also been used in the context of packet erasure channels with authenticated feedback [60]. The availability of an authenticated feedback channel enables only the legitimate receiver to request retransmissions for missing packets, thus 77 78 Randomly Punctured LDPC Codes for Secrecy Enc. BEC(δ)Dec. BEC(ε)Dec. D M P Y ˜ M Zˆ M Enc. BEC(δ)Dec. BEC(ε)Dec. D M P Y ˜ M Zˆ M Figure 5.1: Wiretap model of a coding scheme that uses puncturing to obtain secrecy. Two cases are considered: to the left the puncturing pattern is public, whereas to the right the the puncturing pattern is a shared secret between the legitimate parties. limiting the opportunities of the attacker to eavesdrop on a particular packet. Secrecy is achieved by making use of a stopping-set based puncturing strategy that adds new degrees of freedom for each missing packet. Thus, the diversity of erasure patterns experienced by the legitimate receiver and the eavesdropper is sufficient to ensure secrecy, even when the eavesdropper has channel advantage. As mentioned in Section 2.5, punctured LDPC codes have also been used to design nested codes for the Gaussian wiretap channel [30] that achieve the weak secrecy capacity. The aforementioned code constructions make use of puncturing patterns (or distributions) that are agreed upon a priori. This means that puncturing is used to hide information from the eavesdropper, neglecting it as a mechanism that can be used to adapt the code to channel conditions. However, this does not mean that puncturing cannot take both roles at the same time. In this chapter, we propose a new framework for coding for the binary erasure wiretap channel (BEWC) that is based on random puncturing. Within this framework, we analyze two cases. First, we consider the case of publicly known puncturing patterns, i.e. known by the legitimate party and the eavesdropper. We then consider the case where the puncturing pattern is secret, known by the legitimate party but not by the eavesdropper. Both models are depicted in Fig. 5.1, where Mrepresents the source message, Drepresents the puncturing pattern, Prepresents the punctured output of the encoder, Yand Zthe respective main and wiretap channel outputs, and ˜ Mand ˆ Mthe respective estimates of the source message by the legitimate receiver and eavesdropper. While the coding scheme is the same in both cases, its operational interpretation is quite different with respect to the knowledge of the secret key. If a given user is aware of the puncturing pattern, then the puncturing operation can be seen as a mechanism that introduces erasures. In particular, if the encoder output bits are independently punctured with the same probability, we may model the puncturing operation as passing the outputs of the encoder through a binary erasure channel. Ergo, random puncturing with a public 5.1 Randomly Punctured LDPC codes 79 Enc. BEC(δ0)Dec. BEC(ε0)Dec. M X Y ˜ M Zˆ M Enc. BEC(δ0)Dec. BDC(γ)BEC(ε)Dec. M X Y ˜ M Zˆ MP Figure 5.2: Operational interpretation of random puncturing, when the pattern is public (top figure) or secret (bottom figure). puncturing pattern is essentially a way to introduce artificial noise in the form of erasures w.r.t. the transmitted messages. On the other hand, if a given user is not aware of the puncturing pattern, his observations of the transmitted messages will be lacking bit-level synchronization, i.e. he does not know the positions of the received bits w.r.t to the original unpunctured codeword. Again, if the encoder output bits are independently punctured with the same probability, the puncturing operation can now be modelled as passing the outputs of the encoder through a binary deletion channel [61]. Fig. 5.2 illustrates these operational models, where now Xrepresents the unpunctured encoder output, and where δ0and ε0are erasure probabilities that take into account the puncturing probability. From a security perspective, the second model is more appealing, since the equivocation associated with a deletion channel is higher than that of an erasure channel (the deletion channel can be seen as a genie-aided erasure channel). Hence, hiding the puncturing pattern from the eavesdropper would result in a better secrecy performance. However, there is an added cost associated with secretly sharing the puncturing pattern which must not be disregarded. Herein, we will consider a coding scheme that uses randomly punctured LDPC codes, which are known by their efficiency and high performance. Moreover, there are many established techniques to analyze the performance of LDPC codes over binary erasure channels, which will be useful to our analysis. 80 Randomly Punctured LDPC Codes for Secrecy v1 v2 v3 v4 v5 v6 v7 u1 u2 u3 Figure 5.3: Bipartite graph with n=7 variable nodes (represented by circles) and n−k=3 check nodes (represented by squares). 5.1 Randomly Punctured LDPC codes An LDPC ensemble [62] of length ncan be defined as an ensemble of bipartite graphs comprised of variable nodes and parity check nodes (illustrated in Fig 5.3). These bipartite graphs can be characterized by polynomial degree distributions [62] either from an edge perspective or from a node perspective. As usual, we will denote the variable node and parity check node degree distributions from an edge perspective by λ(x)and ρ(x), respectively. In particular, we define λ(x) = c ∑ l=2 λlxl−1and ρ(x) = d ∑ l=2 ρlxl−1, where λl and ρlrepresent the fraction of edges connected to variable nodes with degree land the fraction of edges connected to parity check nodes with degree land cand drepresent the maximum degree of variable and check nodes. Then, we denote an LDPC ensemble as LDPC(n,λ,ρ). Similarly, we will denote the degree distributions from a node perspective by Λ(x) (variable node) and Γ(x)(parity check node). We define Λ(x) = c ∑ l=2 Λlxland Γ(x) = d ∑ l=2 Γlxl, where Λland Γlrepresent, respectively, the fraction of variable nodes with degree land the fraction of parity check nodes with degree land cand dare defined as above. The conversion between the degree distributions from the edge perspective to the node perspective (and vice-versa) are given by the following two relations: λ(x) = Λ0(x) Λ0(1),ρ(x) = Γ0(x) Γ0(1). 5.1 Randomly Punctured LDPC codes 81 From the degree distributions it is possible to compute the design rate Rof an LDPC code. We have that R=1−Γ Λ, where Γ=d ∑ l=2 ρl land Λ=c ∑ l=2 λl l. A puncturing distribution for an LDPC code is similar to that of a code’s degree distribution. We denote such distribution by γ(x) = c ∑ l=2 γlxl−1, where γlrepresents the fraction of variable nodes of degree lthat are punctured. The resulting punctured code has a design rate R∗given by R∗=R 1−Λp Λ , where Ris the initial code rate, Λp=c ∑ l=2 γlλl l, and Λ is defined as before. As noted before, it is useful to think of the puncturing operation in terms of an erasure channel. Therefore, we will specifically consider puncturing distributions of the form γ(x) = c ∑ l=2 γxl−1, i.e. each bit is punctured independently and uniformly at random with probability γ. 5.1.1 Encoding and Decoding of LDPC Codes over Binary Erasure Channels From an encoding and decoding perspective, LDPC codes are more useful when instanced as linear codes. An (n,k)linear binary block code is a set C ⊂ Fn 2composed of 2kcodewords of length n. The encoder is a bijective map between messages of kbits and codewords of nbits, while a decoder is a surjective map between the set of all binary sequences of length nand the set C. Moreover, one of the code’s properties is that it is a subspace of Fn 2with dimension k. In particular, Cis closed under addition, i.e. the sum of any two codewords in Calso belongs to C. Encoding with linear block codes can be performed by multiplying mby a (k×n) generator matrix G, whose rows form a basis of the linear code, i.e. x=mG. It is possible to associate with Can (n−k)×nparity check matrix H, with the property that xH|=0, for any x∈ C. Then, for any sequence y∈Fn 2, it is possible to compute a quantity called syndrome which is given by s=yH|. Thus, s=0if and only if y∈ C. While decoding of a binary linear code may take many forms, these are in general related to the parity check matrix. We will describe some possible decoding techniques latter in this section. The connection between the definition of LDPC codes via degree distributions and via a linear block code formulation is almost straightforward. Consider a code C ∈ LDPC(n,λ,ρ). LDPC(n,λ,ρ)is a set of bipartite graphs that satisfy the constraints indicated by λand ρand Cis a specific instance of such bipartite graph. Each of the bipartite graphs in LDPC(n,λ,ρ)can be represented (and fully defined) in terms of the parity check matrix Hfor specific values of kand n, where kis the length of the source message and nis the desired codeword block-length n. The parity-check matrix His an (n−k)×n matrix, whose rows are associated with the check nodes of the bipartite graph and whose columns are associated with the variable nodes. Denote the set of variable nodes by denoted V= (v1,v2,...,vn), and the set of check nodes by denoted U= (u1,u2,...,un−k). Then, Hi,j=1 if and only if there is an edge between check node uiand variable node vj, 88 Randomly Punctured LDPC Codes for Secrecy For maximum a posteriori decoding, the MAP decoding threshold εMAP is defined has the largest erasure probability such that the normalized conditional entropy of the code converges to zero [64]. The general method for computing the MAP threshold of a certain ensemble uses the EXIT curves of a BP decoder. The idea is as follows. Given the BP EXIT curve take a vertical line starting at εBP pand shift it to the right. When the area under the BP curve to the left of the line is equal to the area under the BP curve to the right of the line, the abscissa of this line marks the MAP threshold, giving rise to a generalized area theorem for erasure channels [64]. While determining the MAP threshold may be complicated for many ensembles (BP EXIT curves may have many discontinuities, for certain ensembles it is possible to obtain a straightforward computation of the MAP threshold using the notion of a peeling decoder. It can be shown that the residual graph obtained by a peeling decoder is uniformly distributed conditioned on its degree profile [65] and that its degree distribution pair is sharply concentrated around its expected value [64]. More precisely, consider an LDPC ensemble (n,λ,ρ) which is used for transmission over a BEC(ε). A peeling decoder gives rise (w.h.p) to a residual ensemble (Λε,Γε) with the following distribution [64] Λε(z),εΛ(zy)(5.7) Γε(z),Γ(x+zx)−Γ(x)−zxΓ0(x),(5.8) where xis the fixed point of the density evolution equation of the BP decoder, x,1−x and y,1−ρ(1−x). The normalized equivocation is then given by the average rate of the residual ensemble [64]. Moreover, if the design rate of the residual ensemble is equal to its average rate, the normalized equivocation can be computed from this quantity. The following concentration lemma [64] provides us a way to identify which ensembles satisfy such constraint. Lemma 4 ([64], Lemma 7).Consider an LDPC ensemble (n,λ,ρ) with a design rate r,1−Λ0(1) Γ0(1). Let φ(x) = log2(1+x)and consider the function Ψ(u)defined as Ψ(u) = −Λ0(1)[φ(uv)−φ(v)]+∑ l Λlφ(ul)+(1−r)∑ l Γlφ 1−v 1+vl!−Λ(1), where v =∑ l λl 1+ul−1∑ l λlul−1 1+ul. Let G be a code picked uniformly at random from the ensemble LDPC(n,λ,ρ) with a rate rG. If Ψ(u)takes on its global maximum at u =1, for u ∈[0,∞), then there exists B>0such that, for any ξ>0and n >n0(ξ,Λ,Γ), Pr{|rG−r|>ξ} ≤ e−Bnξ. 5.1 Randomly Punctured LDPC codes 89 Thus, if the condition from Lemma 4on Ψ(u)is met for the ensemble LDPC(n,λ,ρ), with high probability, the design rate of the code will be asymptotically close to the average code rate. The following theorem provides the basis to compute the average normalized equivocation for a randomly chosen code for an ensemble LDPC(n,λ,ρ). Theorem 5 ([64], Theorem 10).Consider the LDPC ensemble (n,λ,ρ). Let G be a code picked at random from this ensemble, (Λε,Γε) be the corresponding residual ensemble with respect to the transmission over a BEC(ε) and let the conditions of Lemma 4hold for the residual ensemble. Then, lim n→∞ 1 nE[HG(X|Z)] = Λ0(1)x(1−y)−Λ0(1) Γ0(1)[1−Γ(1−x)]+εΛ(y), where Λand Γare the degree distributions of the ensemble from a node perspective, x is the fixed point of the density evolution equation of the BP decoder and y ,1−ρ(1−x). Since by definition the MAP threshold is the largest channel erasure probability such that the normalized conditional entropy of the code converges to zero, Theorem 5can be used to numerically find the code’s MAP threshold. 5.1.3 LDPC Decoding over Binary Deletion Channels with Erasures As noted in the beginning of this chapter, if the puncturing pattern is not known to the eavesdropper, the observations of the eavesdropper can be described as the outputs of a deletion channel concatenated with a binary erasure channel (recall that we are considering a binary erasure wiretap channel model). Therefore, it is useful to derive the MAP decoder associated for the eavesdropper’s estimates under this setting. This MAP decoder can be described as follows. Let x∈Xbe a randomly chosen codeword to be transmitted from a uniformly distributed source. Let also p∈Pbe the resulting sequence from puncturing xusing the puncturing pattern d= (d1,...,dn)∈Dand z∈Zbe the sequence that results from erasing the bits from pusing the erasure pattern e= (e1,...,en−nd)∈E, where nd=∑n i=1di. Assuming that bits are punctured and erased uniformly, we can derive the conditional probability P(p|x)as follows: P(p|x) = ∑ d P(p|x,d)P(d|x) =∑ d P(p|x,d)P(d). 90 Randomly Punctured LDPC Codes for Secrecy We know that P(p|x,d) =    1,if ΠD(x,d) = p 0,otherwise, with ΠD(x,d)denoting the sequence obtained by puncturing xwith the pattern d. Thus, summing over d, we can group all the puncturing patterns that originate the same p. Noting that |p|=n−nd, we can write P(p|x) = f(p,x)(1−γ)|p|γ|x|−|p|,(5.9) where f(p,x)denotes the number of times pappears as a subsequence of x. In particular, since the generation of pby puncturing of ximplies patterns that always have the same weight, we have that P(d)=(1−γ)|p|γ|x|−|p|and (5.9) follows. Then, using the fact that (X,D)→(P,E)→Zforms a Markov chain, we can write P(z|x) = ∑ p P(z|p)P(p|x) =∑ p P(z|p)f(p,x)(1−γ)|p|γ|x|−|p| Now note that for a given p, any erasure pattern generates a different sequence zwith the same size as p. Hence, we have that P(z|x) = ∑ p:|p|=|z| f(p,x)(1−γ)|p|γ|x|−|p|(1−ε)|p|−neεne,(5.10) where neis the number of erasures in z. Thus, P(z|x)can be found by computing the number of ways a subsequence pcan be generated from xand summing over all the subsequences that are compatible with zthrough erasures. Now, let xbe a randomly chosen codeword to be transmitted from a uniformly distributed source and let zbe the sequence observed by the eavesdropper after puncturing and channel erasures. The MAP estimate ˆ xof xis given by ˆ x=argmax x P(x|z) =argmax x P(z|x)P(x) P(z) =argmax x P(z|x), where P(z|x)can be computed from (5.10). signifies There are a couple of aspects to retain from the above derivation. First, the conditional probability P(z|x)depends on the number of times an erased subsequence zis compatible with a given codeword x. Unfortunately, there are no known bounds on such distribution for arbitrary lengths of x. 5.2 Puncturing for Secrecy over the BEWC 91 Thus, in principle, these have to be computed on a code basis. Hence, for the case of secret puncturing patterns, we may use a very efficient decoder at the legitimate receiver (e.g. BP decoding), while the eavesdropper’s optimal decoder will be very inefficient (counting the number of sub-sequences can be solved with polynomial complexity [66]; however this problem must be solved for every possible codeword). On the other hand, since the computation of equivocation of the eavesdropper requires this conditional probability, the same problem will be present. Consequently, an exact equivocation analysis can only be done for small block-lengths. 5.2 Puncturing for Secrecy over the BEWC Consider the wiretap models depicted Fig. 5.2. The transmitter (Alice) wishes to send a message M∈ {0,1}kto the legitimate receiver (Bob), while preventing an eavesdropper (Eve) from obtaining a correct copy of that message. To achieve this, Alice encodes Minto the codeword X∈ {0,1}nusing a code from an ensemble LDPC(n,λ,ρ). The outputs of the LDPC encoder are further punctured according to the distribution γ(x) = ∑c l=2γxl−1, where γrepresents the probability of a variable node being punctured (irrespective of its degree). Let Dbe a random variable that represents the puncturing pattern, such that D∈ {0,1}n, where a 0 in the i-th entry of vector Dmeans that the ith message bit remains unpunctured, whereas a 1 determines that the i-th message bit is punctured. Then, the channel input Pis given by taking the values of Xthat are indexed by 0-entries in D. Upon transmission of the punctured message, Bob and Eve observe (noisy) copies of P, respectively through the main channel Qmand the wiretap channel Qw. Both channels are assumed to be binary erasure channels with erasure probabilities δfor Qmand εfor Qw. Bob receives Y∈ {0,1,?}n−nd, where ”?” represents an erasure and ndis the number of punctured bits, and makes an estimate ˜ Mof the source message. Eve obtains Z∈ {0,1,?}n−nd, which she also uses to make an estimate ˆ Mof the source message. By definition, this coding scheme is deterministic (and bijective). We are interested in understanding how using this simple encoding procedure can be enough to ensure reliable and secure communication and compare it with a more sophisticated approach, such as using nested codes. In this context, we say that reliable communication is possible if the probability of error is vanishing. On the other hand, we will measure secrecy through the code’s equivocation. Note that we do not set (a priori) a particular secrecy constraint. The reason is that we are interested in measuring the secrecy associated with the coding scheme, rather than setting up an initial goal such as achieving weak secrecy capacity. That being said, our objective is to maximize the equivocation experienced by the eavesdropper (similar to a best effort approach to secrecy). 92 Randomly Punctured LDPC Codes for Secrecy With respect to the nature of the puncturing pattern (public or secret), there is a clear impact in terms of the secrecy analysis, as it is affected by the side information possessed by the eavesdropper. On the other hand, the reliability analysis is essentially the same, since in both cases the puncturing pattern is known by the legitimate party. 5.2.1 Reliability The coding scheme under consideration has a single parameter that can be adjusted, namely the puncturing probability. It is possible to obtain very simple bounds on the maximum puncturing probability, for a given code ensemble, such that it allows vanishing error probability is obtained. Moreover, for the case of LDPC codes, it is also possible to connect this puncturing probability to the type of decoder one wishes to use at the legitimate receiver through the decoding thresholds. In general, let ε∗denote the decoding threshold associated with an ensemble LDPC(n,λ,ρ). Thus, with high probability, lim n→∞Pe(Cn) = 0, if δ<ε∗, where Cnis an instance of the LDPC ensemble. When modelling random puncturing as an erasure channel, our coding scheme can be seen as using the original LDPC ensemble to transmit over a binary erasure channel charaterized by an erasure probability of δ0=γ+ (1−γ)ε. Since reliable communication is only possible if δ0<ε∗, we immediately obtain that the puncturing probability is bounded by γ≤ε∗−δ 1−δ.(5.11) In particular, for BP and MAP decoding, the thresholds can be computed according to the descriptions given in Section 5.1.2. Clearly, with increasing decoding thresholds, larger admissible puncturing probabilities are obtained. Thus, the choice of a particular decoding strategy bears an impact in terms of secrecy, since higher puncturing probabilities imply a larger equivocation with respect to the eavesdropper. This introduces a trade-off between decoding complexity and secrecy, which may be useful when designing a particular system. 5.2.2 Secrecy The secrecy performance of the proposed coding scheme will be measured in terms of the equivocation of the eavesdropper’s observations. For the considered model, it is given by the following lemma. Lemma 5. Let M,X,Z,Dbe random variables that represent respectively, the source message, the unpunctured encoded message, the eavesdropper’s observation and the 5.2 Puncturing for Secrecy over the BEWC 93 puncturing pattern. Then, H(M|Z) = H(M|X,Z)+H(X|Z,D)+H(D|Z)−H(D|X,Z)− H(X|M,Z). Proof. The proof is obtained by multiple applications of the chain rule of entropy. H(M|Z) = H(M,Z)−H(Z) =H(M,X,Z)−H(X|M,Z)−H(Z) =H(M|X,Z)+H(X,Z)−H(X|M,Z)−H(Z) =H(M|X,Z)+H(X|Z)−H(X|M,Z) =H(M|X,Z)+H(X,D|Z)−H(D|X,Z)−H(X|M,Z) =H(M|X,Z)+H(X|Z,D)+H(D|Z)−H(D|X,Z)−H(X|M,Z) =H(M|X,Z)+H(X|Z,D)+I(X;D|Z)−H(X|M,Z) The next two corollaries specify the eavesdropper’s equivocation to the case of a public or secret puncturing pattern using the proposed coding scheme, which consists of deterministic and bijective encoder. Corollary 3. Let there be a one-to-one mapping between Mand X(and vice-versa). If D is publicly known, then H(M|Z) = H(X|Z,D). Corollary 4. Let there be a one-to-one mapping between Mand X(and vice-versa). If Dis only known by the legitimate receiver, then H(M|Z) = H(X|Z,D) + H(D|Z)− H(D|X,Z). Corollary 3states that if the puncturing pattern is public, the eavesdropper’s equivocation is the equivocation associated with the transmission of codewords over a binary erasure channel with erasure probability γ+ (1−γ)ε. On the other hand, Corollary 4 states that hiding the puncture pattern from the eavesdropper results in added equivocation since H(D|Z)−H(D|X,Z) = I(D;X|Z), which is always a non-negative quantity. In particular, this term is associated with the loss of bit-level synchronization at the eavesdropper’s decoder. Both are a consequence of having H(M|X,Z) = H(X|M,Z) = 0, while for Corollary 3it is further implied that H(D|Z)and H(D|X,Z)are zero, as Dis known. As noted before, computing the equivocation of certain ensemble can be done straightforwardly, provided that the ensemble obeys certain criteria. On the other hand, computing the equivocation of a code where Dis unknown, requires the computation of conditional probabilities over that may take an exponential time to compute. This means that an exact analysis of the equivocation in this case can only be done for small block-lengths. Alternatively, it is possible to bound the equivocation of the eavesdropper by considering the connection between the MAP decoder error probability and the respective conditional 94 Randomly Punctured LDPC Codes for Secrecy entropy. While the MAP decoder itself has exponential complexity, it may be reduced with respect to the complexity of computing the equivocation. The reason is that the conditional probabilities to be computed in the MAP decoder only need to be computed over sequences of a certain length, meaning that a certain observation defines the weight of the puncturing patterns. This means that one compute the conditional probabilities with respect to these patterns, thus reducing the amount of computations that need to be performed. In [25], the authors provide expressions for bounding the equivocation using the MAP error probability. Let Pebe the expected MAP error probability and consider the two following functions Φ(Pe)and Φ∗(Pe)as given in [25] Φ(Pe) = (1−Pe)ilog2i+h(iPe−(i−1)),(5.12) and Φ∗(Pe) = aiPe−i−1 i+bi,(5.13) with i−1 i≤Pe≤i i+1,i=1,...,M−1 and where h(·)is the binary entropy function, Mis the alphabet size, ai=i(i+1)log2((i+1)/i)and bi=log2(i). Then, the equivocation of the eavesdropper is bounded according to the following: Theorem 6 ([25], Theorem 1).Let Pe(X|Z)denote the MAP error probability and H(X|Z) denote the equivocation. Then, Φ(Pe(X|Z)) ≥H(X|Z)≥Φ∗(Pe(X|Z)) (5.14) 5.2.3 Rate-Equivocation Regions While there are several ways in which the puncturing pattern can be shared among the legitimate parties (discussed in more detail in Section 5.4), it is possible to do it purely from an information-theoretic point of view. From this perspective, we need to derive the rate-equivocation regions, as our wiretap model requires some side information. This side information can be provided either by an external source3(genie-aided) or can be generated and transmitted by the legitimate receiver. The disclosure strategy and nature of the puncturing pattern may define a variant of the wiretap model, which may result in a modified rate-equivocation region. For instance, if we assume that the puncturing pattern is obtained via a genie, a model which considers a public puncturing pattern is simply the 3For instance using information-theoretic secret-key agreement schemes [3, Chapter 4]. 5.2 Puncturing for Secrecy over the BEWC 95 wiretap model we have considered so far and introduced in Section 2.1. On the other hand, if the puncturing pattern is a shared secret we are dealing with a wiretap with a shared key [67]. In the case the puncturing pattern is to be transmitted, considering a puncturing pattern public can be equivalent to have a broadcast wiretap channel with common and confidential messages (BCC) [14], where the common rate is the rate allocated to the transmission of the puncturing pattern. This would be a worst case scenario, since in practice we do not need to require that the eavesdropper decodes de puncturing pattern, and consequently the rate-equivocation region can be further extended. In the event that we assume that the puncturing pattern is to be transmitted and kept secret, we have again a simple wiretap channel where now the secret rate has to be split to account for the messages and patterns. Table 5.1: Equivalence of rate-equivocation regions as a function of the disclosure strategy and nature of the puncturing pattern. public Dsecret D genie-aided DWTC WTC-SK transmitted DBCC WTC In the following, we will consider that the puncturing pattern is obtained via a genie. Therefore, the two rate-equivocation regions of interest are the rate-equivocation regions for the wiretap channel and the wiretap channel with a shared key (a proof is provided in Appendix C). Theorem 7. ([3, Corollary 3.3]) Consider a wiretap channel (X,Y,Z, pY Z|X(y,z|x)). For any joint distribution pUVX on U × V × X that factorizes as pUpV|UpX|V, the weak rate-equivocation region for this wiretap channel is the convex set RWT =[ pUVX RWT (pUV X ),(5.15) where RWT (pUV X ) =    (R,Re): 0≤Re≤R≤1 nI(Vn;Yn) 0≤Re≤1 nI(Vn;Yn|Un)−I(Vn;Zn|Un)   . Theorem 8. Consider a wiretap channel (K,X,Y,Z, pYZ|X(y,z|x)), where Kis the key alphabet. Moreover, assume that the key has a fixed rate Rk. For any joint distribution pUVX on U ×V ×X that factorizes as pUpV|UpX|V, the weak rate-equivocation region for 96 Randomly Punctured LDPC Codes for Secrecy this wiretap channel is the convex set RSK =[ pUVX RSK(pUVX ),(5.16) where RSK(pUVX ) =    (R,Re): 0≤Re≤R≤1 nI(Vn;Yn) 0≤Re≤1 nI(Vn;Yn|Un)−I(Vn;Zn|Un)+Rk   . For noisier wiretap channel models the above regions can be simplified by taking Vn= Xnand letting Unto be independent of (Vn,Xn,Yn,Zn). It is not surprising that a shared secret extends the rate equivocation region (in the sense that the maximum equivocation of the eavesdropper saturates at a higher value), since the key-rate is given for free in this case. However, it is not clear whether there is an advantage in terms of simplifying the coding process, since coding using a secret key may be an easier task than its keyless counterpart. Note that secret-key agreement is generally considered to be easier than coding for secrecy, and thus there is no added complexity in obtaining this model to start a priori. 5.3 Numerical Results We have seen in Section 5.2.2 that the eavesdropper’s equivocation depends simply on the code’s performance over the binary erasure channel when the puncturing pattern is public. When instead we consider a secret puncturing pattern, the eavesdropper’s equivocation is further affected by the shared information between the codewords and the puncturing pattern, given the eavesdropper’s observation. Given that this is the case, a simple strategy to increase the eavesdropper’s equivocation is to consider codes that allow for a large puncturing probability, which corresponds to the creation of a wiretap channel with a high erasure probability. Note that the manageable puncturing probability is associated with the decoder being used. Let us first consider the secrecy performance of the proposed coding scheme with public puncturing patterns and then move to secret puncturing patterns. 5.3.1 Asymptotic Performance with Public Puncturing Patterns Consider the ensembles defined by the degree distribution pairs in Table 5.2, which is comprised of three irregular codes. Note that all ensembles have small rates. This is due to the fact that we wish to have a large puncturing probability and, therefore, enough 5.3 Numerical Results 97 redundancy must be added in order to account for reliability. The BP thresholds εBP and MAP thresholds εMAP are also listed in the same table. In particular, the BP thresholds of codes C2and C3are very similar, while the MAP thresholds of C1and C3are also very similar. Table 5.2: Degree distributions of LDPC code ensembles C1,C2and C3. C1C2C3 λ20.057143 - - λ30.942857 0.06383 - λ40.93617 0.067797 λ5- - 0.932203 ρ30.085714 - - ρ40.914286 - - ρ50.106383 - ρ60.893617 0.40678 ρ7- - 0.59322 R0.25 0.3333 0.25 εBP 0.6576 0.5129 0.5075 εMAP 0.7444 0.6654 0.7499 To understand how the puncturing probability affects the reliability limits of our code, we will first fix the main channel crossover probability δ. From (5.11), we may obtain the largest admissible puncturing probability as a function of the decoding threshold. Fig. 5.6 plots the largest puncturing probability γ∗as a function of the main channel erasure probability δ. There exists a symmetry between the admissible puncturing probabilities and the channel parameter. Obviously, almost noiseless channels allow for very large puncturing probabilities. Having found the admissible puncturing probabilities, we may turn our attention to the equivocation rate experienced by the eavesdropper. In particular, the ensemble average equivocation rate is given by Theorem 5whenever the required conditions hold, (which is the case for the considered codes) and can be computed through (5.9) for channel parameters above the MAP threshold (by definition the equivocation evaluates to zero bellow the MAP threshold). Figures 5.7 and 5.8 plot the normalized equivocation, as a function of the eavesdropper’s channel erasure probability ε, for a noisy main channel with erasure probability δ=0.25, for the respective puncturing probability γ∗. Fig. 5.7 illustrates that, puncturing up to the BP threshold limit, leads to a constant gap from the maximum achievable equivocation (solid black line) that is a function of the MAP threshold. Thus, if an LDPC 104 Randomly Punctured LDPC Codes for Secrecy the eavesdropper’s equivocation to near maximum equivocation. This suggests that for increasing block-lengths, one can rapidly approach the secrecy capacity of this channel model. As a further comment, it should be noted that, even considering modest blocklengths, punctured codes with a secret puncturing pattern have a performance that is not very far from its theoretical limit, considering the code construction in question is using deterministic and bijective encoders. Figure 5.12: Rate-equivocation regions of the considered models and the rate-equivocation pairs for codes C1,C2and C3for both the asymptotic and finite block-length case. Wiretap model parameters are δ=0 and ε=0.25. As noted before, it is possible to manage slightly larger block-lengths by focusing on the eavesdroppers MAP decoder. To this purpose, we recur to simulation and compute the average MAP error probability, using Theorem 6to bound the equivocation obtained by the simulated average error probability. The employed codes have block-length n= 20 and their degree distribution are defined in Table 5.4, along with the BP threshold. The considered puncturing probability is bounded by the BP decoding threshold and the transmission of 10000 codewords is considered. We considered both noiseless and noisy main channels, with the main channel erasure probabilities δ∈ {0,0.1,0.25}and varying wiretap channel erasure probabilities ε. Note that code C4is a regular code, while code C5is an irregular code. Moreover, the puncturing probability is the maximum allowed by BP decoding. Figs. 5.13 and 5.14 show the average bit error probability experienced by the eavesdropper. For this particular case, it can be seen that the irregular code is able to constantly achieve a high bit error rate, even when the channel to the eavesdropper is noiseless. On 5.4 System Aspects 105 Table 5.4: Degree distributions for the LDPC code ensembles C4, and C5. C4C5 λ20.25105 λ31 0.30938 λ40.00104 λ10 - 0.43853 ρ61 - ρ70.63676 ρ80.36324 εBP 0.4294 0.4701 the other hand, the regular code performs well, but is more affected when the main channel error probability increases, i.e. when the puncturing probability needs to be reduced. The simulated equivocation bounds are plotted in Figs. 5.15 and 5.16, the regular and irregular code, respectively. In each figure, the dashed lines represent the lower bonds on the equivocation obtained via simulation of the average error probability, while the solid lines represent the upper bounds. Each line color is associated with a particular erasure probability of the main channel. For a noiseless main channel, the bounds are tight. With increasing erasure probabilities over the main channel, the puncturing limit decreases, hence the eavesdropper’s error probability also decreases and the bounds become loose. For this particular case, even though the BP decoding thresholds are just slightly apart, the irregular code presents much tighter bounds that the regular code. In summary, it is possible to see that hiding the puncturing pattern results in a high error rate, even when the eavesdropper’s estimates are optimal. Thus, even for modest block-lengths, puncturing can provide secrecy benefits. 5.4 System Aspects In this section we discuss several questions that pertain to the assumptions behind the proposed model as well as other system aspects. 5.4.1 Sharing Secret Keys We have seen that using the puncturing pattern as a shared secret may help in increasing the eavesdropper’s equivocation, due to the lack of synchronization. However, this requires either the transmission or agreement of a secret key. In practice this can be done in several ways. First, it is possible to use cryptographic methods such as the Diffie-Hellman key agreement scheme [68]. Hence, a cross-layer approach may be taken in the system design. Of course that the derived keys do not obey any information-theoretic secrecy 106 Randomly Punctured LDPC Codes for Secrecy Figure 5.13: Simulated average bit error rate for the code C4as a function of the wiretap channel erasure probability ε, when the main channel erasure probability takes values from δ∈ {0,0.1,0.25}. Figure 5.14: Simulated average bit error rate for the code C5as a function of the wiretap channel erasure probability ε, when the main channel erasure probability takes values from δ∈ {0,0.1,0.25}. 5.4 System Aspects 107 Figure 5.15: Bounds on the equivocation of simulated error probability for the code C4as a function of the wiretap channel erasure probability ε, when the main channel erasure probability takes values from δ∈ {0,0.1,0.25}. Figure 5.16: Bounds on the equivocation of simulated error probability for the code C5as a function of the wiretap channel erasure probability ε, when the main channel erasure probability takes values from δ∈ {0,0.1,0.25}. 108 Randomly Punctured LDPC Codes for Secrecy criterion, and therefore, the equivocation of the eavesdropper could in general be less, as he may obtain some information about the puncturing pattern. Nevertheless, even in a worst case scenario where the eavesdropper obtains a perfect copy of the secret key, we have seen that puncturing can provide for maximum equivocation (if we puncture up to the MAP threshold). Thus, from a practical standpoint, using a cross-layer approach may be sufficient for secrecy purposes. On the other hand, one may use information-theoretic secret key agreement schemes [3, Chapters 3 and 4]. A possibility is to use a regular wiretap code to share this key. While apparently this would defeat the motivation for our scheme, this is not necessarily true, as the wiretap code can be used in a conservative way (meaning that we use a wiretap code assuming the quality of the wiretap channel that is very close to the quality of the main channel). Consequently, the secure rate would be small. However, if the code allows for a large enough puncturing probability, the rate required for the secret key is also small, and therefore such strategy may be sufficient. A second possibility that is more appealing is to use sequential key distillation strategies [3, Chapter 4.3], [69], either using one-way or two way communications. Unlike wiretap codes, sequential key distillation strategies do not require a better main channel, but they do require an external source. Lastly, it is also possible to use a parallel secure channel of limited rate, if such channel is available. 5.4.2 Secret Key Rates The examples used in the previous section may suggest a large key rate is always required for the scheme to be effective. Once again, this limitation is imposed in the examples due to the fact that we may only compute the eavesdropper’s equivocation for small blocklengths. In fact, in the limit of large block-lengths, one expects to find codes of very low rate and large MAP threshold, which would translate onto a reduced key rate. However, codes with very low rate require a very large block-length. In particular, the proposed scheme requires Rk=Hb(εMAP), where Hb(·)is the binary entropy function. Thus, for increasingly larger MAP thresholds (where reliability can be achieved by letting n→∞) we would need keys of very low rate. On the other hand, the puncturing operation ensures that we actually communicate at an increased rate, therefore the usage of such codes does not force us to operate with a low communication rate. 5.4.3 Comparison with the One-Time Pad Cryptosystem Consider the system depicted in Fig. 5.17, where we have a BEWC and the encoder performs one-time pad encryption. Assume that the messages are represented by an ndimensional random variable Mand chosen according to a i.i.d. uniform distribution. Let the employed key Kbe also an i.i.d. n-dimensional random variable that follows a Binomial distribution with probability γ. The transmitted message is given by X=M⊕ 5.5 Discussion 109 Encoder Decoder BEC(ε) K M X ˜ M Z Figure 5.17: Shannon Cipher System with erasures. K, where ⊕represents the modulo 2 addition operation. The normalized equivocation 1 nH(M|Z)can be upper bounded as follows: 1 nH(Mn|Zn) = 1 nH(Mn,Kn|Zn)−1 nH(Kn|Mn,Zn) =1 nH(Kn|Zn)+ 1 nH(Mn|Kn,Zn)−1 nH(Kn|Mn,Zn) ≤1 nH(Kn)+ 1 nH(Mn|Kn,Zn)−1 nH(Kn|Mn,Zn) = (1−ε)H(K)+εH(M). Since we have assumed a uniform input distribution, this expression simplifies to 1 nH(Mn|Zn) = H(K)+ε(1−H(K)). Obviously, if the wiretap channel is noiseless (ε= 0), the eavesdropper’s equivocation will amount to the key equivocation. Thus, if we have access to a truly random key we will be able to operate at secrecy capacity with a one-time pad. However, if we only have access to a very biased key, the eavesdropper’s equivocation will decrease. The same relationship is not true in our scheme. A biased key (of lower rate) will lead to an increase in equivocation, since more bits can be punctured (provided that we satisfy the reliability constraint). Moreover, if by some reason an adversary obtains the key used in the system, the eavesdropper’s equivocation will amount to the erasure probability of the wiretap channel when the one-time pad scheme is used, while in the proposed scheme the eavesdropper’s equivocation will amount the modified channel erasure probability, which is always larger than the original wiretap channel erasure probability. 5.5 Discussion In this chapter we have proposed the use of random puncturing for secrecy over the erasure wiretap channel. We have shown that, to achieve high equivocation rates using a public puncturing pattern and a bijective deterministic encoder, the legitimate user is required to use a MAP decoder and puncture bits with a probability up to the MAP threshold. If 110 Randomly Punctured LDPC Codes for Secrecy the puncturing pattern is used as a shared secret, higher secrecy rates can be achieved. If the secret key is derived using physical-layer security methods, then the equivocation rate analysis has to take this fact into account. However, this shared secret can also be derived by public key cryptographic schemes, providing a cross-layer solution to the problem of confidential data transmission. Among the benefits provided by random puncturing is an easy adaptation of the code rate to the main channel, as well as avoidance of the need for channel statistics of the eavesdropper. It also provides easy guidelines for code design, as the only requirement is to puncture up to the permitted thresholds. An interesting point is also worth noting. The use of a puncturing pattern as a shared secret essentially creates a wiretap channel model that is fundamentally different from the main channel. This difference implies that the optimal source distribution with respect to the main channel (which is the one used in practice), may not be optimal for the wiretap channel (for instance, the uniform distribution is not the optimal input distribution for the deletion [61]). This can be seen as a further advantage in using such schemes. Chapter 6 Conclusions Under the paradigm of physical-layer security, we develop several coding schemes to provide for confidential data transmission. The focus is essentially mostly on practical code constructions. Our work differs from other works in this field in several ways. First, we explicitly design codes for finite block-lengths, which contrasts with the traditional asymptotic code designs. Second, we provide code constructions for continuous sources. Hence, our work does not inherit the assumptions required for separation theorems to hold. Third, we consider deterministic code constructions, thus circumventing the need for wiretap channel state information, as well as the need to optimize the use of local randomness. These differences also translate onto several limitations that can be assigned to our code constructions. The greatest perhaps is that, in general, our coding schemes do not achieve the fundamental limits of secrecy. On the other hand, their performance depends on the chosen block-length. In particular, for very small block-lengths, we have shown a relaxation is generally required, with respect to the reliability and secrecy criteria. In summary, our main contributions can be stated as follows. In Chapters 3and 4 we addressed code designs for continuous sources. In the former, a joint-source channel code is proposed which hinders the eavesdropper by forcing him to operate at a desired distortion level. This is accomplished by solving an optimization problem over the code parameters which constitutes in finding the scalar quantizer boundaries as well as the corresponding channel code that satisfies the aforementioned secrecy constraint. In the latter chapter, we use a particular instance of bandwidth expansion mappings which allows us to enforce anomalous errors for the eavesdropper, resulting in a large distortion. In particular, the code is parametrized based on its geometrical properties to ensure this constraint is satisfied. As a further advantage, these codes allow for very efficient encoding and decoding schemes. Chapter 5proposes the use of random puncturing in order to create a wiretap channel of very poor quality to the eavesdropper, ensuring that his equivocation is highly increased. Using the insight that the loss of bit-level synchronization generally creates a channel with reduced capacity, we propose the use of the puncturing pattern as 111 112 Conclusions a shared secret, showing that, in such scenarios, the eavesdropper is bound to have a high equivocation, even for very small block-lengths. 6.1 Future Research The coding schemes and the general framework under which these schemes are treated can be extended in multiple ways. •Nested Code Constructions: While we avoid the use of nested code constructions to circumvent the issues of the lack of wiretap channel state information, this is not necessarily true in all cases. Therefore, there it could be interesting to extend these code constructions to use nested structures. While this has been largely done in the context of codes for discrete sources (see e.g.Chapter 2), the design of continues nested codes is practically non-existent. For instance, the code construction in Chapter 3can be extended to the use of multiple scalar quantizers, each one with non-overlapping channel codes and optimized boundaries. The code construction in Chapter 4could be extended to account for a multiple correspondence between source intervals and tori or source intervals and parallel curves over a given torus. •Secrecy from the absence of synchronization: In Chapter 5we have studied the secrecy performance of LDPC codes when the puncturing pattern was a shared secret. Consequently, this strategy induced a wiretap channel with deletions. Little is known with respect to the deletion channel. Thus, advances in the understanding of this channel model could benefit a more fundamental understanding of the performance of the secrecy codes proposed here. In particular, it could interesting to understand if it is possible to induce a deletion channel of zero capacity using this channel model, which essentially would mean that there is no leakage to the eavesdropper, possibly paving the way to the design of strong secrecy achieving schemes. On the other hand, it would be interesting to understand if expurgating some codewords of the randomly punctured ensemble could be useful from a secrecy perspective. •Fundamental Limits of Secure Communication over the Finite Block-length Regime: In this thesis we avoided the formalization of these fundamental limits. In this regime one inevitably needs to assume non-vanishing error probability for the legitimate party. We have placed these assumptions heuristically, but analysed the performance of our constructions with respect to the fundamental limits in the asymptotic regime. However, this comparison is not necessarily fair. Hence, there is a need to establish the fundamental limits of secure communication under the finite block-length regime. The recent works of Yury Polyanskiy, Vincent Poor and Sergio 6.1 Future Research 113 Verdú [70] have addressed this problem in the context of communications without secrecy requirements, and perhaps can be used to formalize the fundamental limits of secure communication under the finite block-length regime. •Cross-Layer Security: The codes proposed in this thesis have the general goal of inducing a high distortion or high equivocation to the eavesdropper, with a focus on partial secrecy. In this context, the proposed schemes may be very useful with respect to a cross-layer implementation of secrecy. However, there is a need to formalize/understand how cryptanalysis is actually impacted by the errors at the lower layers. In this context, the work of Harrison [16] may be seen as a starting point for an information-theoretic perspective on the impact of errors achieved by physical-layer security with respect to cryptanalysis techniques. 120 Basic Notions on Information Theory Appendix B Leakage Bound for Wiretap Codes We wish to show that I(M;Zn)≤nCe−H(M0)+H(M0|MZn). Proof. Let (M,M0)→Xn→Znform a Markov chain and Mand M0be independent. We know that I(MM0;Zn|Xn) = 0 (see [73, Eq. 6.86]), which implies that I(M;Zn|Xn) = 0 and I(M0;Zn|Xn) = 0. I(MM0;Zn|Xn) = H(MM0|Xn)−H(MM0|XnZn) (a) =H(M|Xn)+H(M0|Xn)−[H(M|XnZn)+H(M0|XnZn)] =H(M|Xn)−H(M|XnZn)+H(M0|Xn)−H(M0|MXnZn) =I(M;Zn|Xn)+I(M0;Zn|Xn), where (a) follows from the independence of Mand M0. Since we have that I(M;Zn|Xn)≥ 0, I(M0;Zn|Xn)≥0 and I(MM0;Zn|Xn) = I(M;Zn|Xn) + I(M0;Zn|Xn) = 0, it must be that I(M;Zn|Xn) = 0 and I(M0;Zn|Xn) = 0. Additionally, we have that H(Xn|M) = H(M0|M) = H(M0)and H(Xn|MZn) = H(M0|MZn). The first equality can be easily seen from the fact that H(Xn|M) = H(M0|M)−H(M0|XnM)+H(Xn|M0M) = H(M0|M) = H(M0), where in the second equality we use the fact H(M0|XnM) = H(Xn|M0M) = 0 since two of the random variables completely determine the third and the last equality follows from the independence between Mand M0. The proof of the second equality follows from the same principles. Finally we have that 121 122 Leakage Bound for Wiretap Codes 1 nI(Xn;Zn) = 1 nI(Zn;XnM)−I(Xn;Zn|M) =1 nI(Zn;Xn)+I(M;Zn|Xn)−I(Xn;Zn|M) =1 nI(Zn;Xn)−H(Xn|M)+H(Xn|MZn) =1 nI(Zn;Xn)−H(M0)+H(M0|MZn) ≤1 nnCe−H(M0) +H(M0|MZn). Appendix C Achievable Rate-Equivocation Region for the Wiretap Channel With a Shared Key A derivation of the secrecy capacity of the wiretap channel model with a shared key is given in [74]. However, in [74], the rate-equivocation region is not explicitly established. While it is straightforward to obtain the rate-equivocation region from [74], we provide a simplified proof of the achievability, that does not require a separate analysis based on the key rate. For the converse, we re-direct the reader to [74]. We wish to prove the existence of (2nR,n)codes {Cn}n≥1, such that limn→∞Pe(Cn)≤δε(n)and limn→∞1 nI(M;Zn)≤ δε(n), where δε(n)represents a function of εand nsuch that limn→∞δε(n) = 0. Proof. Let there be three message sets, M,Mkand Md, where M∈[1,2nR],Mk∈[1,2nRk] and Md∈[1,2nRd]. In particular, Mrepresents the set of messages for transmission, the Mk the set of possible keys and Mda set of dummy messages used to randomize the encoder. Consider the following random code construction. First, generate codewords un(mk), for m∈[1,2nRk]by generating symbols ui(mk), with i∈[1,n]and m∈[1,2nRk]independently according to pU(u). Then, for every generated un(mk), generate codewords xn(m,mk,md), for m∈[1,2nR],md∈[1,2nRd], by generating symbols xi(m,mk,md)with i∈[1,n],m∈[1,2nR],md∈[1,2nRd]independently according to pX|U=ui(mk). The encoding procedure is as follows. Given m,mkand mdthe sender transmits xn(m,mk,md). The considered decoder is essentially a typical set decoder, which can be described as follows. 1. Given ynand mkthe legitimate receiver outputs ( ˜m, ˜md) if it is the unique tuple such that (un(mk),xn(˜m,mk,˜md),yn)∈Tn ε(UXY). 2. Given zn,mkand m, the virtual receiver outputs ˆmdif it is the unique message such that (un(mk),xn(m,mk,ˆmd),zn)∈Tn ε(UXZ). 123 124 Achievable Rate-Equivocation Region for the Wiretap Channel With a Shared Key Let us now analyze the error probability of this random code construction. We have that E[Pe(Cn)] = ECnP[( ˜ M,˜ Md)6= (M,Md)or ˆ Md6=Md|Cn (a) =ECnP[( ˜ M,˜ Md)6= (M,Md)or ˆ Md6=Md|M=1,Md=1,K=1,Cn], where (a) follows from the symmetry of the random-coding construction. Therefore, without loss of generality, we can assume that M=1, Mk=1 and Md=1. Define the two following events: 1. Ei j = (un(1),xn(i,1,j),yn)∈Tn ε(UXY) 2. Fj= (un(1),xn(1,1,j),zn)∈Tn ε(UXZ) We can write E[Pe(Cn)] as a function of Ei j and Fjas follows: E[Pe(Cn)] = P Ec 11 ∪[ (i,j)6=(1,1) Ei j ∪Fc 1∪[ j6=1 Fj  ≤P[Ec 11]+ ∑ (i,j)6=(1,1) PEi j+P[Fc 1]+ ∑ j6=1 PFj By the AEP we know that PEc 11≤δε(n)and PFc 1≤δε(n). Additionally, we have that for (i,j)6= (1,1),xn(i,1,j)is conditionally independent of yngiven un(1)and for j6=1, xn(1,1,j)is is conditionally independent of zngiven un(1). Therefore, we have that PEi j≤2−n(I(X;Y|U)−δε(n)) and PFj≤2−n(I(X;Z|U)−δε(n)). Consequently, we have that E[Pe(Cn)] ≤δε(n)+2n(R+Rd)2−n(I(X;Y|U)−δε(n)) +δε(n)+2nRd2n(I(X;Z|U)−δε(n)) =δε(n)+2n(R+Rd−I(X;Y|U)+δε(n)) +2n(Rd−I(X;Z|U)+δε(n)). Thus, a sufficient condition for having E[Pe(Cn)] ≤δε(n)is to choose Rand Rdsuch that    R+Rd≤I(X;Y|U)−δε(n) Rd≤I(X;Z|U)−δε(n). Achievable Rate-Equivocation Region for the Wiretap Channel With a Shared Key 125 With respect to the leakage, it can be upper bounded as follows. 126 Achievable Rate-Equivocation Region for the Wiretap Channel With a Shared Key 1 nI(M;Zn)≤1 nI(M;ZnMk) =1 nI(MXn;ZnMk)−I(Xn;ZnMk|M) =1 nI(Xn;ZnMk)+I(M;ZnMk|Xn)−I(Xn;ZnMk|M) =1 nI(Xn;Mk)+I(Xn;Zn|Mk)+ I(M;ZnMk|Xn)−I(Xn;ZnMk|M) =1 nI(Xn;Mk)+I(Xn;Zn|Mk)+ I(M;Zn|Xn)+I(M;Mk|XnZn)−I(Xn;ZnMk|M) (a) =1 nI(Xn;Zn|Un)+I(Xn;Mk)+I(M;Zn|Xn)+I(M;Mk|XnZn)−I(Xn;ZnMk|M) =1 nI(Xn;Zn|Un)+I(Xn;Mk)+I(M;Zn|Xn)+I(M;Mk|XnZn)−I(Xn;Zn|M) −I(Xn;Mk|MZn) =1 nI(Xn;Zn|Un)+H(Xn)−H(Xn|Mk)+H(M|Xn)−H(Zn|MXn)+H(M|XnZn) −H(Mk|MXnZn)−H(Xn|M)+H(Zn|MXn)−H(Xn|MZn)+ H(Mk|MXnZn) =1 nI(Xn;Zn|Un)+H(Xn)−H(Xn|Mk)+H(M|Xn)+H(M|XnZn)−H(Xn|M) −H(Xn|MZn) ≤1 nI(Xn;Zn|Un)−H(Xn|Mk)−H(Xn|M)+H(Xn)+H(M|Xn)+ H(M|XnZn) −H(Xn|MZn) ≤1 nI(Xn;Zn|Un)−H(Xn|Mk)−H(Xn|M)+H(Xn|MZn)+H(M|Xn) +H(M|XnZn)−H(Xn|MZn) ≤1 nI(Xn;Zn|Un)−H(Xn|Mk)−H(Xn|M) ≤1 nI(Xn;Zn|Un)−H(Xn|MMk)−H(Xn|MMd) =1 nI(Xn;Zn|Un)−H(Md)−H(Mk) (b) =1 nI(Xn;Zn|Un)−Rd−Rk, ≤I(X;Z|U)−Rd−Rk, Achievable Rate-Equivocation Region for the Wiretap Channel With a Shared Key 127 where (a) comes from the fact that there is a one-to-one mapping between Mkand Unand (b) comes from the code construction. Let us choose Rd=I(X;Z|U)−Rk−δε(n)and R=I(X;Y|U)−I(X;Z|U)+ Rk. Then, we have that 1 nI(M;Zn)≤I(X;Z|U)−Rd−Rk= I(X;Z|U)−I(X;Z|U) + Rk+δε(n)−Rk≤δε(n)and thus, the secrecy constrain holds. At the same time, we have that R+Rd=I(X;Y|U)−I(X;Z|U)+Rk+I(X;Z|U)−Rk− δε(n) = I(X;Y|U)−δε(n)and Rd=I(X;Z|U)−Rk−δε(n)≤I(X;Z|U)−δε(n), thus satisfying the reliability conditions. 128 Achievable Rate-Equivocation Region for the Wiretap Channel With a Shared Key References [1] D. Kahn. The Codebreakers: The Story of Secret Writing. Macmillan Publishing Co., 1967. [2] Alfred J. Menezes, Scott A. Vanstone, and Paul C. Van Oorschot. Handbook of Applied Cryptography. CRC Press, Inc., Boca Raton, FL, USA, 1st edition, 1996. [3] Matthieu Bloch and João Barros. Physical-Layer Security: From Information Theory to Security Engineering. Cambridge University Press, 2011. [4] William Stallings. Cryptography and Network Security. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 4th edition, 2005. [5] Oded Goldreich. The Foundations of Cryptography - Volume 1, Basic Techniques. Cambridge University Press, 2001. [6] R.L. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21:120–126, February 1978. [7] Taher El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In Proceedings of CRYPTO 84 on Advances in Cryptology, pages 10–18, 1985. [8] Bruce Schneier. Applied Cryptography. John Wiley & Sons, 1996. [9] Claude E Shannon. Communication theory of secrecy systems. Bell Systems Technical Journal, 28(4):656–715, 1949. [10] Serge Vaudenay. A classical introduction to cryptography: Applications for communications security. Springer-Verlag New York Incorporated, 2005. [11] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, October 1997. [12] Dan Boneh, Ron Rivest, Adi Shamir, and Len Adleman. Twenty years of attacks on the RSA cryptosystem. Notices of the American Mathematical Society, 46(2):203– 213, 1999. [13] A. D. Wyner. The Wiretap Channel. Bell Systems Technical Journal, 54:1355–1387, October 1975. 129