3
$\begingroup$

In my cryptographic scheme, I would like to rely on the hardness or negligibility of the following problem or situation, respectively. Note the original motivation: it shall be impossible to find two distinct ways how to sum up $n$ random strings $r_i$ into the same value, no modulo and limited number of additions (follows from overflow prevention in a somewhat homomorphic scheme), i.e., $\sum_{i=1}^n w_{1,i} r_i = \sum_{i=1}^n w_{2,i} r_i$ with limited non-negative integer coefficients $w_{\{1,2\},i}$.

Problem

Given a $\lambda$-bit random oracle (RO) with answers interpreted as (positive) integers and stored in a vector $\bf r$, either find an integer vector $\bf w \neq 0$ s.t. ${\bf w \cdot r }= 0$ and $\lVert{\bf w}\rVert_1 < 2^\nu$ where $2^\nu \ll 2^\lambda$, or answer that such a vector does not exist.

In practice, consider $\lambda \sim 128$, $\nu \sim 32$.

Thoughts

Without the $L_1$-norm limitation, the problem is fairly easy. Indeed, ${\bf w^{(1)}} = (\frac{r_2}{GCD(r_1,r_2)}, -\frac{r_1}{GCD(r_1,r_2)}, 0, \ldots, 0)$ is a "small" solution.

Further note that the (linearly independent) system ${\bf w^{(k)}} = (0, \ldots, 0, \frac{r_{k+1}}{GCD(r_{k},r_{k+1})}, -\frac{r_{k}}{GCD(r_{k},r_{k+1})}, 0, \ldots, 0)$, $k=0, \ldots, n-1$, constitutes a basis of a lattice $\bf W$ where each point $\bf w$ solves $\bf w \cdot r = 0$. It is commonly believed that the problem of finding a vector short-enough with respect to the shortest one in $\bf W$ is hard on average, known as the Shortest Vector Problem (SVP).

However, in this situation, we do not even know how long the shortest vector is, i.e., whether it fits the $L_1$ condition.

Also note that, on the one hand, querying the RO increases the chance of existence of such a solution, on the other hand, the problem of finding it becomes harder.

Ultimate Goal

Prove that either

  • existence of such a solution is negligible, or
  • finding such a solution is hard.

Question

Is there any known problem or a research area that would give at least a hint for my problem? Currently, SVP appears to me to be the closest one, however, it does not appear to be sufficient.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.