如何在 Threshold Paillier 方案中計算 Lambda
我正在評估論文中描述的門檻值 Paillier 方案：
Ivan Damgard、Mads Jurik、Jesper Buus Nielsen，“Paillier 公鑰系統在電子投票中的應用”，2010 年，奧爾胡斯大學電腦科學系，金磚國家。
並且評估有問題 $ {\lambda_{0,i}^S} $ 在股份合併步驟中。
在論文中， $ {\lambda_{0,i}^S} $ 計算為：
$ {\lambda_{0,i}^S} = \Delta \displaystyle \prod_{i^{’} \in S \setminus i} \frac{-i}{i - i’} $ .
對於 S 秘密股份。
相同的計算方式 $ {\lambda_{0,i}^S} $ 在另一篇關於門檻值 Paillier 方案的論文中提到：
Ivan Damgard, Mads Jurik，“Paillier 機率公鑰系統的概括、簡化和一些應用。”，2001 年，第四屆公鑰密碼學實踐與理論國際研討會 Springer-Verlag 論文集。
不幸的是，價值 $ {\lambda_{0,i}^S} $ 如上所述並不能讓我正確組合股份。
有一個Paillier Threshold Encryption Toolbox計算 $ {\lambda_{0,i}^S} $ 用另一種方式：
$ {\lambda_{0,i}^S} = \Delta \displaystyle \prod_{i^{’} \in S \setminus i} \frac{-i’}{i - i’} $ .
我可以確認此版本按預期工作。這兩種方法給出了完全不同的值。例如，我們有 3 個解密伺服器：
使用第一種方法：
$ {\lambda_{0,1}^S} = 3 $ , $ {\lambda_{0,2}^S} = -24 $ , $ {\lambda_{0,3}^S} = 27 $
使用第二種方法：
$ {\lambda_{0,1}^S} = 18 $ , $ {\lambda_{0,2}^S} = -18 $ , $ {\lambda_{0,3}^S} = 6 $
有可能只是論文中的一個錯字，但我覺得不太可能。另一方面，在一個簡單的例子上嘗試兩種方法證明第二種方法給出了正確的解密，而第一種方法（來自論文的原文）沒有。
正確的計算方法是什麼 $ {\lambda_{0,i}^S} $ 在門檻值 Paillier 方案中合併股份的參數？我在這裡想念什麼？
<Enc,Dec>往返樣本：讓我們 $ p = 5 $ , $ q = 7 $ , $ p’ = 2 $ 和 $ q’ = 3 $ .
他們滿足 $ p = 2p’ + 1 $ 和 $ q = 2q’ + 1 $ .
$ n = pq = 35 $ , $ m = p’q’ = 6 $ .
解密伺服器的數量是 $ l = 3 $ 門檻值是 $ w = 3 $ .
我挑 $ d = 36 $ 這樣 $ d \equiv 0 (mod : m) $ 和 $ d \equiv 1 (mod : n) $
隱藏多項式表示為：
$ f(X) = {\displaystyle\sum_{i=0}^{w-1}} a_i X^i $
在哪裡
$ a_0 = d $
$ a_i $ 為了 $ 0<i<w $ 是一個隨機值 $ [0, nm) $
隨機挑選 $ a_1 $ 和 $ a_2 $ , 讓我們做
$ f(X) = 36 + 7x + 116x^2 $
秘密股份是：
$ s_1 = f(1) = 159 $
$ s_2 = f(2) = 94 $
$ s_3 = f(3) = 51 $
讓我們加密 $ M=29 $ .
加密文本 $ c $ 是：
$ c=(n+1)^M r^n : mod : n^2 $
在哪裡 $ r $ 是隨機選擇的 $ r \in Z_n $ . 讓我們使用 $ r = 19 $ 這給了我們：
$ c = (35 + 1)^{29} \ast 19^{35} : mod : 35^2 = 234 $
現在，既然我們有我們的秘密，我們可以嘗試解密它。我們首先需要對每個解密伺服器進行共享解密 $ i $ :
$ c_i = c^{2 \Delta s_i} $
在哪裡 $ \Delta = l! $ （解密伺服器總數的因子）和 $ s_i $ 是伺服器先前評估的秘密共享 $ i $
我們有 3 個加密伺服器，所以 $ \Delta = 3! = 6 $ .
然後將股份合併為 $ c’ $ 通過以下方式：
$ c’ = \Delta \displaystyle \prod_{i \in S} c_i^{2 \lambda_{0,i}^S} : mod : n^2 $
在哪裡 $ {\lambda_{0,i}^S} $ 是用前面討論的方法之一計算的。
我將在這裡使用一個小技巧。
自從 $ A^B : mod : C = (A : mod : C)^B : mod : C $
和 $ (AB) : mod : C = (A : mod : C \ast B : mod : C) : mod : C $
我們可以包括 $ mod $ 對每個解密的共享進行操作以避免創建大量數字。這邊走：
$ c_1 = 234^{2 \ast 6 \ast 159} : mod : n^2 = 1121 $
$ c_2 = 234^{2 \ast 6 \ast 94} : mod : n^2 = 771 $
$ c_3 = 234^{2 \ast 6 \ast 51} : mod : n^2 = 106 $
當我們使用論文中的方法時：
$ {\lambda_{0,i}^S} = \Delta \displaystyle \prod_{i^{’} \in S \setminus i} \frac{-i}{i - i’} $ .
$ {\lambda_{0,1}^S} = 3 $ , $ {\lambda_{0,2}^S} = -24 $ , $ {\lambda_{0,3}^S} = 27 $
$ c’ = 1156 $
當我們使用另一種方法時：
$ {\lambda_{0,1}^S} = 18 $ , $ {\lambda_{0,2}^S} = -18 $ , $ {\lambda_{0,3}^S} = 6 $
$ {\lambda_{0,i}^S} = \Delta \displaystyle \prod_{i^{’} \in S \setminus i} \frac{-i’}{i - i’} $ .
$ c’ = 386 $
（我沒有在任何地方找到此資訊，但我認為我們必須這樣做 $ abs(\lambda) $ 避免為負值創建分數，例如 $ -18 $ 或者 $ -24 $ .
如果我們解密消息：
$ M = 4 \Delta^2 \frac{c’ - 1}{N} : mod^{-1} N $
自從
$ c’ = (1+N)^{4 \Delta^2 M} $
我們會得到：
$ M = 17 $ 為了 $ c’ = 1156 $ 這是錯誤的。
和
$ M = 29 $ 為了 $ c’ = 386 $ 哪個是對的。
不幸的是，這是原始論文中的錯字。
在密鑰生成步驟中，私鑰 $ d $ 分為 $ l $ 分享使用 $ (w,l) $ -Shamir 秘密共享，即密鑰被拆分成 $ l $ 分享和重構關鍵需求 $ w $ 分享。
本質上，學位 $ w-1 $ 通過選擇生成隨機多項式 $ w-1 $ 隨機係數 $ a_{w-1},\ldots,a_1 $ 並設置 $ d $ 作為自由係數：
$$ f(x) = a_{w-1}x^{w-1}+a_{w-2}x^{w-2}+\cdots+a_1x+d $$ 那麼每一股 $ s_i=f(i) $ 為了 $ 1\le i\le l $ 注意到 $ d $ 本質上是 $ f(0) $ 可以使用拉格朗日插值從份額中計算出來。我們現在說 $ w $ 當局想要解密，他們總共有 $ w $ 出 $ l $ 分享。讓 $ S $ 是這些股票的一組索引，然後：
$$ f(0) = {\sum_{i\in S}} s_i \cdot \lambda_i(0) $$ 在哪裡
$$ \lambda_i(0) =\prod_{m\in S\setminus i} \frac{0- x_m}{x_i-x_m} $$ 另請注意，在生成共享時，索引被用作 $ x $ 值，即 $ x_m=m $ ， 所以
$$ \lambda_i(0) =\prod_{m\in S\setminus i} \frac{0- m}{i-m} $$ 如果你替換 $ m $ 和 $ i’ $ ， 你會得到
$$ \lambda_i(0) =\prod_{i’\in S\setminus i} \frac{- i’}{i-i’} $$ 這本質上是在另一個公式中，它給你正確的結果（ $ \lambda_{0,i}^S=\Delta\cdot \lambda_{i}(0) $ ).
解密是通過計算完成的：
$$ c’=\prod_{i\in S} c_i^{2\lambda_{0,i}^S}=\prod_{i\in S} c^{2\Delta s_i\cdot2\lambda_{0,i}^S}=\prod_{i\in S} c^{4\Delta^2 s_i\lambda_i(0)}= c^{4\Delta^2{\sum_{i\in S}} s_i \cdot \lambda_i(0)}=c^{4\Delta^2d} $$ 如您所見，私鑰 $ d $ 在指數中重建。