2
$\begingroup$

I tried to understand how dense the Mod-LWR samples are in some space. I tried to see from a view similar to LWE, i.e. using GV-bound(maybe LPN is better example because GV-bound is for codes). But I have some difficulties with the parameters.

Take the Mod-LWR samples used in Saber as example: If the maximum number of Saber codes is denoted by $a$, and the minimum distance of linear code generated by $\operatorname{Gen}(\operatorname{seed}_A)$ is $d$, then we have the inequality as follows according to GV-bound: $$a\ge \dfrac {M^N}{\sum_{j=0}^{d-1}{N\choose j}(M-1)^j}$$ but what should $M$, $N$ be? I guess $M$ is a parameter meaning Saber code is equivalent to $M$-ary code, and $N$ is the equivalent code length, but I'm not sure. Or should I make an estimate of the code length by expanding the polynomial multiplication of a Mod-LWR sample?

$\endgroup$
4
  • $\begingroup$ Can you provide a reference for the analysis of LWE sample density using Gilbert-Varashamov? $\endgroup$
    – Daniel S
    Commented Mar 4 at 7:50
  • $\begingroup$ Sorry I haven't seen similar analysis. I just think GV bound is a measure of disjoint balls in some space, so that it can be used as a measurement of decoding hardness. I'm not sure whether my understanding is right or not, I'm quite new to this topic. If there's any mistakes, I'll edit the question. @DanielS $\endgroup$
    – Sharon
    Commented Mar 4 at 8:36
  • $\begingroup$ You are right about the usual interpretations of $M=q=alphabet~size$ and $N=n=codeword~length$ in the GV formula. $\endgroup$
    – kodlu
    Commented Mar 4 at 19:09
  • $\begingroup$ Thanks for your comment! @kodlu This sound reasonable. But I have a further question about the parameter $I=2,3,4$ which is the rank of the module and makes different security levels in Saber. Where should $I$ reside in this estimation? Will it have an effect on the minimum distance or something else? I have difficulties understanding the intuitive meanings of module rank in this system. $\endgroup$
    – Sharon
    Commented Mar 5 at 4:47

1 Answer 1

2
$\begingroup$

First, you're right that LPN is better. The GV bound is a "volume bound", where

$$\sum_{j=0}^{d-1}\binom{N}{j}(M-1)^j$$

is the volume of a Hamming ball of radius $d$ in $\mathbb{Z}/M\mathbb{Z}$. To see this, note that one can write

$$ \mathcal{B}(d) := \{\vec x\in(\mathbb{Z}/M\mathbb{Z})^N \mid \lVert \vec x\rVert_0 < d\} = \cup_{j = 0}^{d-1}\{\vec x\in(\mathbb{Z}/M\mathbb{Z})^N\mid \lVert \vec x\rVert_0 = j) $$

into the union of disjoint shells. Then, note that the volume of the $j$th shell is $\binom{N}{j}(M-1)^j$. This is because there are $\binom{N}{j}$ distinct locations to insert $j$ errors, and each error can take on $(M-1)$ different values.

In terms of this notation, we can note that if a code $\mathcal{C}\subseteq (\mathbb{Z}/M\mathbb{Z})^N$ has distance $d$, it means that

$$\mathcal{C} + \mathcal{B}(d)\subseteq (\mathbb{Z}/M\mathbb{Z})^N$$

is a partition. This is because given some noisy codeword $c + e$ for $e\in\mathcal{B}(d)$, one can uniquely decode back to $c$. In other words, there is a unique bijection with $\mathcal{C}+\mathcal{B}(d) \cong \mathcal{C}\times \mathcal{B}(d)$.

The GV bound then follows from taking volumes from the above (set) containment, e.g.

$$\mathsf{vol}(\mathcal{C}+\mathcal{B}(d)) \leq \mathsf{vol}((\mathbb{Z}/M\mathbb{Z})^N)\implies |\mathcal{C}|(\sum_{j=0}^{d-1}\binom{N}{j}(M-1)^j) \leq M^N$$

One can rewrite this to

$$ |\mathcal{C}| \leq \frac{M^N}{\sum_{j = 0}^{d-1}\binom{N}{j}(M-1)^j} $$ Note that the inequality is in the opposite direction of your claimed one.

To get your claimed inequality, we need to not investigate error-correcting codes (in the Hamming metric), but covering codes. In particular, we want $d$ to not be the minimum distance of our code, but instead the covering radius. This (can be) defined as the minimum $d$ such that

$$\mathcal{C}+\mathcal{B}(d) \supseteq (\mathbb{Z}/M\mathbb{Z})^N$$

In other words, it is the minimal $d$ such that any point $\vec x\in (\mathbb{Z}/M\mathbb{Z})^N$ can be decomposed into $c + e$ for $c\in\mathcal{C}, e\in\mathcal{B}(d)$. Such a decomposition need not be (and is not, unless $\mathcal{C}$ is a "perfect" code) unique. One can then use the same volume argument used before to get your desired inequality.

This is to say that your claimed inequality is

  1. in the Hamming metric, e.g. is closer to a LPN type bound, and
  2. is a bound on the covering radius of the code, not packing radius.

As for your second question

This sound reasonable. But I have a further question about the parameter $I=2,3,4$ which is the rank of the module and makes different security levels in Saber. Where should I reside in this estimation?

It doesn't have to reside anywhere. At a high level, an appropriate analogue of the above GV bound gives a worst-case bound on some lattice parameter, for all lattices. Module lattices are a special structured subset of lattices. In particular, they are additionally (standard) lattices, so a standard GV-type bound would hold as well.

One could give a refined GV-type bound for module lattices, where one would hope the module structure forces the GV bound to be tighter. There has been some work for this (say for example this, which is not a GV-type bound, but instead upper+lower bounds on the shortest vector of a "random" module lattice). I don't know if it is reasonable to expect an improvement for the GV bound for module lattices though. In particular, I expect that for module rank 1 lattices one can probably still get essentially the same minimum distance as you can for module rank $N$ lattices, but don't know a reference off the top of my head.

$\endgroup$

Your Answer

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

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