0
$\begingroup$

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?
$\endgroup$
  • $\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 Nov 30 '14 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 Nov 30 '14 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 Nov 30 '14 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 Nov 30 '14 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 Nov 30 '14 at 21:14
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\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 Dec 3 '14 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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