否定結果的 Paillier 減法
我想弄清楚Paillier的減法。
從我目前讀到的，給定 $ m_1 $ 小於 $ m_2 $ ( $ m_1<m_2 $ ) 我可以計算 $ E(m_2-m_1) $ 作為 $ E(m_2)\cdot E(m_1)^{-1} $ 在哪裡 $ E(m_1)^{-1} $ 生產 $ -m_1 $ 解密時。
我不清楚的是我是否可以計算 $ E(m_1-m_2) $ 解密時應該導致負數。
在Pailler 加密中，它適用於所有消息 $ m_1 $ 和 $ m_2 $ ，以及任何隨機數$$ * $$被加密使用，即：
$$ \begin{align} (m_1+m_2\bmod n)&=D(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\ (m_1-m_2\bmod n)&=D(E(m_1)\cdot E(m_2)^{-1}\bmod n^2) \end{align} $$ 其中模逆 $ E(m_2)^{-1} $ 是模計算的 $ n^2 $ ，即在 $ \Bbb Z_{n^2}^* $ . 如果 $ 0\le m_2\le m_1<n/2 $ 那麼我們有
$$ \begin{align} m_1+m_2&=D(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\ m_1-m_2&=D(E(m_1)\cdot E(m_2)^{-1}\bmod n^2) \end{align} $$ 當標誌 $ m_1-m_2 $ 是未知的，我們可以定義一個修改後的 Pailler 密碼系統。加密不變，或者/我們可以計算 $ E(m) $ 作為 $ E(m\bmod n) $ 什麼時候 $ m $ 是負數。解密修改為 $ D’(c)=[D(c)]_n $ 根據定義 $ [x]_n=((x+\lfloor n/2\rfloor)\bmod n)-\lfloor n/2\rfloor $ .
隨便隨便$$ * $$被加密使用，如果 $ -n/2<m<n/2 $ ， 然後 $ D’(E(m))=m $ ; 對於所有消息 $ m_1 $ 和 $ m_2 $ :
$$ \begin{align} [m_1+m_2]_n&=D’(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\ [m_1-m_2]_n&=D’(E(m_1)\cdot E(m_2)^{-1}\bmod n^2) \end{align} $$ 如果 $ -n/4<m_1<n/4 $ 和 $ -n/4<m_2<n/4 $ 那麼我們有 $$ \begin{align} m_1+m_2&=D’(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\ m_1-m_2&=D’(E(m_1)\cdot E(m_2)^{-1}\bmod n^2) \end{align} $$ 我找不到誰首先將 Paillier 加密擴展到減法，或/和使用該變體的簽名值 $ [x]_n $ 的 $ x\bmod n $ 操作員; 但這很簡單和自然，我猜它已經被獨立重新發現了好幾次。符號 $ [x]_n $ 經常用於同態加密，至少自 Craig Gentry 和 Shai Halevi實施 Gentry 的全同態加密方案以來（ Eurocrypt 2011 論文集的擴展摘要）。
$$ * $$限制隨機整數 $ r\in\big[0,n^2\big) $ 被加密用來互質 $ n $ ; 如果 $ n $ 很難考慮。