在 regev 方案中將消息解密為 MSB
我正在觀看這個FHE 影片，它將 Regev 加密方案定義為休閒：
驚魂：
- sk：選擇 $ t = (1,s)^t \in \mathbb{Z}_q^{n+1} $
- PK = $ A \in \mathbb{Z}_q^{m*(n+1)} $ 隨機除外 $ [A * t]_q $ 小的
**編碼：**隨機 $ r \in {0,1}^m $ 輸出和 $ \mu \in{0,1} $
- $ c \leftarrow (\mu,0,…,0).\frac{q}{2} + r.A $
**十二月：**計算 $$ \langle c,t\rangle = \mu.\frac{q}{2} + r.A.t = \mu.\frac{q}{2} + ; small ; (mod ; q) $$
- 解密 $ \mu $ 作為 MSB $ ([\langle c,t \rangle]_q) $
但我不明白解密是如何工作的？我認為例如 $ q = 8 $ 如果 $ [\langle c,t \rangle]_q \in [2,6) $ 消息為 1，如果 $ [\langle c,t \rangle]_q \in [6,8) \cup [0,2) $ 消息為 0（如果絕對值 small in $ \langle c,t\rangle $ 少一點 $ q/4 $ ）。我無法理解該消息將如何成為MSB $ ([\langle c,t \rangle]_q) $ ? 例如，如果我們對 0 和 3 的每個數字 MSb 都使用 3 位，則為 0。
編輯
回复@kelalaka 的回答。旁 $ q $ 奇怪的是，這很重要，但不是很讓我首先感到困惑的是Regev 論文的這一部分。**我認為當“小”**有界時你所說的是真的 $ 0<= small < q/2 $ . 例如對於 $ q = 7 $ 我們有類似的東西 $$ 000\001\010\\011\———\100\101\110 $$ 以及我什麼時候說的 $ -q/4<= small < q/4 $ 並且取決於您首先選擇的錯誤分佈。但仍然不確定。
**編輯2：**實際上這是一個愚蠢的問題。如果有人（可能性很小）遇到這個問題，以供將來參考。同態加密是影片中的人 Shai Halevi 的一篇好論文。在第 2.1 節符號和基本定義中，您可以找到 $ [;;]_q $ 以及更多。
您對 Regev 方案的定義有一些錯誤
註冊機（ $ 1^n $ ):
- sk：選擇 $ t = (1,s)^t \in \mathbb{Z}_q^{n} $ 在哪裡 $ q $ 是之間的質數 $ n^2 $ 和 $ 2n^2 $
- PK = $ B \in \mathbb{Z}_q^{m\times n} $ 隨機除外 $ [B \times t]_q $ “小的”
$ Encryption(B,\mu \in {0,1} $ : 隨機 $ r \in {0,1}^m $ 輸出和 $ \mu \in{0,1} $ $$ c \leftarrow (\mu,0,…,0) \cdot \frac{q}{2} + r \times B $$
$ Decrypt(c,t) $ : 計算
$$ \langle c,t\rangle = \mu \cdot \frac{q}{2} + r \times B \times t = \mu \cdot \frac{q}{2} + \text{ “small”} \pmod q $$
- 恢復 $ \mu $ 作為 MSB $ ([\langle c,t \rangle]_q) $
細節
- 密鑰是 $ n $ 維向量 $ \mathbb{Z}_q^{n} $ 第一個組件在哪裡 $ 1 $
- 公鑰是一個矩陣，除了當你與私鑰相乘時 $ t $ 你會有一個向量 $ q $ 散列小值 $ [B \times t]_q $
- 隨機的 $ r $ 是大小的位向量 $ m $ , $ r \in {0, 1}^m $ .
- 消息有點，是的，您要麼加密 $ \mu \in {0, 1} $ ，對於一個大小為的向量 $ n $ , $ (\mu,0,…,0) $
- 加密：
$$ c \leftarrow (\mu,0,…,0) \cdot \frac{q}{2} + r \times B $$
- 解密：
$$ \begin{align} \langle c,t\rangle &= \langle (\mu,0,…,0) \cdot \frac{q}{2} + r \times B ,t\rangle\ & = (\mu,0,…,0) \cdot \frac{q}{2} \times t + r \times B \times t \ & = (\mu \cdot \frac{q}{2},0,…,0) \times t + r \times B \times t \ & = \mu \cdot \frac{q}{2}+ r \times (B \times t) \end{align} $$
記住 $ [B \times t]_q $ 被選為“小”並且 $ r $ 是一個位向量。如果你考慮最後一個整數 $ \mod q $ .
$$ \mu \cdot \frac{q}{2} + \text{“small”} $$
調整開頭的“小”，使 $ r \times B \times t $ 永不超過 $ q/2 $ .
現在，在結果上呼叫 MSB 將提供 $ \mu $ 自從 $ \mu \cdot q/2 $ 使 MSB 0 或 1 取決於 $ \mu $ .
正確性
小項也稱為誤差 $ e $ 學期。正確性要求 $ |e| < \lfloor q/2 \rfloor /2 $
**注意：**我沒有去驗證這個例子，因為 $ q $ 工作這麼小。必須小心控制邊界。
下面的 sageMath 程式碼正在工作，但是，需要調整“小”，即左邊！
q = 129 # n^2 < 129 < 2n^2 R = IntegerModRing(q) n = 10 # vector size m = 10 # random vector size def randSecretKey(R, size): v = vector(R,sample(range(q), size)) v[0] =1 return v def randPublicKey(R,m,n): m2 = random_matrix(R,m,n) return m2 def randomBitVEctor(R,size): v = vector(R,[randint(0, 1) for i in range(size)]) return v def smallPKSK(R,m,n,sk,q): trials = 0 small = false while not small: trials += 1 inrange = true pk = randPublicKey(R,m,n) c = pk*sk for i in c: if i > 50: inrange = false if inrange == true: print( "number of =", trials) return pk def encodeMessage(R,bit,m): mu = zero_vector(R,m) mu[0] = bit return mu def encrypt(R, q, mu, r, B): return mu * R(64) + r * B def decrypt(R, c, t): return c*t sk = randSecretKey(R,n) print("\nsecret key = ", sk) pk = smallPKSK(R,m,n,sk,q) print("\nPublic key\n") print(pk) pk*sk r = randomBitVEctor(R,n) print( "r = " , r) mu = encodeMessage(R,1,m) print("mu = ",mu) c = encrypt(R, q, mu, r, pk) print("ciphertext = ",c) p = decrypt(R, c, sk) print("plaintext = ",p) Integer(p).digits(2)