New "latticeproofs" survey paper

[D. J. Bernstein]

I have a new paper "Comparing proofs of security for lattice-based
encryption" available:

https://cr.yp.to/papers.html#latticeproofs

This paper gives a systematic, unified presentation of what is achieved
by known proof strategies for the 36 KEMs proposed for wide use (aiming
for IND-CCA2, not just IND-CPA) in the Frodo, Kyber, LAC, NewHope, NTRU,
NTRU Prime, Round5, Saber, and ThreeBears submissions.

We all know that what has been proven falls short of security. The gaps
(what has _not_ been proven) are targets for cryptanalysis. However, the
previous literature doesn't make it easy for cryptanalysts to see the
whole list of targets. This paper lays out the whole list, including

* the IND-CPA or OW-Passive problems for 36 core PKEs;
* the possibility of non-ROM IND-CPA attacks against some PKEs;
* the possibility of non-ROM IND-CCA2 attacks against each KEM; and
* two different types of tightness issues for some of the KEMs.

The core PKEs are presented using a shared notation designed to help
cryptanalysts. The paper's presentation is in general self-contained
(although I didn't include, e.g., the details of the Melas code inside
ThreeBears), and it's much more concise than the original sources.

Proofs tell us that the claimed security level L for attacks of type T
against KEM X follows from security level L' for underlying problem P.
Beyond the existing lists of (X,L), this paper shows each T, each P, and
the gap between L' and L. This allows a thorough security review to be
modularized as follows:

* Does the underlying problem P reach security level L'?
* Are there attacks beyond the type T considered in the proofs?
* Are the proofs correct?

Completing a thorough security review will also show the cost of the
review, which in turn is a predictor of the chance that the review
missed a devastating attack. Some aspects of this cost can already be
seen from this paper.

This paper is based upon hundreds of pages of earlier material. I've
taken various steps to reduce the chance of errors (and caught various
mistakes in previous work), but I haven't done the work of, e.g.,
reimplementing all 36 KEMs. Given the indisputable importance of
thorough security reviews for controlling risks, I hope that each KEM
submission team is willing to take the time to check the accuracy of
what the paper says about the KEMs from that submission.

---Dan

[Mike Hamburg]

Hi Dan,

Thanks for this useful work.  I would like to add a bit of nuance on two subjects: the OW-Passive vs IND-CPA angle (aka “dist: risk”), and on decryption failures, coming from our study at the Oxford workshop’s CCA group.  Also I will confirm your analysis of ThreeBears; and add another risk axis, namely multi-target attacks.

=================================================

OW-Passive vs IND-CPA:

The intuitive reason that randomized schemes typically incur a greater tightness loss when reducing from OW-Passive is, roughly, that OW-Passive is a harder problem for a randomized scheme than for a deterministic one.  That is, with a deterministic scheme, an attacker can recognize when he’s solved OW-Passive, and in the (Q)ROM, so can the simulator.  But with a randomized, IND-CPA secure encryption scheme, the simulator or attacker cannot efficiently verify that a proposed preimage is correct, since that’s exactly the IND-CPA problem.

This shows up in the FO theorems, because you need OW-Passive on the derandomized scheme, which is a stronger property than OW-Passive on the randomized one.

This difference applies for the actual parameters of many submissions: they often transport a message which is lambda bits long, using a lattice scheme that has core-SVP difficulty of around lambda.  Since core-SVP is likely an underestimate, the fastest currently-known attack on such systems is generally the lambda-bit exhaustive attack on the message.  This attack doesn’t apply to the underlying randomized PKE, because you’d instead have to guess the randomness.  While obviously a lambda-bit attack isn’t (in general) threatening, this demonstrates that the OW-Passive strength of a randomized encryption scheme might be much higher than that of the derandomized version.

The proof of (non-tight) IND-CPA randomized -> OW-Passive derandomized can, at least in the cases we studied, be routed through an “OW-Conf” security notion with at most constant additional tightness loss.  The OW-Conf notion is OW-Passive, except that the adversary gets an oracle to confirm whether a given guess for the preimage is correct, thereby avoiding the above issues.  This notion captures the way in which randomized OW-Passive is harder than deterministic OW-Passive.

There is still a tightness loss from this approach, but at least it avoids the apparently stronger assumption of IND-CPA security.  Furthermore, it avoids the inherent weakness in IND assumptions pointed out by eg Micciancio and Walter (https://eprint.iacr.org/2018/077).

(There is actually still a technical issue with OW-Conf, which is why we didn’t use it in the Oxford paper, https://eprint.iacr.org/2019/590.  The question is what kind of confirmation oracle does a quantum adversary get?  In the no-additional-tightness-loss case, the adversary gets a semiclassical oracle.  This makes OW-Conf rPKE still a weaker assumption than OW-Passive dPKE, in that you can’t do a Grover attack against a semiclassical oracle.  The tightness loss in the derandomization partially reflects that the Grover attack is possible on a deterministic scheme.  Future work: try to solve with a better O2H-style theorem?)

In sum, I would say that OW-Passive on a dPKE isn’t necessarily a weaker assumption than IND-CPA or especially OW-Conf on an rPKE.

=================================================

Decryption failures:

I also think it’s worth noting that in the Oxford paper, we reduce the contribution of decryption failure probability to two other probabilities:

* The probability \epsilon that, for a given public key, derandomized encryption isn’t injective.  This hasn’t been studied before, but a back-of-the-envelope calculation suggests that it should be truly negligible (2^-thousands) for lattice systems.  That calculation is rigorous (in the QROM) for ThreeBears, but needs improvement to be rigorous for eg Kyber because of zero divisors.

* The probability that, given a public key (but NOT the private key) the adversary asks a decryption query valid ciphertext that fails to decrypt.  This probability is additive with the adversary’s advantage, i.e. it is tight.  It is bounded by O(dq\delta + \sqrt{\epsilon}) in the QROM, using your third definition of \delta.

This proof gives strong evidence that the attack model used in papers such as [https://eprint.iacr.org/2018/1089.pdf] is the right one.  Inasmuch as the technique can be adapted to everyone’s FO mode, it indicates exactly what those q\sqrt{delta} terms are doing in everyone’s proof.  So in general it reduces the risk of an unknown attack leveraging decryption failures, though of course there could still be non-QROM attacks, or attacks that improve on today’s “key-agnostic” ones.

=================================================

ThreeBears and multi-target risk:

As for my submission, ThreeBears, you have categorized it correctly.  It uses the ROM for hashing and for derandomization (ROM and ROM2 risk).  It has a nonzero failure rate that isn’t proved (conj:risk), though there is a pretty rigorous evaluation for the correctness of the conjecture in the supplemental material.  Finally, it assumes indistinguishability (but could possibly be converted to OW-Conf) for the underlying problem, which is of course itself only conjecturally secure.  And you are right that I am planning to change to implicit rejection, unless a good reason appears soon to avoid the change.

I say “could possibly be converted” because the ThreeBears proof examines an additional element of risk, namely multiple-target attacks.  While there has been little serious evaluation of PQ schemes against multi-target attacks, it is worth mentioning that the ThreeBears proof includes a reduction from multiple-key, multiple-ciphertext security of the KEM to that of the underlying PKE.  This is relevant (if the proof is correct) because there have been other works suggesting multi-target security problems against earlier versions of, eg, LAC.  These attacks appear to be a much more serious risk to systems that have nonzero failure probability, since multi-target LWE problems haven’t (AFAIK) been thoroughly examined.

The proof included in the submission uses the IND-CPA problem specifically because it avoids the memory-tightness issues you mention when there are many keys and ciphertexts.  It may be possible to port those to a multi-target generalization of OW-Conf, but I haven’t checked it.

Cheers,

— Mike

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.

[D. J. Bernstein]

Thanks to Mike for his comments. Here are a few followup comments.

1. I agree that, for cryptanalysts analyzing the impact of decryption
failures, the critical question is how to make a decryption failure
happen. (If you can't make a decryption failure happen then you can't
distinguish the PKE from a modified PKE that magically always works.)
Of course the attacker isn't given the secret key.

Some of the KEMs have proofs that eliminate the need for cryptanalysts
to analyze this question. However, care is required in these proofs. As
far as I know, every correct proof of this type can be factored through
the HHK17 definition of failure probability, which has the subtlety that
the attacker _can_ look at the secret key.

There are ways to work with the HHK17 definition---some KEMs have no
decryption failures; some KEMs use the attacker-chosen message in a way
that doesn't affect the failure probability; maybe the probability can
be analyzed even in other cases---but we can't simply assume that people
are getting this right. As a code-based example,

https://www.ledacrypt.org/documents/LEDAcrypt_spec_latest.pdf

appeals to the HHK17 CCA theorems, but it actually uses a different
notion of failure probability, without commenting on the difference.
It's not clear to me that this proof gap can be fixed.

2. My paper focuses on specific KEMs that are proposed for widespread
deployment and that claim specific quantitative security levels. As far
as I can tell, none of the target KEMs claim a better T-target security
level than what's implied by the trivial T-factor bound.

In other words, if the single-target security goal is chance <=eps (at
whatever cost), then the T-target security goal is chance <=T*eps (at
the same cost modulo overhead for key generation etc.). There is no
additional risk of T-target attacks beating the T-target security goal,
beyond the risks of single-target attacks beating the single-target
security goal, which are the risks covered in my paper.

Hypothetically, if some KEM were to go out on an extremely shaky limb
and claim a better T-target security level (e.g., chance<=sqrt(T)*eps),
then this KEM would have an extra multi-target risk to analyze, and it
would be useful to make a table showing how proofs address various
components of this risk.

3. Regarding OW-Passive hardness assumptions, see below.

Mike Hamburg writes:
> I would say that OW-Passive on a dPKE isn’t necessarily a weaker
> assumption than IND-CPA or especially OW-Conf on an rPKE.

After reviewing the relationship between OW-Passive for a PKE and
IND-CPA for the same PKE, my paper says

This does not imply that assuming OW-Passive for one PKE is safer
than assuming IND-CPA for a _different_ PKE: the differences between
the PKEs can outweigh the gap between OW-Passive and IND-CPA.

What Mike is saying sounds like a special case of this, where the first
PKE is deterministic and the second is randomized. He's also considering
a variant of the same statement with OW-Conf in place of IND-CPA.

> The intuitive reason that randomized schemes typically incur a greater
> tightness loss when reducing from OW-Passive is, roughly, that OW-Passive is a
> harder problem for a randomized scheme than for a deterministic one.

I agree that known proof strategies have more trouble using OW-Passive
assumptions for randomized PKEs than using OW-Passive assumptions for
deterministic PKEs. (Otherwise every KEM would have "dist: safe".)

But I don't agree that OW-Passive assumptions for randomized PKEs are
generally harder to break than OW-Passive assumptions for deterministic
PKEs. This can go either way, depending on the PKEs; it's critical for
cryptanalysts to look at the details of both PKEs. The literature is
full of examples of broken PKEs of each type.

Of course an already-proven-to-be-broken hardness assumption is,
logically, a powerful tool in proofs. (False implies everything.) So we
have many examples of powerful hardness assumptions that are easy to
break---counterexamples to the idea that power of an assumption inside
proofs implies strength of the assumption. But we also have many
apparent counterexamples to the opposite extreme, the idea that power
implies weakness.

Mike points specifically to FO derandomization having security limited
by the message length. My reaction to "input length limits security" is
"make sure the inputs are long enough"; this doesn't justify any sort of
deterministic-vs.-randomized conclusion.

To be clear: I'm not saying that FO derandomization is safe. I find it
worrisome that there don't seem to be any papers from cryptanalysts
studying the security of FO derandomization. The proof picture allows
the output of FO derandomization to be much weaker than the original
PKE, even if one restricts attention to ROM attacks: HHK17 has a
Q-factor loss, and I'm not aware of anyone suggesting that better proofs
are possible. The main message from an attack here would be "make sure
that proof gaps are seen and addressed by cryptanalysts".

---Dan

[Mike Hamburg]

Hi Dan,

I think we’re in agreement on decryption failures, but I’d like to clarify a

few things.

On Jun 10, 2019, at 2:43 PM, D. J. Bernstein <d...@cr.yp.to> wrote:

Thanks to Mike for his comments. Here are a few followup comments.

1. I agree that, for cryptanalysts analyzing the impact of decryption
failures, the critical question is how to make a decryption failure
happen. (If you can't make a decryption failure happen then you can't
distinguish the PKE from a modified PKE that magically always works.)
Of course the attacker isn't given the secret key.

This intuitively obvious fact is proven in [BHHP19], under the assumption

that the PKE’s encryption algorithm is at least injective.

What makes the proof nontrivial is that the adversary needs to

_classically_ output a decryption failure, rather than just _quantumly_

distinguishing a magical change that would make the PKE always work.

In the attack-based definition, the attacker is not given the secret key,

nor any oracle with the secret key embedded (eg decapsulation).

The paper then proves that outputting a decryption failure is hard, if the

scheme is \delta-correct for small \delta under the HHK17 definition.

This matches the intuition that 

Some of the KEMs have proofs that eliminate the need for cryptanalysts
to analyze this question. However, care is required in these proofs. As
far as I know, every correct proof of this type can be factored through
the HHK17 definition of failure probability, which has the subtlety that
the attacker _can_ look at the secret key.

The HHK17 definition is statistical: it doesn’t involve an attacker at all.

Also, as used in [BHHP19], the use of the secret key in the definition is

inessential.  If you made an equivalent definition with the outer expectation

only containing the public key, you would get the same result.  But that

distinction only matters if there are multiple secret keys for a given public

key, such that failure or success depends on which secret the recipient

holds.

However, the important point is that the HHK17 definition is fairly strong,

since it’s a maximum over all messages and not an average.

There are ways to work with the HHK17 definition---some KEMs have no
decryption failures; some KEMs use the attacker-chosen message in a way
that doesn't affect the failure probability; maybe the probability can
be analyzed even in other cases---but we can't simply assume that people
are getting this right. As a code-based example,

  https://www.ledacrypt.org/documents/LEDAcrypt_spec_latest.pdf

appeals to the HHK17 CCA theorems, but it actually uses a different
notion of failure probability, without commenting on the difference.
It's not clear to me that this proof gap can be fixed.

Thanks for the example.  I don’t mean to imply that everyone is getting it right.

I would say that OW-Passive on a dPKE isn’t necessarily a weaker
assumption than IND-CPA or especially OW-Conf on an rPKE.

After reviewing the relationship between OW-Passive for a PKE and
IND-CPA for the same PKE, my paper says

  This does not imply that assuming OW-Passive for one PKE is safer
  than assuming IND-CPA for a _different_ PKE: the differences between
  the PKEs can outweigh the gap between OW-Passive and IND-CPA.

What Mike is saying sounds like a special case of this, where the first
PKE is deterministic and the second is randomized. He's also considering
a variant of the same statement with OW-Conf in place of IND-CPA.

I may not have been clear about this: I’m saying that there isn’t necessarily

a gap to be outweighed.  For a deterministic scheme, OW-Passive and

OW-Conf are the same (except up to the cost of encryption; and, depending

on the exact definition, in pathological cases that don’t apply here).  This

is because confirmation is easy in a deterministic scheme.

For a randomized scheme, they are not the same: OW-Conf is a stronger

assumption.  This reflects the fact that confirmation is hard for a randomized

scheme.  In fact, in this case there is a hierarchy of possible assumptions

depending on whether the confirmation oracle is classical or quantum:

OW-Passive <= OW-Conf-classical <= OW-Conf-semiclassical <= OW-Conf-quantum

So if you want to make an argument about one assumption or the other

being a priori preferable or less risky, you’d need to determine which

assumptions match up the best across schemes.  I think the best

translation of OW-Passive (vs deterministic) to a randomized scheme

is in fact OW-Conf-quantum.  This is a good translation because it best

translates the known attacks on those systems, whereas translating

OW-Passive to OW-Passive doesn’t.  In particular, OW-Conf analogizes

correctly when an attacker narrows the message down to an exhaustible

number possibilities but can’t pick a final answer.

If you buy this argument, you should agree that assuming

OW-Conf-semiclassical for a randomized scheme (or using IND-CPA,

but only to puncture an oracle, which is equivalent) isn’t a priori riskier

than assuming OW-Passive for a deterministic scheme.  Instead, it

depends almost entirely on the differences between the two schemes.

There is still the risk that FO derandomization is weaker than expected,

either from the factor of q (or d) in the QROM proofs, or because SHAKE

isn’t a random oracle.

Cheers,

— Mike (speaking for myself)

[BHHP19] Tighter proofs of CCA security in the quantum random oracle model

Nina Bindel and Mike Hamburg and Andreas Hülsing and Edoardo Persichetti
https://eprint.iacr.org/2019/590

[daniel.apon]

Section 2, page 6:  "Any attack A against X must be of type T."

This is not an assumption anyone actually makes -- no matter their personal confidence in the notion of provable/reductionist security.

Hope this helps,
--Daniel

[D. J. Bernstein]

Mike Hamburg writes:
> The HHK17 definition is statistical: it doesn’t involve an attacker at
> all.

HHK17: "Equivalently, delta-correctness means that for all (possibly
unbounded) adversaries A, Pr[Cor^A_PKE => 1] <= delta, where the
correctness game is defined as in Figure 2 (left). That is, an
(unbounded) adversary obtains the public and the secret key and wins if
it finds a message inducing a correctness error."

If by "statistical" you mean that the attacker defined by HHK17 is
permitted unlimited amounts of computation (and can thus compute the
secret key or an equivalent secret key from the public key), I agree.
But I don't agree that this "doesn't involve an attacker at all". It's
helpful to think of the maximization over messages as being a message
selection by an attacker with massive amounts of computer power.

> I think the best translation of OW-Passive (vs deterministic) to a
> randomized scheme is in fact OW-Conf-quantum.

I understand your enthusiasm for this proof strategy, but the switch
makes it much harder to argue that the problem is "well studied". See
generally Section 6.2 of the latticeproofs paper, pointing to Ajtai and
Regev and Peikert citing work by Dirichlet, LLL, Schnorr, etc., none of
whom were considering your extra OW-Conf-quantum oracle.

---Dan

[D. J. Bernstein]

Daniel Apon writes:
> Section 2, page 6:  "Any attack A against X must be of type T."
> This is not an assumption anyone actually makes

The next sentence says that this is "the 'definition' of the type of
attack under consideration". The quoted word "definition" is coming from
the Katz--Lindell quote earlier on the page:

Proofs of security give an iron-clad guarantee---relative to the
definition and assumptions---that no attacker will succeed; ...

As part of this quote, Katz and Lindell are doing exactly what you claim
nobody is doing: namely, assuming that "no attacker" (their words!) is
outside the scope of whichever definition is used in the proof.

My paper goes on to point out various ways that the stated argument can
fail. Of course this includes the risk that what the attacker is doing
is _not_ of type T. The next page states a bulletproofed argument that
takes this into account, along with various other risks. Spelling out
the concept of "security proofs" at this level of detail is a
prerequisite for the rest of the analysis in the paper.

> -- no matter their personal
> confidence in the notion of provable/reductionist security.

I'm unable to figure out (1) what you think you mean by "confidence" in
this "notion" and (2) why you think this is relevant to my paper's
analysis, in particular the quote given above.

---Dan

[Mike Hamburg]

> On Jun 10, 2019, at 9:04 PM, D. J. Bernstein <d...@cr.yp.to> wrote:
>
> Mike Hamburg writes:
>> The HHK17 definition is statistical: it doesn’t involve an attacker at
>> all.
>
> HHK17: "Equivalently, delta-correctness means that for all (possibly
> unbounded) adversaries A, Pr[Cor^A_PKE => 1] <= delta, where the
> correctness game is defined as in Figure 2 (left). That is, an
> (unbounded) adversary obtains the public and the secret key and wins if
> it finds a message inducing a correctness error."
>
> If by "statistical" you mean that the attacker defined by HHK17 is
> permitted unlimited amounts of computation (and can thus compute the
> secret key or an equivalent secret key from the public key), I agree.
> But I don't agree that this "doesn't involve an attacker at all". It's
> helpful to think of the maximization over messages as being a message
> selection by an attacker with massive amounts of computer power.

Ah, so that’s why you frame it in terms of an attacker.

From my point of view, the issue was twofold. First, to reduce to
correctness, you need to define correctness by the worst message
and not the average one. This reflects a realistic attack, (starting
with the failure-prone messages first) and not just a proof
shortcoming. In my view, this is the subtlety when analyzing failure
probabilities.

The second is that we couldn’t tightly reduce to a computational model
where the attacker is trying to find failures but without knowing the secret
key. I didn’t know if you were referring to this in your post. There was a
lingering risk that somehow the decaps oracle might help you find failures,
or that the point in the proof where you do the failure-finding step has been
modified already using the secret key, or something like that. This is
solved, at least in large part, by BHHP19.

>> I think the best translation of OW-Passive (vs deterministic) to a
>> randomized scheme is in fact OW-Conf-quantum.
>
> I understand your enthusiasm for this proof strategy, but the switch
> makes it much harder to argue that the problem is "well studied". See
> generally Section 6.2 of the latticeproofs paper, pointing to Ajtai and
> Regev and Peikert citing work by Dirichlet, LLL, Schnorr, etc., none of
> whom were considering your extra OW-Conf-quantum oracle.

Fair enough. Still, I don’t see there being a huge additional risk from
unstudied *distinguishing* attacks, at least not on the PKE as a whole,
because (if the ROM proof offers guidance) the attack should look in
some fundamental way like a search.

Regards,
— Mike