使用 Pedersen 承諾作為向量

我正在閱讀Bootle/Groth。我試圖了解他們如何使用 Pedersen 承諾來承諾向量。以下是我在本文中對 Pedersen 承諾的理解：

1. 我們有一個群 $ \mathbb{Z}_p^* $ , $ g $ 作為發電機。
2. 生成器產生隨機組元素 $ (g_1,\dots,g_n,y) $ .
3. 我們承諾向量 $ \vec{m} = (m_1,\dots, m_n) $ 通過選擇 $ r $ 隨機從 $ \mathbb{Z}p^* $ 接著 $ c = Com(\vec{m};r) $ 是 $ c = y^r \prod{i=1}^n g_i^{m_i} $ .

論文接著描述瞭如何 $ \vec{m} $ 實際上是多項式中的一行係數，驗證者可能會發送一個輸入 $ x $ 進行評估（不知道多項式是什麼！）。不過，我想知道的是：

1. 我對這個方案的理解有意義嗎？
2. 如果是這樣，是什麼讓這個方案（計算上）隱藏和綁定？我不知道如何證明這一點。

是的，您的方案基本上是正確的 - 除了該組不能 $ \mathbb{Z}_p^* $ ，因為後者沒有素數順序。然而，它可以是許多其他的東西——比如平方的乘法子群 $ \mathbb{Z}_p^* $ ，或橢圓曲線。讓我們簡單地考慮一下你描述的方案，在一些組 $ \mathbb{G} $ 素數的 $ p $ .

為什麼計劃隱藏？

直覺地說，該計劃是完全隱藏的，因為對於任何承諾 $ c $ , 對於任何元組 $ (m_1, \cdots, m_n) $ , 存在一個開口 $ r $ 那個“解釋” $ c $ 作為 $ c = y^r\prod_{i=1}^n g_i^{m_i} $ ，以及這個的分佈 $ r $ （接管用於生成的硬幣 $ c $ ) 是均勻的。

更正式地，表示 $ a\gets_r S $ 繪畫的動作 $ a $ 均勻隨機地從 $ S $ ，承諾方案是完全隱藏的，因為對於任何一對元組 $ (m_1, \cdots, m_n) $ 和 $ (m’_1, \cdots, m’n) $ , 分佈$$ D = \left{c : r\gets_r\mathbb{Z}p, c \gets y^r\prod{i=1}^n g_i^{m_i}\right} \text { and } D’ = \left{c : r\gets_r\mathbb{Z}p, c \gets y^r\prod{i=1}^n g_i^{m’i}\right} $$完全相等。這很容易證明：對於 $ i=1 $ 至 $ n $ ， 讓 $ \alpha_i $ 表示指數 $ g_i $ 在基地 $ y $ （那是， $ g_i^{\alpha_i} = y $ ）。讓 $ \alpha \gets \sum{i=1}^n \alpha_im_i $ 和 $ \alpha’ \gets \sum{i=1}^n \alpha_im’_i $ .

然後 $ c $ 計算為 $ y^r\prod_{i=1}^n g_i^{m_i} = y^{r+\alpha} $ 在 $ D $ （對於隨機 $ r $ ）， 並作為 $ y^r\prod_{i=1}^n g_i^{m’_i} = y^{r+\alpha’} $ 在 $ D $ （對於隨機 $ r $ ）。因此，分配的平等是直接的。

為什麼方案具有約束力？

我們可以證明該方案在離散對數假設下具有約束力。讓 $ \mathcal{A} $ 是一個 PPT 對手，給定係統的參數（在這種情況下， $ (y,g_1, \cdots, g_n) $ ）可以產生（具有不可忽略的機率 $ \varepsilon $ ) 一個承諾以及對兩個不同明文的有效開口，id est： $ (c,(m_1, \cdots, m_n),r,(m’_1,\cdots, m’_n),r’) $ ， 在哪裡 $ c\in\mathbb{G} $ 是一種承諾， $ (m_1, \cdots, m_n) \neq (m’1, \cdots, m’n) $ ， 和$$ c = y^r\prod{i=1}^n g_i^{m_i} = y^{r’}\prod{i=1}^n g_i^{m’_i}. $$

讓我們使用該算法以不可忽略的機率打破離散對數假設。收到隨機離散對數質詢後 $ (g,y) $ ，我們選擇 $ i $ 之間隨機 $ 1 $ 和 $ n $ , 並設置 $ g_i \gets g $ . 然後我們挑 $ n-1 $ 值 $ \alpha_j $ , $ (\alpha_j)_{j\neq i}\gets_r \mathbb{Z}_p^{n-1} $ 並設置 $ g_j \gets y^{\alpha_j} $ 對於任何 $ j\neq i $ . 請注意 $ (y, g_1, \cdots, g_n) $ 完美分佈為 Pedersen 承諾方案的有效參數元組。因此，我們執行 $ \mathcal{A}(y,g_1,\cdots, g_n) $ 並獲得 $ (c,(m_1, \cdots, m_n),r,(m’_1,\cdots, m’_n),r’) $ 它有可能在哪裡成立 $ \varepsilon $ 那 $ (m_1, \cdots, m_n) \neq (m’1, \cdots, m’n) $ 和 $ c = y^r\prod{j=1}^n g_j^{m_j} = y^{r’}\prod{j=1}^n g_j^{m’_j} $ . 我們檢查是否 $ m_i \neq m’_i $ ，否則重新啟動協議。請注意，作為我們（均勻隨機）選擇 $ i $ 完全隱藏在 $ \mathcal{A} $ ， 並作為 $ (m_1, \cdots, m_n) \neq (m’_1, \cdots, m’_n) $ 至少有機率 $ \varepsilon $ , 它認為 $ m_i \neq m’_i $ 至少有機率 $ \varepsilon/n $ .

讓 $ \alpha \gets \sum_{j\neq i} \alpha_j m_j $ 和 $ \alpha’ \gets \sum_{j\neq i} \alpha_j m’_j $ . 如果 $ m_i \neq m’_i $ ，因此我們有以下內容：

$ y^r\prod_{j=1}^n g_j^{m_j} = y^{r’}\prod_{j=1}^n g_i^{m’_j} $

因此 $ y^r g^{m_i}\cdot y^{\alpha} = y^{r’} g^{m’_i} y^{\alpha’} $

因此 $ y^{r-r’+\alpha-\alpha’} = g^{m_i-m’_i} $ ， 和 $ m_i - m’_i \neq 0 $

因此 $ y^{(r-r’+\alpha-\alpha’)\cdot(m_i-m’_i)^{-1}\bmod p} = g $ ：我們獲得的離散對數 $ y $ 在基地 $ g $ .

因此，如果 $ \mathcal{A} $ 至少以機率打破 Pedersen 承諾方案的約束屬性 $ \varepsilon $ ，我們可以構造一個算法，給定訪問 $ \mathcal{A} $ ，提取的離散對數 $ g $ 在基地 $ y $ 至少有機率 $ \varepsilon/n $ .

引用自：https://crypto.stackexchange.com/questions/55955