零知識驗證以檢查私有元素是否位於隱藏在中央伺服器上的集合中
我正在嘗試確定如何將 ZK 證明應用於下面的非對稱場景。
假設在一個集中式 Web 伺服器上有一個包含 5000 個秘密元素的列表。
使用者試圖猜測這 5000 個元素是什麼。
但是，使用者不想向中央伺服器透露他們的錯誤猜測。
使用者向網路伺服器送出他們猜測選擇的證明，伺服器檢查證明是否顯示使用者猜測了 5000 個元素之一。
重要的是，這個方案的目標是：1）使用者不應該能夠在本地驗證他們的猜測是否是集合的一部分，以及 2）伺服器不應該知道使用者的猜測是什麼，只有當它是集合的一部分時集。
如何實施？
此外，您將使用哪些庫來實現此方案（跨任何語言）？
聽起來像一個計劃 $ \phi $ - 隱藏會很好用。
單個秘密元素的方案
編寫一個眾所周知的散列到素數函式，將猜測映射到大約 128 位的素數（例如，取 SHA3 輸出的前 128 位，將其視為整數並查找下一個最大素數）。
將您的秘密元素散列到素數 $ s $ 然後構造一個，比如 1024 位素數 $ p $ 這樣 $ s|p-1 $ 和另一個素數 $ q $ 然後相乘 $ p $ 和 $ q $ 創造公共價值 $ N=pq $ . 發布 $ N $ 和你散列函式。注意 $ s|\phi(N) $ .
為了送出猜測，使用者將他們的猜測散列到素數 $ g $ , 生成一個隨機元素 $ e\in(\mathbb Z/N\mathbb Z)^\times $ 並將其提升到權力 $ g $ 模數 $ N $ 創建響應 $ r=e^g\mod N $ . 他們發送 $ r $ 給檢查員。
檢查器接受響應 $ r $ 並提升他們的權力 $ \phi(N)/s $ 模數 $ N $ . 如果 $ r $ 是一個 $ s $ th（即幾乎可以肯定不是這種情況，除非 $ g=s $ ) 然後他們將得到答案 1 確認正確的猜測。任何其他答案都應該被拒絕。
特性
如果使用者能夠確定他們的猜測是正確的，這將打破 $ \phi $ -隱藏假設。
對於任何散列到不正確素數的猜測，伺服器獲得了對不正確猜測的零知識 $ h\neq g $ ， 響應 $ r $ 可能同樣來自隨機元素選擇 $ e’=r^{1/h}\mod N $ .
多秘密計劃
對於多秘密方案，為了使伺服器無法區分猜測，我們應該將所有猜測散列到相同的素數 $ s $ . 例如，這可以通過將猜測散列到 6000 位值（例如使用諸如 SHAKE 之類的 XOF）來安排，其中的值 $ h_1,\ldots, h_{5000} $ 對應於秘密元素。然後我們可以構造一個 128x6000 的二進制矩陣 $ M $ 與條目匹配的二進制向量 $ h_1\oplus h_2, h_1\oplus h_3,\ldots, h_1\oplus h_{5000} $ 位於零空間 $ M $ . 這確保了 $ M\cdot h_i= M\cdot h_j $ 對所有人 $ 1\le i,j\le 5000 $ 因此將這個 128 位值視為整數並尋找下一個素數將導致相同的結果 $ s $ 對於所有秘密輸入。
不過需要謹慎。在這個方案中，使用者可以檢查兩個猜測是否都是秘密，方法是對它們進行散列、異或運算並乘以 $ M $ . 如果答案是 0，那麼兩種猜測都可能是正確的。如果這不再滿足您的要求，則可能需要不同的方案。