
Private information retrieval scheme for coded data storage is considered in
this paper. We focus on the case where the size of each data record is large
and hence only the download cost (but not the upload cost for transmitting
retrieval queries) is of interest. We prove that the tradeoff between storage
cost and retrieval/download cost depends on the number of data records in the
system. We also propose a fairly general class of linear storage codes and
retrieval schemes and derive conditions under which our retrieval schemes are
errorfree and private. Tradeoffs between the storage cost and retrieval costs
are also obtained. Finally, we consider special cases when the underlying
storage code is based on an MDS code. Using our proposed method, we show that a
randomly generated retrieval scheme is indeed very likely to be private and
errorfree.

Motivated by communication through a network employing linear network coding,
capacities of linear operator channels (LOCs) with arbitrarily distributed
transfer matrices over finite fields are studied. Both the Shannon capacity $C$
and the subspace coding capacity $C_{\text{SS}}$ are analyzed. By establishing
and comparing lower bounds on $C$ and upper bounds on $C_{\text{SS}}$, various
necessary conditions and sufficient conditions such that $C=C_{\text{SS}}$ are
obtained. A new class of LOCs such that $C=C_{\text{SS}}$ is identified, which
includes LOCs with uniformgivenrank transfer matrices as special cases. It is
also demonstrated that $C_{\text{SS}}$ is strictly less than $C$ for a broad
class of LOCs. In general, an optimal subspace coding scheme is difficult to
find because it requires to solve the maximization of a nonconcave function.
However, for a LOC with a unique subspace degradation, $C_{\text{SS}}$ can be
obtained by solving a convex optimization problem over rank distribution.
Classes of LOCs with a unique subspace degradation are characterized. Since
LOCs with uniformgivenrank transfer matrices have unique subspace
degradations, some existing results on LOCs with uniformgivenrank transfer
matrices are explained from a more general way.

Shannon's fundamental bound for perfect secrecy says that the entropy of the
secret message cannot be larger than the entropy of the secret key initially
shared by the sender and the legitimate receiver. Massey gave an information
theoretic proof of this result, however this proof does not require
independence of the key and ciphertext. By further assuming independence, we
obtain a tighter lower bound, namely that the key entropy is not less than the
logarithm of the message sample size in any cipher achieving perfect secrecy,
even if the source distribution is fixed. The same bound also applies to the
entropy of the ciphertext. The bounds still hold if the secret message has been
compressed before encryption.
This paper also illustrates that the lower bound only gives the minimum size
of the preshared secret key. When a cipher system is used multiple times, this
is no longer a reasonable measure for the portion of key consumed in each
round. Instead, this paper proposes and justifies a new measure for key
consumption rate. The existence of a fundamental tradeoff between the expected
key consumption and the number of channel uses for conveying a ciphertext is
shown. Optimal and nearly optimal secure codes are designed.

Strong typicality and the Markov lemma have been used in the proofs of
several multiterminal source coding theorems. Since these two tools can be
applied to finite alphabets only, the results proved by them are subject to the
same limitation. Recently, a new notion of typicality, namely unified
typicality, has been defined. It can be applied to both finite or countably
infinite alphabets, and it retains the asymptotic equipartition property and
the structural properties of strong typicality. In this paper, unified
typicality is used to derive a version of the Markov lemma which works on both
finite or countably infinite alphabets so that many results in multiterminal
source coding can readily be extended. Furthermore, a simple way to verify
whether some sequences are jointly typical is shown.

Motivated by linear network coding, communication channels perform linear
operation over finite fields, namely linear operator channels (LOCs), are
studied in this paper. For such a channel, its output vector is a linear
transform of its input vector, and the transformation matrix is randomly and
independently generated. The transformation matrix is assumed to remain
constant for every T input vectors and to be unknown to both the transmitter
and the receiver. There are NO constraints on the distribution of the
transformation matrix and the field size.
Specifically, the optimality of subspace coding over LOCs is investigated. A
lower bound on the maximum achievable rate of subspace coding is obtained and
it is shown to be tight for some cases. The maximum achievable rate of
constantdimensional subspace coding is characterized and the loss of rate
incurred by using constantdimensional subspace coding is insignificant.
The maximum achievable rate of channel training is close to the lower bound
on the maximum achievable rate of subspace coding. Two coding approaches based
on channel training are proposed and their performances are evaluated. Our
first approach makes use of rankmetric codes and its optimality depends on the
existence of maximum rank distance codes. Our second approach applies linear
coding and it can achieve the maximum achievable rate of channel training. Our
code designs require only the knowledge of the expectation of the rank of the
transformation matrix. The second scheme can also be realized ratelessly
without a priori knowledge of the channel statistics.