Damien Stehlé writes:
> some type of Ring-LWE assumption
So, to be clear, the dividing line is whether a hardness assumption fits
within the parameter space of the LPR definition of "Ring-LWE"? E.g.:
* A proof for anything like Round5 or Saber would not qualify as
"enjoy a security proof that is analogous", because the starting
assumption is hardness of Ring-LWR/Module-LWR instead of Ring-LWE?
* If a scheme releases many overstretched Ring-LWE samples, and has a
proof based on the alleged hardness of this case of Ring-LWE, then
this would qualify as "enjoy a security proof that is analogous"?
This sounds very strange. Cryptanalysis indicates that the second
example is _much_ more dangerous than the first.
Are you sure this is what you meant by "enjoy a security proof that is
analogous to that of the LPR scheme"?
> due to the fact that the encryption procedure uses "LWE left hand
> sides" that are multiples of 3 (because of the rounding in the key
> generation procedure).
If you're really insisting on specifically Ring-LWE and not anything
rounding-based, then you're excluding all of the proposed LPR variants
that eliminate random errors in favor of deterministic rounding, such as
Round5 and Saber. This isn't specific to NTRU LPRime, and the main
technical point isn't new: the literature already makes clear that
"Ring-LWE hard => Ring-LWR hard" relies on irrelevant parameter choices.
Tweaking the key distribution in these pure rounding schemes doesn't
enable a proof from Ring-LWE, so I don't understand why you attribute
your ad-hoc exclusion of NTRU LPRime to details of the key distribution.
If I wanted to write down a list of proof requirements that allows
Round5 and Saber (and round-2 Kyber etc.) while disallowing NTRU LPRime,
I think I'd be able to, but stating the list clearly would also show how
unprincipled and artificial it is.
> Indeed, the main point of the LPR encryption scheme was to have a
> proof under the RingLWE hardness assumption.
What the LPR paper actually says that it is (1) "introducing an
algebraic variant of LWE" and (2) "proving that it too enjoys very
strong hardness guarantees. Specifically, we show that the ring-LWE
distribution is pseudorandom, assuming that worst-case problems on ideal
lattices are hard for polynomial-time quantum algorithms."
A closer look shows that these "guarantees" are for irrelevant
cryptosystem parameters. (I think https://eprint.iacr.org/2016/360
deserves the primary credit for this observation.) But then why should
Ring-LWE be treated as better than
* Ring-LWR, which has a proof "Ring-LWE hard => Ring LWR hard" for
* the "NTRU problem", which has a hardness proof for irrelevant
* a rounded-multiplier variant of Ring-LWE, which has a hardness
proof for irrelevant parameters; and
* a rounded-multiplier variant of Ring-LWR, which has a hardness
proof for irrelevant parameters?
I already asked for clarification of whether your "analogous" claim
would allow the first and second assumptions. You didn't answer. How
about the third and fourth assumptions?
(Disclaimer: I'm relying on claims that I've heard about these proofs.
I'm not saying that I've verified the proofs and theorem statements. I
try to keep my proof-verification efforts focused on proofs applicable
to relevant cryptosystem parameters.)
The underlying "worst-case problems on ideal lattices" have not been
holding up well to cryptanalysis. My understanding is that, for this
reason, you no longer endorse relying on the LPR "guarantee". But,
without this "guarantee", essentially nothing is left of LPR's
cryptosystem "proof"---it's simply the generic observation that
(1) one-wayness for the system's keys and ciphertexts follows from
(2) presumed indistinguishability of the keys from random and
(3) presumed one-wayness for ciphertexts for random keys,
modulo generic replacement of OW with IND. As I said before, this has
nothing to do with the specific structure of Ring-LWE, or with the
choice of distribution that parameterizes the word "random". Do you not
agree that all submissions "enjoy" such a proof?
> I am not going to discuss about topics that were not covered
> by the email of mine that started this thread.
You filed an "OFFICIAL COMMENT" dated 3 May 2019 20:27:01 +0200
claiming, among other things, that "NTRU LPRime does not enjoy a
security proof that is analogous to that of the LPR scheme".
The intended meaning of this claim is not clear. I have asked various
clarification questions, and I would like to hear your answers. If these
questions make you realize that the statement you made doesn't actually
have a meaning that you endorse, then you can withdraw the statement.
Of course the withdrawal itself needs to be specific and clear!
---Dan (speaking for myself)