這個問題是基於一個已知的難題嗎？
假設我生成了一個 $ n $ 維向量 $ a_{(1)} = [a_1, \dotsc, a_n] $ 帶有整數分量（實際上我可以生成盡可能多的 $ a_{(i)} $ 盡可能）。現在我需要得到一個向量 $ b = [b_1, \dotsc, b_n] $ 這樣 $ \langle a_{(i)}, b \rangle = c_{(i)} $ ， 對全部 $ i $ . 我不知道的價值 $ c_{(i)} $ 但我可以驗證是否 $ c_{(i)} $ 是正確的（通過具有 $ c_{(i)} $ 作為密鑰，如 AES）。
我想知道，這個問題難嗎？如果屬實，它基於什麼難題？我已經閱讀了有關背包問題、子集和問題甚至整數規劃的材料。但我不認為他們匹配。
2014 年 12 月 3 日編輯：請允許我修改上述問題，因為它可能沒有意義。現在我有一組方程 $ Ba = c $ ， 在哪裡 $ B $ 是一個未知矩陣， $ a $ 和 $ c $ 是已知的向量。他們都是 $ n $ -維（上一個問題是該組的一個方程，我刪除了對 $ c $ 因為如果我想實現更好的安全性，我需要假設 $ c $ 已知）。所以在群裡 $ 1 $ ， 我們有 $$ Ba^{(1)} = \left[ \begin{array}{cccc} b_{11} & b_{21} & \cdots & b_{1n}\ b_{21} & b_{22} & \cdots & b_{2n}\ \vdots & \vdots & \ddots & \vdots\ b_{n1} & b_{n2} & \cdots & b_{nn} \end{array} \right] \cdot \left[ \begin{array}{c} a_1\ a_2\ \vdots\ a_n \end{array} \right] = \left[ \begin{array}{c} c_1\ c_2\ \vdots\ c_n \end{array} \right] = c^{(1)} $$
現在我的問題是：
- 據我所知，如果我們有 $ n $ 團體 $ a^{(i)} $ 和 $ c^{(i)} $ 這樣 $ Ba^{(i)} = c^{(i)} $ ，我們可以計算 $ B $ 容易地。但是如果我們最多能得到呢？ $ n-1 $ 團體？我認為有無限的解決方案，但我們可以恢復部分 $ B $ ? 或者所有的 $ {b_{ij}} $ 是不確定的？（認為 $ {a^{(i)}} $ 是獨立向量集。）
- 如果什麼 $ B $ 是正交矩陣嗎？多少組才能恢復 $ B $ ? 是不是很難計算 $ B $ 如果 $ n $ 大嗎？
這個問題很大程度上取決於 $ c_{(i)} $ ，如果它們是獨立的，還取決於向量的每個座標所在的空間大小，以及每次檢查時獲得的資訊是否 $ c_{(i)} $ 是正確的。
假設向量空間是 $ Z_q^n $ 和 $ n $ 是多項式在 $ \log q $ ， 那 $ c_{(i)} $ 是獨立且均勻分佈的，並且您的驗證算法僅告訴您是否 $ c_{(i)} $ 正確與否，讓我們看一個實例的問題 $ a $ , $ b $ 和 $ c $ .
如果你拿 $ b $ 均勻隨機，你有機率 $ \frac{1}{q} $ 具有 $ ⟨a,b⟩=c $ ，它是指數級的小。
此外，沒有辦法提高蠻力的價值 $ ⟨a,b⟩ $ 因為除了你的正確性之外，你什麼也學不到 $ b $ ，所以這是一個你會稱之為困難的問題是密碼學。即使您有多項式的實例，這也對您沒有太大幫助，因為找到一個 $ b $ 這樣即使只有一個 $ ⟨a_i,b_i⟩=c_i $ 已經是指數級的困難。
當然，這是解決這個問題複雜性的一種資訊理論方法，我認為您想要簡化的真正假設是允許您使用我的結果的假設，即當您驗證時讓您一無所獲的假設 $ ⟨a,b⟩=c $ .
我知道這並不是真正的減少，但這就是我能幫助你的全部，我希望這已經足夠了。
讓我編輯來回复你的。
首先，說你有 $ q $ 團體 $ a^{(i)} $ 和 $ c^(i) $ .
現在如果你知道 $ c $ ，你只是要求解決一個系統 $ qn $ 線性方程組 $ n^2 $ 未知。現在我認為這個主題是眾所周知的，你可以很容易地找到很多關於它的文件。
請注意 $ B $ 作為正交矩陣對應於添加 $ n $ 系統的方程。即使它們不再是線性的，我認為這個主題已經被研究過了。
至於復雜性問題，如果我沒記錯的話，您可以使用在時間多項式中執行的算法來解決問題 $ n $ ，所以人們會認為這很容易。