# 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.

• Can't you just create $k$ commitments, each for an individual message $m_i$? Surely this allows you to commit to all values and selectively open some. Or are there any other constraints not mentioned in the question? – Changyu Dong Mar 26 '19 at 9:35
• What you said requires us to send $O(nk)$ data. The communication must strictly be less than $O(nk)$. – Sahu Mar 26 '19 at 10:10

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).