平均情況 SIS 和平均情況 BDD
在基於格的密碼學中，我們說平均情況SIS（短整數解）問題，因為它是這樣的問題” $ A \stackrel{$}{\leftarrow} \mathbb{Z}^{n\times m}{q} $ , 找到一個向量 $ s\in \mathbb{Z}^{m}{q} \backslash {0} $ 這樣 $ As=0 $ 和 $ ||s||\leq \beta $ "
但不是這樣的實例“ $ A \stackrel{$}{\leftarrow} \mathbb{Z}^{n\times m}{q} $ , 找到一個矩陣 $ B\in \mathbb{Z}^{m\times k}{q} \backslash {0} $ 這樣 $ AB=C $ 和 $ ||B||\leq \beta $ ”。後一種情況較為籠統，前一種情況只包括後一種情況。
同樣的情況也發生在 BDD（有界距離解碼）問題中。我們說 LWE 問題是一個平均情況問題，因為它只包含 BDD 問題的一些情況。
我理解正確嗎？
如果您願意，可以使用參數定義“一般 SIS 問題” $ (n,m,q, \beta) $ ，如下：我給你一個矩陣 $ A\in\mathbb{Z}_q^{n\times m} $ , 你必須找到一個非零向量 $ \vec x \in \mathbb{Z}_q^m $ 這樣 $ ||\vec x|| \leq \beta $ 和 $ A\cdot \vec x = \vec 0 $ .
矩陣 $ A $ 指定此一般 SIS 問題的一個實例。通過定義實例的方式，您可以獲得問題的不同變體 $ A $ 被選中。SIS 的平均案例硬度意味著當從一些實例分佈中隨機選擇實例時，假設很難（很有可能）找到上述問題的解決方案。這與最壞情況的硬度形成對比，後者將是（更弱的）假設問題在某些情況下難以解決 $ A $ .
現在，當我們談論 SIS 問題時，預設情況下，這指的是我上面描述的問題的推測平均情況硬度，其中實例上的分佈是均勻分佈 $ \mathbb{Z}_q^{n\times m} $ . 如果您喜歡將其視為更一般的 SIS 問題系列的特例，您可以將其視為一個特殊情況，其中可以考慮實例上不同分佈的平均情況硬度或最壞情況硬度。
然而，術語“平均情況”與以下事實無關，即 SIS 可以被視為一個更一般問題的特例，在這個問題中，人們試圖找到一個小範數矩陣 $ B $ 這樣 $ AB=C $ 而不是小範數向量 $ \vec x $ 這樣 $ A\vec x = 0 $ . 請注意，第一個也是眾所周知的（它詢問解決非同質 SIS 問題的幾個實例），如果我們定義 $ k $ 和 $ C $ 成為系統的參數。但這與術語平均情況無關 - 事實上，對於您考慮的更普遍的問題，您可以等效地討論平均情況硬度和最壞情況硬度。BDD 和 LWE 也是如此。