# Constant size commitment to a membership of a fixed size of elements

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.

• "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. – Maeher Jul 30 '20 at 7:00
• 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. – Od Na Jul 30 '20 at 9:51

## 1 Answer

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.

• Thank you! Does this answer also apply when the elements of $M$ are known to both $A$ and $B$? – Od Na Jul 30 '20 at 13:54
• 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$. – Maeher Jul 30 '20 at 13:56
• Thank you! Makes sense – Od Na Jul 30 '20 at 14:27