# Is this problem based on a known hard problem?

Suppose I generated an $n$-dimentional vector $a_{(1)} = [a_1, \dotsc, a_n]$ with integer component (actually I can generate as many $a_{(i)}$ as possible). Now I need to get an vector $b = [b_1, \dotsc, b_n]$ such that $\langle a_{(i)}, b \rangle = c_{(i)}$, for all $i$. I don't know the value of $c_{(i)}$ but I can verify whether $c_{(i)}$ is correct (by an decryption algorithm which have $c_{(i)}$ as the key, like AES).

I want to know is this problem hard? If true, what hard problem it based on? I've read materials about knapsack problem, subset sum problem even integer programming. But I don't think they are match.

Edited on Dec 3, 2014: Allow me to modify question described above because it may be not meaningful. Now I have a group of equations $Ba = c$, where $B$ is an unknown matrix, $a$ and $c$ are known vectors. They are all $n$-dimensional (the previous question is one equation of this group, and I remove the restriction to $c$ because if I want to realize a better security, I need to assume that $c$ is known). So in group $1$, we have $$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)}$$

Now my question is:

1. As far as I know, if we have $n$ groups of $a^{(i)}$ and $c^{(i)}$ such that $Ba^{(i)} = c^{(i)}$, we can calculate $B$ easily. But what if we can get at most $n-1$ groups? I think there are infinite solutions, but can we recover part of $B$? Or all of the $\{b_{ij}\}$ are indeterminate? (Suppose $\{a^{(i)}\}$ are independent vector set.)
2. What if $B$ is an orthogonal matrix? How many groups are enough to recover $B$? And is it hard to calculate $B$ if $n$ is big?
• $<a,b>$ usually means the inner product. But that only really makes sense with vectors, not sets. Do you mean $a$ and $b$ are vectors? – Guut Boy Nov 30 '14 at 18:26
• It probably depends a lot on how you can test if $c$ is correct. If you check an incorrect $c$ does that reveal information on the real $c$. – Guut Boy Nov 30 '14 at 18:31
• @fgrieu I'm sorry I didn't clarified the notaions. $a$ and $b$ are indeed vectors, and $\langle a, b \rangle$ stands for the inner product. – JeffLee Nov 30 '14 at 20:20
• @GuutBoy I'm sorry I didn't clarified. The right notation is stated in the previous comment. $c$ is a key for a symmetric cipher like AES. I don't know if the incorrect key will reveal information. – JeffLee Nov 30 '14 at 20:27
• Well for starters the set of $a_i$ can't be linearly independent otherwise this amounts to solving an $i \times n$ system $Ab = c$ for $b$ with $A$ invertible. It can be solved in the rationals and then scaled to get an integer solution. And for linearly dependent $a_i$, I would imagine some partial solution could be obtained as well (if one exists) using the same techniques. Unless I am misreading the problem... – Thomas Nov 30 '14 at 21:14

This problem hugely depends on the distributions of the $c_{(i)}$, if they are independant or not, also on the size of the space in which each coordinate of the vectors are, and on the information you gain with each check if $c_{(i)}$ is correct.

Assuming the vector space is $Z_q^n$ and $n$ is polynomial in $\log q$, that $c_{(i)}$ are independant and uniformly distributed, and that your verification algorithm only tells you if $c_{(i)}$ is correct or not, let us look at the problem for one instance of $a$, $b$ and $c$.

If you take $b$ uniformly at random, you have probability $\frac{1}{q}$ to have $⟨a,b⟩=c$, which is exponentially small.

Moreover, there is no way to improve brute force on the value of $⟨a,b⟩$ because you don't learn anything beside the correctness of your $b$, so this is a problem you would call hard is cryptography. Even if you have a polynomial number of instances, this won't help you that much because finding a $b$ such that even only one $⟨a_i,b_i⟩=c_i$ is already exponentially hard.

Of course, this is an information theoretical approach to the complexity of this problem, and I think the real assumption you want to reduce to is one that would allow you to use my results, i.e. an assumption which makes you learn nothing when you verify $⟨a,b⟩=c$.

I know this is not really a reduction, but that's all I've got to help you, I hope it is enough.

Let me edit to reply to yours.

First, say you have $q$ groups of $a^{(i)}$ and $c^(i)$.

Now if you know $c$, you are just asking to solve a system of $qn$ linear equations with $n^2$ unknown. Now I think the subject is quite known and you can find a lot of documentation on it easily.

Remark that $B$ being an orthogonal matrix corresponds to adding $n$ equations to the system. Even though they are no more linear, I think the subject has already been studied.

As for the complexity questions, if I'm not wrong you can solve the problem with an algorithm running in time polynomial in $n$, so one would consider it easy.

• Thank you for your help. I think for a single equation, even if $c$ is known, to get b is still hard, is it? So I enlarged my quesion and hope you to help me again, regards. – JeffLee Dec 3 '14 at 11:03