矩陣密鑰交換

給定的是一個方陣 $ M $ 在一個領域 $ F $ ，我們有以下條件的密鑰交換：

1. 人 $ X $ 向人發送消息 $ Y $ : $ C_{1}=AM $ ， 在哪裡 $ A $ 是一個隨機選擇的方陣。
2. 人 $ Y $ 向人發送消息 $ X $ : $ C_{2}=MB $ ， 在哪裡 $ B $ 是一個隨機選擇的方陣。
3. 兩者都可以計算密鑰 $ K=AMB $ .

問題是如何找到 $ K $ 在矩陣環大小的多項式時間內不知道 $ M $ ，或者證明給定協議的安全性。

有人可以幫我解決這個問題嗎？我真的被它困住了，沒有辦法解決它。

一個觀察結果是，如果我們修改問題，使得 $ M, A, B $ 是隨機可逆矩陣，則很容易證明系統的安全性。事實上，我們可以證明系統是資訊安全的；也就是說，對於任何觀察到的 $ C_1, C_2 $ 對，對於任何可能的值 $ K $ ，有一組唯一的值 $ A, B, M $ 這會產生 $ K $ （因此攻擊者沒有從 $ C_1, C_2 $ 對關於哪些值 $ K $ 更有可能）。當然，如果那個具體的值 $ M $ 在任何其他上下文中重用，您將失去此資訊安全性。

現在，最初的問題是關於選擇隨機矩陣而不考慮它們的可逆性。我會把這個留給你解決：如果 $ M, A $ 或者 $ B $ 是不可逆的，攻擊者可以在多大程度上利用它來恢復 $ K $ （或者，更確切地說，限制可能的值 $ K $ 也許能夠承擔）？

引用自：https://crypto.stackexchange.com/questions/11486