This is the problem

Let $\mathcal{L}$ be a lattice and $v_1,v_2,\ldots,v_n\notin\mathcal{L}$. Given the values $a_1,\ldots,a_n$ such that

$$a_1=\lfloor v_1\rceil+v_2+\ldots+v_n$$ $$a_2=v_1+\lfloor v_2\rceil+\ldots+v_n$$ $$\vdots$$ $$a_n=v_1+v_2+\ldots+\lfloor v_n\rceil$$

where $\lfloor\cdot\rceil$ means projection to $\mathcal{L}$. Retreive $\Sigma:=\sum_{i=1}^{n}v_i$.

Paraphrasing, say Alice lets Bob know $\mathcal{L}$, the $a_i$'s and the way they're constructed (i.e. the system above). How hard it is for Bob to obtain $\Sigma$?

For instance, if Bob manages to obtain $v_j$ for some $j$, then he only needs to compute $\lfloor v_j\rceil$ and $a_j-\lfloor v_j\rceil+v_j$ to obtain $\Sigma$. Therefore, at this point, the secrecy of $\Sigma$ relies on the secrecy of the $v_i$'s and the CVP.

Of course obtaining all the $v_i$'s will give it away immediately avoiding CVP, but that seems hard at first glance.


  • $\begingroup$ It sounds an interesting problem, but I have a question, you mean that $ \lfloor v \rceil$ is the closet lattice points to $v$ right? But there may be many such lattice points, thus if $v_i$ satisfied that $ \lfloor v_i \rceil$ is unique, then the question is unambiguous. $\endgroup$ Apr 26 at 2:18
  • $\begingroup$ Sorry, I an wrong. More generally, You can interpret $\lfloor\cdot\rceil$ as some random algorithm. This problem is likely to be difficult in this sense, and it is likely to be easy in the sense mentioned above. $\endgroup$ Apr 26 at 2:44

1 Answer 1


The below is essentially a comment, but perhaps long for one.

There are a number of ways which this problem seems underspecified currently. For example, does one need to exactly obtain $\Sigma$, or is approximately obtaining it bad as well? One method to approximately obtain it is

$$\frac{\sum_i a_i}{n} = \Sigma + \frac{\sum_i v_i\bmod\mathcal{L}}{n}.$$

Here, $x\bmod\mathcal{L} := x - \lfloor x\rceil$. If $v_i$ is randomly sampled, under suitable assumptions of the underlying distribution (which are somewhat common), we will have that $\mathbb{E}[v_i\bmod\mathcal{L}] = 0$, and moreover $v_i$ is (at least close to) uniform on $\mathcal{V} = \{x\mid \lfloor x\rceil = 0\} = \mathbb{R}^m\bmod \mathcal{L}.$ Then $\frac{\sum_i v_i\bmod\mathcal{L}}{n}$ can be seen as an empirical/sample mean. By things like the Central Limit Theorem, it will be distributed as $\mathcal{N}(0, \sigma^2/n)$ for large-enough $n$, where $\sigma^2 = \mathsf{Var}[v_i\bmod\mathcal{L}]$. Therefore if $n\gg \sigma^2$, one starts to expect significant issues, even if we have to exactly obtain $\Sigma$. If we only have to approximately obtain $\Sigma$, the problem of course becomes significantly easier. This is to say that the hardness of your problem seems closely-related to the ratio $\sigma^2/n$. This makes sense --- when this quantity is small, $\lfloor x\rceil\approx x$, and $a_i\approx \Sigma$ already. When this quantity is large, this is no longer true.

Note that there are other potential issues as well, namely the pairwise differences $a_i - a_j = v_j\bmod\mathcal{L} - v_i\bmod\mathcal{L}$ are efficiently computable. This doesn't directly seem to cause issues, but it seems uncomfortably close to causing issues. If one can get many samples of $x\mapsto x\bmod \mathcal{L}$, one can

  1. use this to extract a description of $\mathcal{V}$, and then
  2. use this to construct an oracle for $\lfloor x\rceil$.

I believe this is (roughly) the content on the various "learning a hidden basis" papers, attacking things like GGH and NTRUSign.

Here, we don't precisely get samples of the form $x\mapsto x\bmod \mathcal{L}$. Instead, we get the weaker samples $(v_i, v_j)\mapsto v_i\bmod\mathcal{L} - v_j\bmod\mathcal{L}$. Perhaps this thwarts the previously-mentioned attacks, but it is not clear to me, and it is adjacent to something which is vulnerable to attacks.

Concretely, given enough samples (and under some assumptions), I expect an attacker to be able to learn $\mathcal{V} + \mathcal{V}$, where $A+B = \{a+b\mid a\in A, b\in B\}$. If somehow they can "divide by two", i.e. go from $2\mathcal{V} := \mathcal{V}+\mathcal{V}$ to $\mathcal{V}$, I expect there to be a straightforward attack on the proposal via constructing a CVP oracle for $\lfloor \cdot \rceil$. I won't look into this further myself, but it is a somewhat-concerning potential way to attack your proposed problem.

  • 1
    $\begingroup$ Thanks for writing what I wanted to say,I have the same opinion as you, and the paper of Ducas and Nguyen paper ''Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures'' is relevant $\endgroup$ Apr 27 at 11:38

Your Answer

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

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