Introduction
This project aims at studying security in wireless communications from
an information theoretical point of view. Information theoretical security contrasts with
computational security, which relies on computational assumptions on the adversary, typically
that the adversary does not have enough computational power to break a problem thought hard.
Information theoretical security is unconditional and relies on the uncertainty that the
adversary faces. In the context of communication systems, it is often obtained by exploiting
the noise inherently present over communication channels, and eventually amplifying it by
a careful coding strategy that further injects random bits. This idea stems from the seminal
work of Wyner and the introduction of the wiretap channel, a broadcast channel where a legitimate
player Alice communicates to two users, a legimitate user Bob, and an eavesdropper Eve.
By exploiting the difference in channels between the two users, Wyner showed that it is possible
to communicate confidentially to Bob over discrete memoryless channels, that is, there exist
codes, namely wiretap codes, that allow both reliable and confidential communications.
One of the goals of this project is to look for wiretap codes for different classes of channels,
and in particular wireless channels such as fading or MIMO channels. A dual class of problems
consists of using wiretap codes, or other techniques from coding theory, to help in achieving
cryptographic protocols over noisy channels.
We have built a USRP testbed to experiment the theory that we have developed around wiretap codes, more details of experiments are available on the testbed webpage .
We have built a USRP testbed to experiment the theory that we have developed around wiretap codes, more details of experiments are available on the testbed webpage .
Wiretap Codes for the Gaussian Channel
We consider a Gaussian wiretap channel, where Alice communicates with Bob over a Gaussian channel,
and similarly Eve can eavesdrop communication over a Gaussian channel. We analyze the probability
of Eve being able to correctly decode the message intended to Bob when Alice transmits information using
as strategy coset lattice encoding ([C2]), namely two lattices are used: a fine lattice to communicate
with Bob (a regular lattice code for Gaussian channels), and a coarse lattice encoding random bits to confuse
the eavesdropper. It is shown that confusion at the eavesdropper can be increased by a careful coding, which is
characterized by the notion of secrecy gain. Secrecy gain is a new lattice invariant related to the theta
series of the coarse lattice intended for Eve.
In [J4], we study the secrecy gain for even unimodular lattices: in particular, the secrecy gain of extremal even unimodular lattices is computed, and asymptotic bounds on the secrecy gain are given. Finally, examples of code constructions are worked out. The case of odd unimodular lattices is studied in [C6], and in fact, all the unimodular lattices in dimension less than 23 are classified with respect to their secrecy gain in [J5]. Unimodular lattices in higher dimensions are investigated in [C8], using the duality between self-dual codes and unimodular lattices. Motivated by the need to encode and decode unimodular lattices, their connection with codes via Constructions A, A' and D are revisited in [C10] and [J8].
Examples of even 2- and 3-modular lattices are considered in [C7], and a more general study of 2- and 3- modular lattices, including odd 2-modular lattices is available in [J7], which shows that in small dimensions (less than 24), there exist 2- and 3- modular lattices with higher secrecy gain than the best unimodular lattices in the same dimension. In an attempt to understand how the lattice level influences the secrecy gain, [C19] looks at the construction and secrecy gain of 5- modular lattices, but no general behavior can be seen from the proposed lattice codes.
In [J4], we study the secrecy gain for even unimodular lattices: in particular, the secrecy gain of extremal even unimodular lattices is computed, and asymptotic bounds on the secrecy gain are given. Finally, examples of code constructions are worked out. The case of odd unimodular lattices is studied in [C6], and in fact, all the unimodular lattices in dimension less than 23 are classified with respect to their secrecy gain in [J5]. Unimodular lattices in higher dimensions are investigated in [C8], using the duality between self-dual codes and unimodular lattices. Motivated by the need to encode and decode unimodular lattices, their connection with codes via Constructions A, A' and D are revisited in [C10] and [J8].
Examples of even 2- and 3-modular lattices are considered in [C7], and a more general study of 2- and 3- modular lattices, including odd 2-modular lattices is available in [J7], which shows that in small dimensions (less than 24), there exist 2- and 3- modular lattices with higher secrecy gain than the best unimodular lattices in the same dimension. In an attempt to understand how the lattice level influences the secrecy gain, [C19] looks at the construction and secrecy gain of 5- modular lattices, but no general behavior can be seen from the proposed lattice codes.
Wiretap Codes for Fading Channels
We consider a wireless wiretap channel, where all the players (Alice, Bob and the eavesdropper Eve) are equipped with one antenna, corresponding to fast fading and block fading channels. In [C3], we propose a code design criterion to design wiretap lattice codes for fading channels, this design is made available for finite signal constellations in [J9].
In [C11] and [J9], we consider wiretap lattices built over number fields for fast fading channels, and study some of the trade-offs involved in terms of choosing the right number field to help getting both reliability and confidentiality: more precisely, the role of elements of small norms is looked at in [J9], while that of the lattice volume and underlying regulator is analyzed in [C15]. In [C12] and [J10], motivated by the need to perform coset encoding with algebraic lattices, we study generalizations of Construction A over number fields.
MIMO wiretap codes are used when all players are equipped with multiple antennas (transmit antennas for Alice, and receive antennas for Bob and Eve). We analyze the probability of Eve being able to correctly decode the message intended to Bob when Alice transmits information using as strategy coset lattice encoding ([J6]). The particular case of the Alamouti code is detailed carefully. Howerer here again wiretap coding relies on coset coding and thus we look at ways of implementing Construction A in an algebra setting in [C14] and [C17].
MIMO wiretap codes are used when all players are equipped with multiple antennas (transmit antennas for Alice, and receive antennas for Bob and Eve). We analyze the probability of Eve being able to correctly decode the message intended to Bob when Alice transmits information using as strategy coset lattice encoding ([J6]). The particular case of the Alamouti code is detailed carefully. Howerer here again wiretap coding relies on coset coding and thus we look at ways of implementing Construction A in an algebra setting in [C14] and [C17].
Wiretap Codes for Network Coding
It is known from the work of Silva et al. that rank metric codes can be used as wiretap tap codes for
network coding. It is also known that generalized Hamming weights characterize the performance of wiretap codes of type II.
In [C9], we introduce a definition of generalized rank weights, motivated by the security provided by rank
metric codes for network coding. In [C13], generalized rank weights of the dual codes are considered, where they are shown to interlace the rank weights of the code, similarly as for the case of the Hamming weights. The rank hierarchy of cyclic codes is studied in [C18].
Enhanced Security of Systems using the Encoding-Encryption Paradigm
It is standard for communication systems that use both error-correction coding
for reliability and encryption for security to first perform the encryption, and
only then the encoding. In this project, we focus on those systems which adopted
the reverse approach, namely they first encode the data and then encrypt it, which
is referred to as the encoding-encryption paradigm . A motivating example
is the standard for Global Telephony GSM. In this project, we study how the security of systems such as GSM could be enhanced by using wiretap coding. More
precisely, since systems using the encoding-encryption paradigm rely their security on a stream cipher, we are interested in protecting the stream cipher key against
both passive and active attacks. To do so, we introduce a wiretap encoder which
injects extra randomness in the system, and study the security it provides.
We first consider an information theoretical analysis, which focuses on the equivocation of the key, and show that under chosen plaintext attacks ([C1]), even when the adversary can add some controled noise and learn the resulting effect on the legitimate user's decoding ([J2]), the addition of the wiretap encoder provides an unconditional security as long as the adversary does not collect too many samples, after which, the unconditional security is lost. The fact that the adversary can recover the key with a very high probability however does not mean that it is easy to do so, it only tells that a computational security analysis is needed.
We show in ([J3]) that the computational security of systems using the encoding-encryption paradigm enhanced with a wiretap encoder is related to the difficutly of sovling the LPN (Learning Parity in Noise) problem. Furthermore, the complexity of the LPN problem can be increased by a careful design of the wiretap encoder. We thus propose code design criteria for designing wiretap codes that maximize the security of the system, both from an unconditional and computational point of view, and give a corresponding generic code construction.
We first consider an information theoretical analysis, which focuses on the equivocation of the key, and show that under chosen plaintext attacks ([C1]), even when the adversary can add some controled noise and learn the resulting effect on the legitimate user's decoding ([J2]), the addition of the wiretap encoder provides an unconditional security as long as the adversary does not collect too many samples, after which, the unconditional security is lost. The fact that the adversary can recover the key with a very high probability however does not mean that it is easy to do so, it only tells that a computational security analysis is needed.
We show in ([J3]) that the computational security of systems using the encoding-encryption paradigm enhanced with a wiretap encoder is related to the difficutly of sovling the LPN (Learning Parity in Noise) problem. Furthermore, the complexity of the LPN problem can be increased by a careful design of the wiretap encoder. We thus propose code design criteria for designing wiretap codes that maximize the security of the system, both from an unconditional and computational point of view, and give a corresponding generic code construction.
Publications
- PhD Theses
- [T2]. S.S. Ong, Lattice Codes for Wiretap Fading Channels , 2014.
- [T1]. F. Lin, Lattice Coding for the Gaussian Wiretap Channel-a Study on the Secrecy Gain , 2014.
- Patent
- [P1] A Full Diversity Wiretap Lattice Encoder, PAT/262/13/13/US PRV.
- Book Chapter
- [BC1] F. Lin, F. Oggier, Coding for wiretap channels, in ``Physical Layer Security in Wireless Communications", CRC Press, Taylor and Francis Group. November 2013.
- Journals
- [J11] J. Ducoat, F. Oggier, On Skew Polynomial Codes and Lattices from Quotients of Cyclic Division Algebras, Submitted, November 2014.
- [J10] W. Kositwattanarerk, S.S. Ong, F. Oggier, Construction A of Lattices over Number Fields and Block Fading Wiretap Coding , Submitted, December 2013.
- [J9] S.S. Ong, F. Oggier, Wiretap Lattice Codes from Number Fields with no Small Norm Elements, Designs, Codes and Cryptography, vol. 73, no 2, 2014.
- [J8] W. Kositwattanarerk, F. Oggier, Connections Between Construction D and Related Constructions of Lattices, Designs, Codes and Cryptography, vol. 73, no 2, 2014.
- [J7] F. Lin, F. Oggier, P. Solé, 2- and 3- Modular Lattice Wiretap Codes in Small Dimensions, Submitted, April 2013.
- [J6] J.-C. Belfiore, F. Oggier, An Error Probability Approach to MIMO Wiretap Channels. IEEE Transactions on Communications , vol. 61, no. 8, August 2013.
- [J5] F. Lin, F. Oggier, A Classification of Unimodular Lattice Wiretap Codes in Small Dimensions . IEEE Transactions on Information Theory vol. 59, no. 6, June 2013.
- [J4] F. Oggier, P. Solé, J.-C. Belfiore. Lattice Codes for the Wiretap Gaussian Channel: Construction and Analysis. Submitted, March 2011.
- [J3] M. Mihaljevic, F. Oggier, H. Imai. Homophonic Coding Design for Communication Systems Employing the Encoding-Encryption Paradigm . Submitted , December 2010.
- [J2] F. Oggier, M. Mihaljevic. An Information-Theoretic Security Evaluation of a Class of Randomized Encryption Schemes (the original title before revision was ``An Information-Theoretic Analysis of the Security of Communication Systems Employing the Encoding-Encryption Paradigm"), IEEE Transactions on Information Forensics and Security , vol. 9, no 2, Feb 2014.
- [J1] F. Oggier, H. Fathi. An Authentication Code against Pollution Attacks in Network Coding. ACM/IEEE Transactions on Networking , March 2011.
- Conferences
- [C19] X. Hou, F. Lin, F. Oggier, Construction and Secrecy Gain of a Family of 5-modular Lattices, ITW 2014.
- [C18] J. Ducoat, F. Oggier, Rank weight hierarchy of some classes of cyclic codes, ITW 2014.
- [C17] J. Ducoat, F. Oggier, Lattice Encoding of Cyclic Codes from Skew-polynomial Rings, 4ICMCTA.
- [C16] F. Lin, C. Ling, J.-C. Belfiore, Secrecy gain, flatness factor, and secrecy-goodness of even unimodular lattices , ISIT 2014.
- [C15] J. Ducoat, F. Oggier, An Analysis of Small Dimensional Fading Wiretap Lattice Codes , ISIT 2014.
- [C14] R. Vehkalahti, W. Kositwattanarerk, F. Oggier, Constructions A of Lattices from Number Fields and Division Algebras , ISIT 2014 .
- [C13] J. Ducoat, Generalized rank weights: a duality statement, Finite Fields and Applications (Fq11).
- [C12] W. Kositwattanarerk, S.S. Ong, F. Oggier, Wiretap Encoding of Lattices from Number Fields Using Codes over F_{p}, ISIT 2013.
- [C11] S.S. Ong, F. Oggier, Lattices from Totally Real Number Fields with Large Regulator, WCC 2013.
- [C10] W. Kositwattanarerk, F. Oggier, On Construction D and Related Constructions of Lattices from Linear Codes, WCC 2013.
- [C9] F. Oggier, A. Sboui, On the Existence of Generalized Rank Weights, ISITA 2012 .
- [C8] F. Lin, F. Oggier, Gaussian Wiretap Lattice Codes from Binary Self-dual Codes , ITW 2012 .
- [C7] F. Lin, F. Oggier, Secrecy Gain of Gaussian Wiretap Codes from 2- and 3-Modular Lattices , ISIT 2012 .
- [C6] F. Lin, F. Oggier, Secrecy Gain of Gaussian Wiretap Codes from Unimodular Lattices , ITW 2011.
- [C5]F. Oggier, A. Datta. Byzantine Fault Tolerance of Regenerating Codes . P2P 2011.
- [C4] J.-C. Belfiore, F. Oggier, P. Solé. Lattice Codes for the Gaussian Wiretap Channel . Invited paper, IWCC 2011 .
- [C3] J.-C. Belfiore, F. Oggier. Lattice Code Design for the Rayleigh Fading Wiretap Channel. Invited Paper, ICC 2011.
- [C2] J.-C. Belfiore, F. Oggier. Secrecy Gain: a Wiretap Lattice Code Design. ISITA 2010.
- [C1] M. Mihaljevic, F. Oggier. A Wire-tap Approach to Enhance Security in Communication Systems using the Encoding-Encryption Paradigm. Information and Coding Theory workshop, ICT 2010 .
- Talks
- [T16] On Generalized Rank Weights, by. F. Oggier, IITB, Mumbai, July 2014.
- [T15] On Pollution Attacks in Network Coding based Systems, by. F. Oggier, KTH, Stockholm, June 2014.
- [T14] Wiretap network coding and generalized rank weights, by J. Ducoat, NTU-SNU joint Workshop on Mathematics and Applications, Singapore, October 2013.
- [T13] On the Design of Wiretap Codes, by J. Ducoat, 2013 SIAM Conference on Applied Algebraic Geometry, MS17 Cryptography and Number Theory, August 2013.
- [T12] On the Design of Wiretap Codes, by J. Ducoat, Computer Science Department, Ecole Normale Superieure de Lyon, July 2013.
- [T11] Generalized Rank Weights: Duality and Griesmer Bound, by J. Ducoat, Fq11, the 11th international conference on finite fields and their applications, July 2013.
- [T10] Wiretap Network Codes and Generalized Rank Weights, by F. Oggier, Zurich COST Meeting - Random Network Coding and Designs over GF(q), June 21 2013.
- [T9] An Error Probability Approach to the Design of Wiretap Codes, by F. Oggier, University of Calgary, Canada, June 10 2013.
- [T8] Recent Results on Constructions of Lattices from Codes, by W. Kositwattanarerk, Turku University, Finland, April 23 2013.
- [T7] An Error Probability Approach to the Design of Wiretap Codes, by F. Oggier, IIT Madras, India, March 26 2013.
- [T6] Construction of Secure Algebraic Lattice Codes, by F. Oggier, Joint EMS/EWM Survey Lectures, Krakow, June 1 2012.
- [T5] On Wiretap Lattice Codes, by F. Oggier, Mathematics Department, EPFL, Lausanne, March 5 2012.
- [T4] An Error Probability Approach to Wiretap Code Design, by F. Oggier, Workshop on Algebraic Structure in Network Information Theory, Banff, Canada, August 2011.
- [T3] What can (and can't) physical layer do for secure communication?, Panel Participation, F. Oggier, Communication Theory Workshop (CTW) 2011.
- [T2] Systems of Homogeneous Polynomials in F_{q}[X_0, X_1, ..., X_n]_{d}^{h} and spectrum weight of codes over P^{n}(F_{q}), by Adnen Sboui, Third Irsee Conference on Finite Geometries, Munich, June 2011.
- [T1] On Gaussian Wiretap Lattice Codes, by F. Oggier, Department of Mathematics, IIT Mumbai, April 27 2011.