消息值符號的零知識證明
我正在使用 ElGamal 加密來加密整數消息 $ m $ 作為，
$ E[m] $ = ( $ g^x $ , $ g^m.h^x $ )
我可以寫一個零知識證明來向驗證者證明 $ m > 0 $ ?
我可以創建位表示 $ m $ 並加密每一位來證明這一點，但我有很多整數，並試圖避免這種方法。
您正在尋找的東西稱為範圍證明。最近對該主題進行了大量研究——事實上，研究如此之多，以至於很難知道什麼是最先進的，以及在給定情況下哪種解決方案最合適。因此，為了讓您自己評估最適合您的確切情況的方法，我將嘗試對現有方法及其限制進行快速調查。
最自然的方法是您提到的幼稚方法：承諾 $ (m_i)_{i\leq \log q/2} $ 明文的 $ m $ ， 證明 $ \sum m_i 2^i = m $ 然後 $ m_i(1-m_i)=0 $ 對於每個 $ i $ （id est，每個 $ m_i $ 有一點）。不幸的是，這需要 $ O(\log q) $ 組元素，因此它非常昂貴。本文提出了對這種簡單方法的改進。構想如下：而不是分解 $ m $ 在base 2中，在base中分解 $ B $ . 您現在只需要承諾 $ \log_B(q/2) $ 元素 $ m_i $ 鹼基分解 $ B $ . 有效地證明（在恆定時間內） $ m_i \in {0, \cdots, B-1} $ ，想法是讓驗證者添加整數的簽名 $ 0, \cdots, B-1 $ 到公鑰，並使用已知方法讓證明者證明他可以為送出的值生成簽名。因為他不能為外部的任何價值偽造簽名 $ {0, \cdots, B-1} $ , 足以完成證明。這為您提供了一個可以交流的證明 $ O(\log q / \log \log q) $ 組元素，但它有一個缺點：它需要使用帶有適當配對操作的橢圓曲線，因為簽名部分需要這樣的配對。這裡面的常數 $ O() $ 已在本文中改進。
現在，您可能也可以使用不適用於任意證明者的證明，但僅適用於計算有界證明者 - 它在實踐中不會產生太大影響。這稱為零知識論證，在這種情況下有更有效的方法。我將要描述的那個在一篇文章中沒有明確提及，而是格羅斯和拜耳一系列作品的自然結果（因此可以被視為民間傳說）。核心思想是可以使用一種稱為“廣義 Pedersen 承諾方案”的方案一次承諾多個數字：公鑰包含 $ n+1 $ 隨機組元素，並承諾 $ n $ 價值觀 $ (a_1, \cdots, a_n) $ 用隨機硬幣 $ r $ , 計算 $ c = h^r\cdot \prod_i g_i^{a_i} $ . 這是完全隱藏的，並且在離散對數假設下具有計算約束力。
為了證明 $ m $ 在 $ [0,q/2] $ , 分解 $ m $ 在基地2： $ m = \sum_i m_i2^i $ . 按包對這些位進行分組 $ \sqrt{\log q} $ 連續位（你會有 $ O(\sqrt{\log q}) $ 這樣的包）。使用廣義 Pedersen 方案送出每個包，每個包有一個組元素。現在，執行批量產品證明以顯示所有送出的值都是位（即，它們滿足 $ m_i^2-m_i = 0 $ ）。這種批量證明是不平凡的，但已經在例如這篇文章中進行了詳細的研究。本質上，它們都是通過仔細反复應用 Schwartz-Zippel 引理來構造的，該引理用於（非正式地）說，如果某人知道某些值的隨機線性組合，則他必須知道所有值。應用這個引理可以縮小問題的維度。
證明者還必須證明 $ m = \sum_i m_i 2^i $ ; 前面提到的文章還展示瞭如何建構這樣的證明。所開發的技術本質上允許對可以用線性代數表示的承諾值的任何陳述執行有效的（批量）證明，請參閱這篇文章。總體而言，這為您提供了一個範圍證明，其中包含 $ O(\sqrt{\log q}) $ 組元素。它涉及許多輪次（我會說 7 到 9 輪），但如果您可以使用 Fiat-Shamir 變換，則可以將其設為非互動式，該變換在隨機預言模型中是安全的（因此只有“啟發式安全”）。
如果您想要更短的證明，那麼您可以再次考慮使用帶有配對的橢圓曲線，以使用上述方法的改進版本：本文基本上做了我上面描述的內容，但通過使用配對獲得了額外的效率，允許（非正式地）承諾承諾，從而獲得更高級別的“打包”。它提供了一個通信協議 $ O(\log^{1/3}q) $ 組元素。
最後……你可以有一個恆定大小的證明。但是，你必須依靠一種完全不同的方法：首先，承諾 $ m $ 在一組未知順序中，並證明您在兩個不同的組中送出了相同的值，例如使用本文。要擁有這樣一個組，通常的方法是使用 RSA 模數 $ N = pq $ ，兩個安全素數的乘積，並取平方群的生成器，其順序 $ \phi(N)/2 $ 是未知的，除非可以考慮 $ N $ . 請注意，這意味著常數會很大：基於分解的方法需要非常大的組（例如， $ |N| = 2048 $ ）。因此，這適用於大間隔的範圍證明。訣竅如下：根據拉格朗日定理，一個整數是正的當且僅當它可以分解為四個平方的和。因此，只需送出該分解的元素（可以有效地計算）並證明它們的平方和為 $ m $ . 需要未知階的組來確保我們確實在整數上工作：如果證明者不知道模數，他就不能執行模數歸約。此方法在本文中有所描述，並經過多次改進。據我所知，本文給出了最有效的恆定大小範圍證明的構造，這是我最近的作品之一。特別是，我們審查了現有的優化範圍證明並給出了新的結構，同時削弱了必要的安全假設。
選擇合適的方案現在取決於您，具體取決於以下幾點：
- 你願意使用帶有配對的橢圓曲線嗎？
- 你同意使用隨機預言模型來減少互動性參數嗎？
- 您是否可以使用額外的假設和一組未知順序，這可能需要額外的設置階段？
- 您必須執行多少次範圍證明？範圍證明可以批量化：使用本文和我的文章的組合允許執行 $ M $ 同時進行範圍證明，只產生一個 $ \sqrt{M} $ 高架。由於您似乎有許多這樣的範圍證明要執行，因此執行全域批量範圍證明可能會更好。
- 您將擁有的間隔的確切大小是多少？（有 $ q $ 大小為 256 位，如果使用橢圓曲線，或者說，如果使用素數階域的子組，則為 1024 位，可以更改適當的方法）
我的答案中沒有詳細解釋方法，會太長；您可以參考我包含的文章，或者如果其中一個似乎符合您的要求，請詢問特定方法的精度。