對固定大小元素的成員的恆定大小承諾
假設有一個全域集 $ n $ 元素，其中我想承諾 $ 2n/3 $ 元素，即任何人都可以接受我的承諾並測試什麼 $ 2n/3 $ 可能的 $ n $ 我承諾的元素。
有沒有辦法通過不需要指數計算的恆定大小承諾來做到這一點。我想到了 Merkle 樹根，但是如果沒有根中包含的元素的位向量，那當然是行不通的。
在澄清評論之後，我將首先重申我理解的問題。如果我有什麼誤解，請告訴我。
讓 $ M $ 是一組大小 $ n $ . 有兩個派對 $ A $ 和 $ B $ . 我們正在尋找執行以下操作的協議。 $ A $ 選擇一個子集 $ N\subseteq M $ 和 $ |N|=2n/3 $ 併計算一些消息 $ m $ 和 $ |m|=\ell $ ， 在哪裡 $ \ell $ 是一個常數，獨立於 $ n $ . 給定 $ m $ ， 派對 $ B $ 能夠重建和輸出 $ N $ 有機率 $ 1 $ .
如果這是對您正在尋找的內容的正確描述，那麼很遺憾是不可能的，因為它意味著無限的無損數據壓縮。
有 $ \binom{n}{\frac{2n}{3}} $ 許多可能的子集，所以通過發送 $ m $ 你正在轉移 $ \log_2 \binom{n}{\frac{2n}{3}} $ 位的資訊。
我們有 $$ \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}. $$
自從 $ m $ 只是 $ \ell $ 比特長，鴿巢原理告訴我們，你不能轉移超過 $ \ell $ 位的資訊。對於任何 $ n>3\ell $ ¹這顯然被違反了。
¹這種情況發生得更早，我只是懶得在這裡進行嚴格的分析，我們使用的是非常寬鬆的下限。