Damien Stehlé
unread,Jul 24, 2020, 11:58:23 AM7/24/20Sign in to reply to author
Sign in to forward
You do not have permission to delete messages in this group
Sign in to report message as abuse
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to pqc-forum, pqc-comments, Leo Ducas, Vadim Lyubashevsky
Dear Dan, everyone,
As far as we understand, the situation is as follows:
1. There is a worst-case to worst-case "everything-preserving" (i.e.,
noise, samples over Z_q, total dimension over Z) reduction from
Ring-LWE instances to Module-LWE ones,
2. There is an average-case to average-case reduction from Ring-LWE
to Module-LWE that is noise/total dimension preserving, but not
sample-preserving,
3. There is no known noise-preserving reduction of any kind going
the other way around (i.e., from Module-LWE to Ring-LWE),
4. There is no known "everything-preserving" average-case to
average-case reduction in either direction.
To sum up, there is no known reduction between Kyber and NewHope,
due to Item 4. However, Items 1 - 3 make it seem unlikely (at least to
us) that Module-LWE could be easier in practice for "natural" (e.g.,
uniform in bounded intervals) distributions that are not covered by the
reductions. This was one of the reasons why Module-LWE was chosen
for Kyber.
Best regards,
Damien, Léo, Vadim