基於格的簽名和雜湊
儘管存在許多不同的基於格的簽名方案，但雜湊和簽名簽名方案，如$$ GPV08 $$, 普遍存在。另一方面，眾所周知，抗碰撞雜湊函式可能是由格問題建構的 $$ SWIFFT08 $$. 但是，我從未見過將兩者結合起來的方案。為什麼？這樣的組合似乎很明顯，所以我想它的缺席是有充分的理由的。
你能幫我找出原因嗎？
詳情如下：
簡要地，$$ GPV08 $$類似的簽名可以在多項式環上實例化 $ \mathcal{R}_q = \mathbb{Z}_q[X]/\langle X^N+1 \rangle $ ，通過建立一個向量 $ \overrightarrow{\mathbf{a}} \in \mathcal{R}_q^k $ 帶活板門 $ t $ ，並通過對向量進行採樣來簽署消息 $ \overrightarrow{\mathbf{\sigma}} \in \mathcal{R}_q^k $ , 範數很小，這樣 $ \langle\overrightarrow{\mathbf{a}}, \overrightarrow{\mathbf{\sigma}}\rangle = H(m) $ ，在活板門的幫助下 $ t $ . 在哪裡 $ H(m) \in \mathcal{R}_q $ 是消息的雜湊 $ m $ 解析為多項式。簽名的驗證 $ \overrightarrow{\mathbf{\sigma}} $ 只是驗證 $ \langle\overrightarrow{\mathbf{a}}, \overrightarrow{\mathbf{\sigma}}\rangle = H(m) $ 並且規範 $ \overrightarrow{\mathbf{\sigma}} $ 是小。
另一方面，$$ SWIFFT08 $$雜湊函式族大致定義為 $ H_b(m)= \langle \overrightarrow{\mathbf{b}}, \overrightarrow{\mathbf{m}}\rangle $ ， 在哪裡 $ \overrightarrow{\mathbf{b}} \in \mathcal{R}_q^l $ 是一個均勻多項式向量，其係數為 $ \mathbb{Z}_q[X] $ 和 $ \overrightarrow{\mathbf{m}} \in \mathcal{R}_q^l $ 是一個消息多項式向量，係數在 {0,1}。所以消息空間是 $ 2^{ln} $ 位。
對於最多的消息 $ n $ 位，似乎將這兩種技術結合起來將是微不足道的，但我從未見過。有誰知道為什麼？
$$ Edit $$Lyubashevsky 等人，在他們的原始論文中$$ SWIFFT08 $$指出 SWIFFT 函式不適合用作隨機預言機，因為它們在加法下是同態的，可以用來構造區分器，但沒有提到簽名。事實上，鑑於其強大的抗碰撞特性，SWIFFT 函式似乎非常適合此目的。
Lyubashevsky 等人，在他們的原始論文中
$$ SWIFFT08 $$指出 SWIFFT 函式不適合用作隨機預言機，因為它們在加法下是同態的，可以用來構造區分器，但沒有提到簽名。
是的，但是這個同態屬性似乎仍然存在問題。即，對於 $ i\in[2] $ 讓 $ (\vec \sigma_i, \vec m_i) $ 是 SWIFFT 的簽名 $ \vec m_0, \vec m_1 $ 這樣 $ \vec m_0+\vec m_1\in{0,1}^{\ell n} $ . 然後， $ (\vec \sigma_0+\vec \sigma_1, \vec m_0+\vec m_1) $ 也將是有效的 SWIFFT 簽名。
如果我們用 SWIFFT 代替 $ H(\cdot) $ 在 Hash-and-Sign 簽名中，這意味著給定兩個 Hash-and-Sign 簽名滿足 $ \langle \vec a^0, \vec \sigma^0\rangle = H_b(\vec m_0) $ 和 $ \langle \vec a^1, \vec \sigma^1\rangle = H_b(\vec m_1) $ ，我們可以創建另一個 Hash-and-Sign 簽名滿足 $ \langle \vec a^0+\vec a^1, \vec \sigma^0+\vec \sigma^1\rangle = H_b(\vec m_0+\vec m_1) $ . 規範檢查是可能的 $ \vec \sigma^1+\vec \sigma^1 $ 會拒絕這種偽造，但似乎不太可能經常發生。
這就是說 SWIFFT 中的線性似乎直接啟用了 Hash-and-Sign（使用 SWIFFT 實例化）簽名的偽造。