Selectively opening only a few commitments I have k messages $m_1,m_2...m_k$ and I want to commit to all of them but open only a few of them -- as asked by Bob. Each message is of $n$ bits. Show how one can commit to all the $k$ messages and then later open only the messages that Bob asks her to such that the total communication is less than $O(nk)$.

I am stuck at the very beginning. I am not able to find what kind of a cryptographic object is suitable for this. Any clue will be appreciated.
Since your main concern is communication, then use something that can reduce communication cost. I can think of two possible directions.

1 Use a Merkle tree

The idea is to commit to all elements, then build a Merkle tree on top of the commitments, and send the root of the Merkle tree as the commitment of the whole set. To reveal an element, open its commitment and show the commitment is covered by the Merkle tree.

2 Use a cryptographic accumulator


  A (static) cryptographic accumulator scheme allows to accumulate a
  finite set $X = \{x_1 , . . . , x_n \}$ into a succinct value $accX$ , the so
  called accumulator. For every element $x_i \in X$ , one can efficiently
  compute a so called witness $witx_i$ to certify the membership of $x_i$ in
  $acc_X$ . However, it should be computationally infeasible to find a
  witness for any non-accumulated value $y \not\in X$ (collision freeness).


Essentially the accumulator serves as a commitment of a set, and each witness serves as the opening secret of the individual elements in the set.