同態加密和近似 GCD 問題混淆
注意：我昨天在 Math.StackExchange上問了這個問題，但沒有得到回答，所以我想我會在這裡重新發布它，希望得到答案
我正在閱讀同態加密和近似 GCD 問題，特別是第 23 頁的第 3.2 節，其中概述了基本加密方案：
使用者選擇一個大的奇數 $ p $ 成為系統的密鑰。
明文是一個比特 $ m $ . 加密消息 $ m\in{0,1} $ 並獲得密文 $ c $ , 使用者選擇 $ q,e \in\mathbb{Z} $ 獨立且隨機地從每個加密和計算的某個分佈中
$$ E(m,p) =qp+ 2e+m $$ 二進制大小 $ q $ 通常被選擇為大於二進制大小 $ p $ . 二進制大小 $ e $ ，稱為誤差，遠小於二進制大小 $ p $ . 稍後我們將討論這些參數的確切大小。
該系統的解密函式由下式給出
$$ D(c,p) = (c\mod p)\mod 2 $$ 查看解密函式對密文是否正確 $ c=qp+ 2e+m $ , 觀察到
$$ \begin{align}D(c,p) &= (qp+ 2e+m\mod p)\mod 2 \&= (2e+m)\mod 2\ &=m \end{align} $$ 請注意，要使其正常工作，我們需要
$$ \begin{align}2|e|+ 1&<\frac p2\|e|&<\frac p4−\frac 12\end{align} $$以便 $ (2e+m\mod p) = 2e+m $ .
但是，我正在努力解決的是，如果我們選擇 $ e<0 $ 然後
$$ \begin{align}2e+m\mod p &= (p-2|e|)+m\&\neq2e+m\end{align} $$根據模的定義（至少在最常見的程式語言中是這樣）：
$ a\mod b=r $ 在哪裡 $ a=qb+r $ 和 $ 0\leq r<b $
自從 $ p $ 被指定為奇數，那麼我們有
$$ \begin{align}&((p-2|e|)+m)\mod 2 \ &=((p\mod2)-((2|e|)\mod 2))+(m\mod 2)\mod 2\ &= ((1-0)+m)\mod2\tag{as $p$ is odd}\ &= (1+m)\mod 2\tag{as $m$ is either $1$ or $0$}\ &\neq m\end{align} $$ 我只是想了解我們為什麼指定
$$ |e|<\frac p4 - \frac 12 $$並不是$$ 0<e<\frac p4 - \frac 12 $$ 據我了解，解密不起作用
$$ \begin{align}0<-e&<\frac p4 - \frac 12\ \frac 12 - \frac p4 < e &< 0 \end{align} $$
例子
選擇 $ p=1583 $ , $ q=52498 $ ， 然後 $ |e|<\frac{1583}{4}-\frac 12 = 395.25 $ 所以選擇 $ e=-241 $
為了 $ m=1 $ ， 我們有
$$ \begin{align}c&=52498\times 1583+2\times (-241)+1\ &= 83104334-482+1\ &= 83103853\end{align} $$ 我們解密如下
$$ \begin{align}D(c,p)&=(c\mod p)\mod 2\ &= (83103853\mod 1583) \mod 2\ &= 1102 \mod 2\ &= 0\ &\neq m=1\end{align} $$ 我們可以看到
$$ \begin{align}(c\mod p) &= 1102\ &= (2\times 550.5) + 1\end{align} $$和 $ 550.5 > 395.25 $ 不滿足約束 $ |e| $
有人可以確認我的邏輯是正確的，還是請向我解釋它在哪裡崩潰了。
參考連結在其符號部分（第 vii 頁）中聲明：
$ a\bmod p;; $ 表示減少 $ a $ 模組 $ p $ 進入區間 $ (-p/2, p/2] $
因此定義 $ \bmod $ 使用的是非標準的
$$ (a\bmod p)=r;\iff;p\text{ divides }a-r;\text{ and };-p<2r\le p $$ 這可以看作是偏移量 $ a $ 從最近的倍數 $ p $ （最近選擇較低的作為決勝局），正如評論所建議的那樣。
這可以程式為
r = ((a + (p-1)/2) % p) - (p-1)/2，確保
- 事物被評估為有符號整數（在 C 中可能需要對 unsigned 進行一些顯式轉換
p）；- 添加
(p-1)/2不會導致溢出。