The main theme of my PhD research has been designing efficient lattice coding schemes for secure and reliable communication, and secret key generation. During my short visit to INC, I worked on a problem of estimating the pattern maximum likelihood distribution of discrete-time Markov Chains.
The bidirectional relay is a three-node network where two nodes A and B want to exchange messages via a relay R. All links between user nodes and relay are assumed to be wireless AWGN links. If A has message X and B has message Y, then a simple two-stage protocol for exchanging X and Y is the following:
- A encodes X to U and B encodes Y to V, and they simultaneously broadcast the codewords. The relay obtains
W=U+V+Z,
where Z is the additive noise.
- R estimates $X\oplus Y$ (we embed the messages in a suitable Abelian group with addition operation $\oplus$ ), encodes this, and broadcasts to the user nodes.
Assuming that all goes well, A and B will be able to recover Y and X respectively. For such a setup, Wilson et al.[1] and Nazer and Gastpar[2] gave a nested lattice coding scheme which ensures that the desired messages can be recovered reliably. If we assume that all links have unit channel gains, both nodes have transmit power constraints of P, and the noise variance is $\sigma^2$, then a rate of $\frac{1}{2}\log_2 ( \frac{1}{2}+\frac{P}{\sigma^2} )$ can be achieved.
We look at a problem of securely computing $X \oplus Y$.
If we impose the additional constraint that the relay must only be able to recover $X\oplus Y$ and not X or Y individually, what can we say about this problem? More specifically, assuming that the messages are uniformly chosen at random, we want
- R must be able to recover $X\oplus Y$.
- W must be independent of X, and
- W must be independent of Y.
Firstly, is this even doable? We showed [3] that this is indeed the case. In fact, our scheme works even if the distribution of Z is arbitrary and unknown to the two users. We gave a lattice coding scheme, and found the achievable rates. We also relaxed the security constraint to only requiring that $I(X;W)\to 0$ and $I(Y;W)\to 0$ for large blocklengths and gave a scheme that achieves a higher rate. Later, we also made some observations on the case where the channel gains are not unity, and possibly unknown to the user nodes.[4]
Consider a set-up where $m$ terminals have correlated random sources. They have access to a public noise-free communication channel, and the aim is to agree upon a secret message (key) by talking to each other on the public channel. The key so obtained must be kept secret from a passive eavesdropper who can listen to all the exchange that takes place across the public channel. At the end of the communication, all terminals must be able to recover the key (which is a function of the sources) reliably, and the key must be independent\/nearly independent of the public communication (which is a random variable that depends on the sources and possibly some added randomness).
This set-up is called the source model for secret key generation.
Csiszar and Narayan [1] studied the multiterminal source model where all terminals have access to discrete sources (drawn from a finite alphabet). They gave a protocol for secret key generation and characterized the secret key capacity, the maximum number of key bits that can be generated per source sample. This was extended to the case where the sources are Gaussian by Nitinawarat and Narayan [2]. We studied a specific case of the Gaussian multiterminal source model (the dependence structure of the sources can be described by a Markov tree), and gave a lattice coding scheme whose overall complexity (of computing the secret key) is polynomial in the number of samples [3].
Lattice codes have been shown to be useful in several problems such as reliable communication in AWGN channels, vector quantization, multiterminal source and channel coding, physical layer security, and so on.
A useful class of lattices is the so-called Construction-A lattices. These are derived from linear codes over prime fields, and are a good choice for the previously mentioned applications.
A key deterrent to using lattice codes in practice is that the computational complexity of finding the closest lattice point scales exponentially in the dimension of the lattice.
We studied a class of Construction-A lattices derived from low-density parity check (LDPC) codes, called low-density Construction-A (LDA) lattices.
These were proposed by di Pietro et al. [1], who showed that LDA lattices achieve the capacity of the AWGN channel with closest lattice point decoding. We carried on further studies and showed that LDA lattices have several structural properties that are desirable in practice.
We also proposed a concatenated lattice coding scheme whose encoding/decoding complexity is polynomial in the blocklength [3]. This gives a general technique to reduce the decoding complexity (while maintaining the same rate-error probability performance) of lattice coding schemes. Thus, we can get poly-time coding schemes that achieve the capacity of the AWGN channel, the Gaussian wiretap channel, the rate-distortion limit for memoryless Gaussian sources, and near-optimal poly-time schemes for physical layer network coding, secure compute-and-forward, and several other applications.
This is motivated by the problem of inferring the structure of a graph from a random walk starting from a random vertex. More generally, suppose that we observe $n$ samples of a discrete-time Markov chain (DTMC). We do not know the state space/alphabet of the DTMC, but only know that the number of states/alphabet size is k. In such a scenario, we want to estimate the transition kernel of the DTMC up to a relabeling of the alphabet. In such a case, the only useful information in the observed sequence is the pattern of the observed sequence. The pattern of an n-length string is the n-length string of numbers obtained by replacing each element by its order of appearance. For example, the pattern of the string "shashank" is "12312345". The kernel that maximizes the probability of occurrence of the observed pattern is called the pattern maximum likelihood (PML) distribution.
The motivation for studying the PML distribution of memoryless sources came from the problem of universal source compression. [1,2] There has also been work on designing efficient algorithms to compute the PML estimate [3]. We extended some of the results to Markov sources, and studied some variational techniques for efficiently computing the PML estimate for DTMCs [4].