  We propose a new capacity-achieving code for the private information
retrieval (PIR) problem, and show that it has the minimum message size (being
one less than the number of servers) and the minimum upload cost (being roughly
linear in the number of messages) among a general class of capacity-achieving
codes, and in particular, among all capacity-achieving linear codes. Different
from existing code constructions, the proposed code is asymmetric, and this
asymmetry appears to be the key factor leading to the optimal message size and
the optimal upload cost. The converse results on the message size and the
upload cost are obtained by a strategic analysis of the information theoretic
proof of the PIR capacity, from which a set of critical properties of any
capacity-achieving code in the code class of interest is extracted. The
symmetry structure of the PIR problem is then analyzed, which allows us to
construct symmetric codes from asymmetric ones, yielding a meaningful bridge
between the proposed code and existing ones in the literature.
