Suppose there is a global set of $n$ elements, out of which I want to commit to $2n/3$ elements, i.e., anyone can take my commitment and test what $2n/3$ of the possible $n$ elements I committed to.

Is there any way to do so with a constant size commitment that doesn't require exponential calculations. I had Merkle tree root in mind, but of course that doesn't work without a bit-vector of the elements included in the root.

  • $\begingroup$ "i.e., anyone can take my commitment and test what 2𝑛/3 of the possible 𝑛 elements I committed to." So there's no hiding? It doesn't sound you're looking for a commitment in the usual sense then. $\endgroup$ – Maeher Jul 30 '20 at 7:00
  • $\begingroup$ No hiding. In other words, can one party tell another party with a constant size message of the elements in a subset containing $2n/3$ elements from a total of $n$ globally known elements. $\endgroup$ – Od Na Jul 30 '20 at 9:51

I will first restate the question as I understand it after the clarifying comment. If I'm misunderstanding something, please let me know.

Let $M$ be a set of size $n$. There are two parties $A$ and $B$. We are looking for a protocol that does the following. $A$ chooses a subset $N\subseteq M$ with $|N|=2n/3$ and computes some message $m$ with $|m|=\ell$, where $\ell$ is a constant, independent of $n$. Given $m$, party $B$ is able to reconstruct and output $N$ with probability $1$.

If that is a correct description of what you're looking for, then it's sadly impossible, since it would imply infinite lossless data compression.

There are $\binom{n}{\frac{2n}{3}}$ many possible subsets, so by sending $m$ you are transferring $\log_2 \binom{n}{\frac{2n}{3}}$ bits of information.

We have $$\log_2 \binom{n}{\frac{2n}{3}} \geq \log_2\left(\frac{n}{2n/3}\right)^{2n/3}=\log_2\left(\frac{9}{4}\right)^{n/3} > \log_2 2^{n/3} = \frac{n}{3}.$$

Since $m$ is only $\ell$ bits long, the pigeonhole principle tells us that you cannot transfer more than $\ell$ bits of information. For any $n>3\ell$¹ that's clearly being violated here.

¹This happens even earlier, I just can't be bothered to do a tight analysis here, we're using pretty loose lower bounds.

  • $\begingroup$ Thank you! Does this answer also apply when the elements of $M$ are known to both $A$ and $B$? $\endgroup$ – Od Na Jul 30 '20 at 13:54
  • $\begingroup$ Yes. The information being transferred is which elements (think: the indices of an ordered representation) of $M$ are in $N$, not the elements of $M$. $\endgroup$ – Maeher Jul 30 '20 at 13:56
  • $\begingroup$ Thank you! Makes sense $\endgroup$ – Od Na Jul 30 '20 at 14:27

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.