Polar coding for the wiretap broadcast channel

Abstract

In the next era of communications, where heterogeneous, asynchronous and ultra-low latency networks are drawn on the horizon, classical cryptography might be inadequate due to the excessive cost of maintaining a public-key infrastructure and the high computational capacity required in the devices. Moreover, it is becoming increasingly difficult to guarantee that the computational capacity of adversaries would not be able to break the cryptograms. Consequently, information-theoretic security might play an important role in the future development of these systems. The notion of secrecy in this case does not rely on any assumption of the computational power of eavesdroppers, and is based instead on guaranteeing statistical independence between the information message and the observed cryptogram. This is possible by constructing channel codes that exploit the noisy behavior of the channels involved in the communication.

Although there has been very substantial research in the last two decades regarding information-theoretic security, little has gone to study and design practical codes for keyless secret communication. In recent years, polar codes have changed the lay of the land because they are the first constructive and provable channel codes that are able to provide reliability and information-theoretic secrecy simultaneously. Additionally, their explicit construction and the low complexity of the encoding/decoding schemes makes them suitable for the new generation of communication systems.

The main objective of this dissertation is to provide polar coding schemes that achieve the best known inner-bounds on the capacity regions of different multiuser models over the discrete memoryless broadcast channel. These models not only impose a reliability constraint, but also some sort of information-theoretic secrecy condition in the presence of eavesdroppers. In general, we focus on describing the construction and the encoding/decoding schemes of the the proposed polar code for a particular setting. Then, we analyze the reliability and the secrecy performance of these schemes in order to prove that they are able to achieve these inner-bounds as the blocklength tends to infinity.

The first part of the thesis drives the attention to two different models over the degraded broadcast channel that commonly appear in real communication systems. In this models, there are a set of legitimate receivers and a set of eavesdroppers that can be ordered based on the quality of their channels. According to this ordering, different reliability or secrecy constraints apply for each legitimate receiver or eavesdropper respectively. Moreover, we propose practical methods for constructing the polar codes for both models and analyze the performance of the coding schemes by means of simulations. Despite we only evaluate the construction for these two particular settings, the proposed methods are also suitable for any polar coding scheme that must satisfy some reliability and secrecy conditions simultaneously.

In the second part of the dissertation we describe and analyze two different polar coding schemes for the general broadcast channel (where channels are not necessarily degraded) with two legitimate receivers and one eavesdropper. We consider a model where a confidential and a non-confidential message must be reliably decoded by both legitimate receivers in presence of an eavesdropper. Despite it is almost immediate to find an inner-bound on the capacity for this model using random coding arguments, how to secretly convey the same confidential message to both legitimate receivers using polar codes is not straightforward. We also analyze the setting where a transmitter wants to send different confidential and non-confidential messages to the corresponding legitimate receivers. We compare two inner-bounds on the capacity of this model, and we design a polar coding scheme that achieves the inner-bound that surely includes the other.

La criptografia clàssica o computacional pot suposar certs inconvenients en els sistemes de comunicació de nova generació que es basen en xarxes heterogènies, asíncrones i que requereixen baixa latència. Els motius principals són l'alt cost que suposa mantenir una infraestructura de clau pública i l'elevada capacitat computacional que requereix als dispositius electrònics. A més, cada cop és més difícil garantir que aquesta capacitat computacional dels dispositius adversaris no serà suficient per trencar els criptogrames. Per tant, la seguretat basada en la teoria de la informació pot tenir un rol molt important pel futur desenvolupament d'aquests sistemes. La noció de seguretat en aquest cas no es basa en cap suposició sobre la potència computacional dels adversaris, sinó que consisteix en garantir que el missatge que es vol transmetre i el criptograma enviat pel canal siguin independents estadísticament. Això és possible utilitzant una codificació que aprofita el comportament sorollós del canal involucrat en la comunicació. Malgrat durant les dues darreres dècades la recerca en el camp de la seguretat basada en la teoria de la informació ha estat important, s'han destinat pocs esforços al disseny de codis pràctics per tal de transmetre informació confidencial sense utilitzar claus secretes. Així i tot, en els últims anys, els codis polars, un tipus de codis bloc lineals, han demostrat ser molt útils per tal de transmetre informació sense errors i de forma confidencial des d'un punt de vista de la teoria de la informació. L'objectiu principal d'aquesta tesis és construir esquemes de codificació basats en codis polars que assoleixin la capacitat (o la millor aproximació coneguda) per diferents models sobre el canal de difusió (broadcast channel) amb presència d'adversaris. Aquests models no només imposen restriccions sobre la fiabilitat de la transmissió, sinó que també imposen restriccions sobre la confidencialitat des del punt de vista de la teoria de la informació. En general, per a cada model descriurem un esquema de codificació i després analitzarem el seu rendiment per demostrar que són capaços de transmetre informació de forma fiable i confidencial a la màxima taxa de transmissió possible quan la longitud del codi tendeix a infinit. La primera part d'aquesta tesis centra l'atenció en dos models de comunicació diferents pel canal degradat de difusió que representen molts de sistemes de comunicació reals. En aquests models, hi ha un conjunt de receptors legítims i un conjunt d'adversaris, i els canals de tots ells es poden ordenar en base a la seva qualitat. En base a aquest ordre, s'apliquen condicions de fiabilitat i de seguretat diferents per a cada receptor o adversari, respectivament. També, en aquesta part proposem mètodes pràctics de construcció dels codis polars i analitzem el seu rendiment mitjançant simulacions. Malgrat que només avaluem la construcció per aquests dos models particulars, els mètodes proposats es poden generalitzar per qualsevol esquema de codificació polar que hagi de satisfer condicions de fiabilitat i seguretat de forma simultània. En la segona part es descriuen i s'analitzen dos esquemes de codificació basats en codis polars pel canal de difusió general (on els canals individuals no necessàriament són degradats) compost per dos usuaris legítims i un adversari. Primer, considerem un model en què dos missatges s'han de transmetre de forma fiable als dos receptors de manera que un ha de ser confidencial davant la presència de l'adversari. En segon lloc, considerem un model on el transmissor vol enviar diferents missatges confidencials i no confidencials als dos receptors.