使用短向量在 Ajtai 的散列函式中查找衝突
背景
Ajtai 的雜湊函式是什麼？
給定一個矩陣 $ A \hookleftarrow U(\mathbb{Z}_q^{n \times m}) $ 和一個列向量 $ \vec{m} \in \mathbb{Z}_d^m $ , 消息的雜湊 $ \vec{m} $ 是（誰）給的
$ H(\vec{m}) = A\vec{m} \mod q $
Ajtai 的 SIS 格
對應的格子為 $ A $ 表示為 $ L^{\bot}(A) $ 被定義為所有向量 $ \vec{v} $ 這樣 $ A\vec{v}=\vec{0} $ ， 換句話說 $ L^{\bot}(A) $ 是核心_ $ A $ . 因此，據我了解，為 $ L^{\bot}(A) $ 本質上等於為 $ A $ .
SIS問題
這 $ \beta $ -SIS 問題是尋找非零向量的問題 $ \vec{v} $ 這樣 $ A\vec{v}=\vec{0} $ 和 $ |\vec{v}|\le \beta $ . 眾所周知，這個問題很難。
雜湊函式是否抗碰撞？
找到雜湊函式的衝突與解決 $ 2d\sqrt{m} $ SIS 問題。這意味著，給定一個碰撞 $ (\vec{x}, \vec{y}) $ 我們可以很容易地計算出一個短向量 $ L^{\bot}(A) $ 作為 $ \vec{x}-\vec{y} $ .
為什麼它有效？我們有一個碰撞，即 $ A\vec{x}=A\vec{y} \rightarrow A(\vec{x}-\vec{y})=\vec{0} $ , 所以向量 $ \vec{v}=\vec{x}-\vec{y} $ 在格子裡。接下來，由於三角不等式，我們有 $ |\vec{v}| \le |\vec{x}|+|\vec{y}| $ . 由於兩者 $ |x|{\infty} \le d $ 和 $ |y|{\infty} \le d $ ， 它遵循 $ |\vec{v}| \le 2d\sqrt{m} $ .
問題
現在，我的問題是；有可能反過來嗎？也就是說，給定一個短的非零向量，例如使用Lentra-Lenstra-Lovász 晶格縮減算法，是否有可能找到 Ajtai 散列函式的衝突？
它取決於散列函式的確切域和 SIS 解決方案的質量，即它的範數（以及範數本身的選擇）。
假設雜湊域是 $ {-d, \ldots, d}^m $ ，即，向量 $ \ell_\infty $ 最多規範 $ d $ . 那麼 Ajtai 格中的任何非零向量最多具有歐幾里得範數 $ d $ 與全零輸入衝突。（實際上， $ \ell_\infty $ 最多規範 $ d $ 就足夠了。）因此，找到足夠短的晶格向量會產生碰撞。
但現在假設 $ d=1 $ ， 說。（這是一個典型的選擇。）對於標準參數，Ajtai 格中的最短（歐幾里得範數）非零向量的範數約為 $ \sqrt{n \log q} \gg d = 1 $ . 因此，歐幾里得範數中的短向量（這是典型的格基約簡算法所提供的）可能不足以產生碰撞。相反，找到碰撞需要在 $ \ell_\infty $ 規範。但是對於這種設置的格基縮減算法知之甚少。
有關這些問題的更多詳細資訊，請參見論文“SWIFFT: A Modest Proposal for FFT Hashing”（我是合著者）。