can this estimator evaluate the security of LWR ( learning with rounding ) problem as a variant of LWE problem ?

[1853582]

Hello, can this estimator evaluate the security of LWR ( learning with rounding ) problem as a variant of LWE problem ? Since some cryptographic schemes are constructed based on the LWR problem, I want to make a security evaluation of such schemes.

Banerjee A, Peikert C, Rosen A. Pseudorandom functions and lattices[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 719-737.

[1853582]

The LWR problem is a variant of LWE. The difference is that the Gaussian noise is replaced by rounding computation.

[bencrts]

Hi @1853582!

One way to do this is to model the LWR instance as an LWE instance with uniform errors in {-q/2p + 1, ..., q/2p}. See ND.Uniform() located here. So, in your parameter set you would use Xe = ND.Uniform(-q/2p + 1, q/2p).

[1853582]

Thank you for your answer. Could you be more specific ? For example, I want to test the security of the following scheme, for here ( m, n, p, q ), to measure the security of the LWR problem.

[1853582]

But I seem to be wrong here ?

[1853582]

May I ask how to evaluate the security of this, please.

[bencrts]

In Sage, you need to use 2*p, instead of 2p. So, in your code you would need to change -q/2p to -q/(2*p) (and similarly for the positive one).

[1853582]

Thank you again for your answer. I have modified the code for testing and found that there is a problem with data overflow：

When I modify smaller p and q, the code cannot output results How should this be resolved? Thank you for answering my question in your busy schedule.

[1853582]

In fact, this does not match the estimate results mentioned in the paper I saw. The paper also claims to use LWE estimator, but the results are different. It seems that he used a different estimation method?

Ernst J, Koch A. Private Stream Aggregation with Labels in the Standard Model[J]. Proc. Priv. Enhancing Technol., 2021, 2021(4): 117-138.

[1853582]

May I ask how to evaluate this? Thank you for taking the time to answer my question.

[1853582]

In Sage, you need to use 2*p, instead of 2p. So, in your code you would need to change -q/2p to -q/(2*p) (and similarly for the positive one).

Can you give an example of a code running? I‘m sorry to bother you, I need a security analysis of this part at present.