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}$.


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$.


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.


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.


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.