Analyzing subrings for some R-LWE and NTRU instances

[Zhenfei Zhang]

Hi list,

Inspired by the ABD16 subfield attack against over-stretched NTRU, I started to look into
NTRU and R-LWE where there exist nice sub-rings. There seems to be some subrings
with really nice property. At the moment I am not able to find any successful attacks.
However, it seems to be an interesting idea, and I think it is worth putting "this is what I
tried, and it didn't work" into a report.

I would appreciate your comments. Please let me know if it has been shown in the literature,
in particular, if there is some more abstract or high level view of exploiting the subrings. I
would also love to see if there are any tricks to carry the attack further.

Thanks for your time!

Regards,
Zhenfei Zhang
Security Innovation.

[Ian M]

Zhenfei,

 

I've been reviewing the invited talk at PQCrypto 2016 given by Steven Galbraith.  He outlines his proposal for modulus switching related to LWE and SIS problems.  He does glance over binary secrets, preferring not to discuss it after mentioning modulus switching related to hardness of LWE.  The link to this talk is at the end of this message.

My reading of your paper focuses mostly on the section covering binary secrets of R-LWE.  One of your main findings is that the loss of SVP from the original ring mapped to the sub-ring implies that modulus switching attacks are potentially impossible.  You also base this claim on the closeness of shortest non-zero vectors to the Gaussian heuristic length for cases in which the shortest vector problem is preserved.

Intuitively, this largely makes sense to me.  A change in coordinate systems implies a change in the domain of shortest vectors.

In your demonstration of modulus switching, you use an instance of R-LWE in the integer ring mod q, where modulus q is one plus a multiple of 2N.  Your mod switch is then to Q, where mod Q is a modulus w.r.t "power of 2."  By using these switch techniques you show that the shortest vector is largely lost in the mapping from the integer ring to the sub-ring, but I'm wondering if you've included any methods to account for the change in dimensions that might preserve the vector?  You account for the Gaussian heuristic length when the shortest non-zero vector is preserved, but does any possible use of a Gaussian heuristic length help preserve the shortest non-zero vector in mappings where the shortest vector is not shown preserved?

 

To rephrase my question, can a Gaussian heuristic help attenuate for loss of shortest vectors in mappings from the original ring to the sub-ring?  Would including the cross-rounding function help achieve this goal?

Regards,

Ian

 

Mod Switch and Binary Secrets mentioned by Steven Galbraith (18:00 minutes in).

https://youtu.be/xpBEgT9xyk8?t=18m5s 

[Ian M]

 Apologies, the range changes, not the domain.

[Zhenfei Zhang]

Hi Ian,

Thanks for the feedback.

> I've been reviewing the invited talk at PQCrypto 2016 given by Steven Galbraith.  He outlines his proposal for modulus switching related to LWE and SIS problems.  He does glance over binary secrets, preferring not to discuss it after mentioning modulus switching related to hardness of LWE.  The link to this talk is at the end of this message.

Thank you for the pointer. I have also been informed off-line that modulus switching is routinely used in estimating parameters for LWE:

- Albrecht, M. R., Jean-Charles Faug\`ere, Fitzpatrick, R., & Perret, L.
  (2014). Lazy modulus switching for the BKW algorithm on LWE.

- Albrecht, M. R., Player, R., & Scott, S. (2015). On The Concrete
  Hardness Of Learning With Errors.

> I'm wondering if you've included any methods to account for the change in dimensions that might preserve the vector?

No I don't. The analysis in the paper is based on individual cases.

I find the optimal dimension by trying most combinations.

I would love to see if there is a systematical way to find the optimal dimension

(which is one of the reason of this post).

> To rephrase my question, can a Gaussian heuristic help attenuate for loss of shortest vectors in mappings from the original ring to the sub-ring?  Would including the cross-rounding function help achieve this goal?

Sorry I don't really know any technique that achieves your goal.

Cheers,

Zhenfei

On Tue, Feb 21, 2017 at 11:48 PM, Ian M <iama...@utica.edu> wrote:

 Apologies, the range changes, not the domain.

--
You received this message because you are subscribed to a topic in the Google Groups "Cryptanalytic algorithms" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/cryptanalytic-algorithms/lSfA45mITRE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to cryptanalytic-algorithms+unsub...@googlegroups.com.
To post to this group, send email to cryptanalytic-algorithms@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cryptanalytic-algorithms/21c98cb1-ef8d-4ce2-9448-442cde8fcfe1%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Ian M]

Zhenfei, et al.

This is a response to our conversation involving length-preserving short vectors between dimensions.

>>> I'm wondering if you've included any methods to account for the change in dimensions that might preserve the vector?

>No I don't. The analysis in the paper is based on individual cases.

>I find the optimal dimension by trying most combinations. 

>I would love to see if there is a systematical way to find the optimal dimension

>(which is one of the reason of this post).

I wonder if a Dedekind cut would be useful?  It may be possible to have sets (A,B) as subrings where A and B are posets.  If this holds, it should be possible to derive a completion of A or B defined as a complete lattice.  Since this requires a monotone function, it could be possible to use a Galois connection.  The meet and join operators of lattices can be treated as the lower and upper adjoints of a diagonal map.  Using this method, you could treat the subrings as posets while preserving order for embedding after a modulus switch.

By relying on the order embedding of the Galois connection, you might be able to preserve the shortest vector by maintaining the order of each poset.  This could potentially help moving to and from the sub-ring.

Thoughts?