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.

  • $\begingroup$ 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? $\endgroup$ – Changyu Dong Mar 26 '19 at 9:35
  • $\begingroup$ What you said requires us to send $O(nk)$ data. The communication must strictly be less than $O(nk)$. $\endgroup$ – Sahu Mar 26 '19 at 10:10

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.