Suppose I generated an $n$-dimensional 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 is it based on? I've read materials about the knapsack problem, subset sum problem even integer programming. But I don't think that they match.

Edited on Dec 3, 2014: Allow me to modify the question described above because it may not be 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 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?
  • $\begingroup$ $<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? $\endgroup$
    – Guut Boy
    Commented Nov 30, 2014 at 18:26
  • $\begingroup$ 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$. $\endgroup$
    – Guut Boy
    Commented Nov 30, 2014 at 18:31
  • $\begingroup$ @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. $\endgroup$
    – JeffLee
    Commented Nov 30, 2014 at 20:20
  • $\begingroup$ @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. $\endgroup$
    – JeffLee
    Commented Nov 30, 2014 at 20:27
  • $\begingroup$ 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... $\endgroup$
    – Thomas
    Commented Nov 30, 2014 at 21:14

1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$
    – JeffLee
    Commented Dec 3, 2014 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.