NTRU 中的消息擴展：為什麼會這樣日誌p(q)日誌p(q)log_p(q)-至-111?
假設我們正在使用帶參數的原始版本 NTRU $ (N,p,q,k,d_f,d_g,d_\phi) $ .
在這種情況下，我們正在使用帶有數字信封和參數的原始 NTRU $ k $ 如下所述。
假設我們加密了一條消息 $ m $ 那是在 $ \frac{\mathbb{Z}[X]}{\langle X^N-1 \rangle} $ .
回顧 $ m $ 之間有係數 $ -\frac{1}{2}(p-1) $ 和 $ -\frac{1}{2}(p-1) $ 最多有學位 $ n-k-1 $ .
那麼密文就是 $ e=p\phi \circledast h + m $ .
據說消息擴展等於 $ \frac{n}{n-k}\log_p(q) $ -至- $ 1 $ .
有人可以幫我解釋為什麼我們有這種平等嗎？我不太明白在這種情況下所謂的“消息擴展”……
提前致謝。
我猜你是從這個文件中獲取這些資訊的。
在第 2.1 節中，您可以看到不同大小的表格。特別是，明文塊（即編碼消息）具有大小 $ (n-k) \log_2 p $ 位，而密文有大小 $ n \log_2 q $ 位。解釋很簡單：密文實際上是多項式 $ n $ 條款（因為程度是 $ n-1 $ )，其中每個係數可以表示為 $ \log_2 q $ 位，而編碼的消息是多項式 $ n-k $ 條款（因為程度是 $ n-k-1 $ )，其中每個係數可以表示為 $ \log_2 p $ 位。
現在，“消息擴展”（也稱為“密文擴展”）只是密文大小與明文大小之間的比率。換句話說，它表示密文相對於原始消息增加了多少。理想情況下，出於顯而易見的原因，您不希望它過度擴展，儘管可以證明必須存在一些擴展才能使加密在語義上安全（在公鑰方案的情況下，如 NTRU）。在這種情況下，它是 $ \frac{n \log_2 q}{(n-k) \log_2 p} $ . 最後，根據對數的性質，我們有 $ \frac{\log_2 q}{\log_2 p} = \log_p q $ , 所以最終的消息展開是 $ \frac{n}{n-k}\log_p q $ .