連接消息的 ElGamal 加密
假設一個加密器分別產生三個 ElGamal 密文 $ c_1 = E(m_1) $ , $ c_2 = E(m_2) $ 和 $ c_3 = E(m_3) $ ，它加密消息 $ m_1 $ , $ m_2 $ 和 $ m_3 $ ， 分別。
加密器是否有可能用零知識證明證明 $ m_1 $ = $ m_2 \mathbin| m_3 = m_2 \times 2^{32} + m_3 $ ，即，那個 $ c_1 $ 加密消息的串聯 $ m_2 $ 和 $ m_3 $ ?
（由版主添加以總結與 OP 的交流）
- 它用於ElGamal 加密的變體，其中用於明文 $ m $ 組元素 $ g^m $ 是使用標準 ElGamal 加密的內容。
- 在表達式中 $ m_2\mathbin|m_3 $ , 明文整數 $ m_2 $ 和 $ m_3 $ 是固定大小（32 位）的位串。
- 加密器/證明者的一種選擇是利用加密時生成的臨時秘密指數。
我們將考慮 ElGamal 加密的加法同態變體，在具有生成器的有限群中 $ g $ 素數¹ $ n $ .
私鑰是一個隨機秘密整數 $ d $ 均勻隨機抽取 $ [0,n) $ . 公鑰是 $ q\gets g^d $ .
整數加密 $ m $ 去：
- 繪製一個隨機秘密整數 $ k $ 均勻隨機地 $ [0,n) $
- 計算 $ r\gets g^k $ 和 $ s\gets g^m\cdot q^k $
- 輸出密文 $ (r,s)=c $ 作為加密的結果 $ m $ ， 著名的 $ E(m) $ .
密文解密 $ (r,s)=c $ 去
- 檢查 $ r $ 和 $ s $ 在組中
- 計算 $ a\gets r^{n-d}\cdot s $
- 查找整數 $ m\in [0,n) $ 和 $ g^m=a $ . 這需要小型的易處理的工作 $ m $ ，例如使用baby-step/giant-step。對於大 $ m $ , 我們假設在我們寫的時候某個 oracle 解決了這個問題 $ D(c) $ .
- 輸出 $ m $ 作為解密的結果 $ c $ ， 著名的 $ D(c) $ .
注意：加密 $ E $ 不是函式。 $ D $ 是一個。
什麼時候 $ c=(r,s) $ 和 $ c’=(r’,s’) $ ，我們會注意到 $ c\cdot c’ $ 為了 $ (r\cdot r’,s\cdot s’) $ ; 和 $ c^u $ 為了 $ (r^u,s^u) $ .
很容易證明
- 如果 $ 0\le m<n $ ， 然後 $ D(E(m)),=,m $ [任何 $ k $ 被畫了 $ E $ ]
- $ D(E(m)\cdot E(m’)),=,(m+m’)\bmod n $
- 對於任何整數 $ u $ 它認為 $ D(E(m)^u),=,(m\times u)\bmod n $ [在哪裡 $ \times $ 是整數乘法]。
下面，我們假設 $ c_i $ 已獨立計算為 $ E(m_i) $ 為了 $ i\in{1,2,3} $ ; $ m_2 $ 和 $ m_3 $ 在 $ [0,2^{32}) $ ; 的定義 $ m_2\mathbin|m_3 $ 作為 $ m_2\times2^{32}+m_3 $ ; 和 $ n>m_1 $ , $ n\ge2^{64} $ .
（鑑於這樣的價值 $ c_i $ ) 加密器是否有可能用零知識證明證明 $ m_1,=,m_2 \mathbin| m_3 $ ?
是的，如果加密者/證明者持有私鑰 $ d $ ： 定義 $ c\gets{c_1}^{n-1}\cdot{c_2}^{(2^{32})}\cdot c_3 $ ，並提出任何懷疑的零知識證明 $ D(c)=0 $
$$ see next paragraph $$. 爭論 $ D(c)=0 $ 證明 $ -m_1+m_2\times2^{32}+m_3\bmod n,=,0 $ ， 因此 $ m_1,=,m_2\times2^{32}+m_3 $ . 的計算 $ c $ 不會太繁瑣，用於計算 $ {c_2}^{(2^{32})} $ 只需要計算一個 $ 62 $ 組中的正方形，而 $ {c_1}^{n-1} $ 最多需要 $ 2\left\lfloor\log_2n\right\rfloor $ 平方和較少的乘法，使用標準的指數方法。 還有一個零知識證明（ZKP） $ D(c)=0 $ ; 也就是說，與 $ c=(r,s) $ , 它持有 $ r^{n-d}\cdot s,=,g^0 $ ; 等效地，即 $ r^d=s $ . 假設證明者知道 $ d $ , 可以直接檢查這個。ZKP 旨在說服驗證者了解組元素 $ g,q,r,s $ 證明者知道 $ d $ 這樣 $ g^d,=,q $ 和 $ r^d,=,s $ . 這是等效離散對數的 Chaum-Pedersen 證明，在那里和那裡進行了解釋。
這應該說服精通數學的理性驗證者。一個隨機的公民擔心選舉中存在欺詐行為，祝你好運。
如果加密者/證明者不持有私鑰，但控製或保存 $ k_i $ ，也有辦法。
一種簡單的方法是加密器/證明器生成 $ k_1 $ 作為 $ k_1\gets k_2\times2^{32}+k_3 $ ，而不是隨機的。這確保 $ c_1,=,{c_2}^{(2^{32})}\cdot c_3 $ ，這對任何人來說都是微不足道的。這種關係本身可以證明這種選擇 $ k_1 $ [在假設之上 $ m_1=m_2 \mathbin| m_3 $ ]不會削弱任何東西。更簡單的， $ c_1 $ 可以直接計算為 $ c_1\gets{c_2}^{(2^{32})}\cdot c_3 $ .
計算和揭示 $ k\gets k_2\times2^{32}+k_3-k_1 $ 也可以完成這項工作：它允許檢查 $ c_1\cdot(g^k,q^k)={c_2}^{(2^{32})}\cdot c_3 $ , 這最終證明 $ D(c_1),=,D(c_2)\mathbin|D(c_3) $ . 但我通過證明我的直覺並沒有透露任何有用的資訊，我不會說這是一個真正的 ZKP。
但這可以通過等效離散對數的 Chaum-Pedersen 證明轉化為真正的 ZKP： $ c=(r,s) $ 定義為 $ {c_1}^{n-1}\cdot{c_2}^{(2^{32})}\cdot c_3 $ , ZKP 旨在說服驗證者知道組元素 $ g,q,r,s $ 證明者知道 $ k $ 這樣 $ g^k,=,r $ 和 $ q^k,=,s $ .
¹ 即：該組有 $ n $ 元素 $ g^m=\underbrace{g\cdot g\ldots g}_{m\text{ terms}} $ 為了 $ m $ 在 $ [1,n] $ ， 和 $ g^n $ 團體中立 $ 1 $ . 為了安全， $ n $ 通常是一個大素數。一個簡單的例子是Schnorr 組。