  Multi-message private information retrieval (MPIR) is an interesting
variation of PIR which allows a user to download multiple messages from the
database without revealing the identity of the desired messages. Obviously, the
user can repeatly use a single-message PIR scheme, but we wish for a more
efficient way to reduce the download cost. In [1], Banawan and Ukulus
investigate the multi-message PIR problem with replicated database. In this
paper, we consider multi-message PIR schemes where the database is stored using
minimum storage regenerating (MSR) or minimum bandwidth regenerating (MBR)
codes which are classes of optimal regenerating codes providing efficient
repair when a node in the system fails. The relationships between the costs of
storage, retrieval and repair are analysed, and explicit schemes using the MSR
and MBR codes from [2], which both achieve the optimal curve of the trade-off,
are given. To the best of our knowledge, our work is the first to explore the
multi-message PIR with coded database.
