# Hardness or negligibility of finding small non-trivial addition coefficients for random values to sum to zero

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.