如何確定一個元素是否是 NTRU 加密方案中的公鑰？
首先，我使用https://en.wikipedia.org/wiki/NTRUEncrypt的設置， $ L_f $ 多項式的集合 $ d_f+1 $ 係數等於 1， $ d_f $ 等於 $ -1 $ 和剩下的 $ N-2d_f-1 $ 等於 0；和 $ L_g $ 多項式的集合 $ d_g $ 係數等於 1， $ d_g $ 等於 $ -1 $ 和剩下的 $ N-2d_g $ 等於 0。自然數 $ d_f $ 和 $ d_g $ 只是方案的固定參數。
假設一個人收到一個多項式 $ h $ 在環中 $ R_{N,q}=\mathbb{Z}_q[X]/\langle X^N-1 \rangle $ .
問題：是否可以確定是否 $ h $ 是一個公鑰，也就是說，是否有可能確定是否 $ h $ 是形式 $ pf_q \cdot g \pmod{q} $ ?
我的嘗試：NTRU 硬度假設表明，從 $ h $ 無法確定 $ f $ 或者 $ g $ ，否則該方案將毫無用處。雖然我無法回答我的問題，但我想出了一個測試。自從 $ g(1)=0 $ , 我們必須有 $ h(1)=0 $ . 因此，如果 $ h(1) \neq 0 $ 然後 $ h $ 不是公鑰。我們還可以測試什麼？
PS：從源頭上沒有零知識證明或類似的東西 $ h $ 給出。
您不能在稱為“決定性 NTRU 假設”的標准假設下。這本質上是 NTRU 公鑰是偽隨機的聲明。以下是A Decade of Lattice Cryptography 的定義 4.4.4。
NTRU 學習問題：對於可逆 $ s\in R_q^* $ , 和分佈 $ \chi $ 上 $ R $ ， 定義 $ N_{s, \chi} $ 成為輸出的分佈 $ e/s\in R_q $ 在哪裡 $ e\gets\chi $ . NTRU 學習問題是：給定獨立樣本 $ a_i\in R_q $ ，其中每個樣本根據任一分佈
- $ N_{s,\chi} $ , 對於一些隨機選擇的 $ s\in R_q^* $ （對所有樣本都固定），或
- 均勻分佈，區分哪種情況（具有不可忽略的優勢）。
請注意，此問題實質上表明您無法按照您的要求進行操作，即表明 NTRU 密鑰在計算上與隨機密鑰無法區分。