On the looseness of FO derandomization

[D. J. Bernstein]

Shoup's Crypto 2001 paper "OAEP reconsidered" provided "strong evidence
that the OAEP construction is not sound": the paper constructed a family
of ROM trapdoor functions F for which OAEP(F) provably has much less ROM
security (and thus much less security for most choices of the oracle).

This does _not_ imply that OAEP(F) is _always_ less secure than F, but
it means that in general OAEP has a provable-security gap. This gap was
then closed (in the ROM) for some RSA variants, but in general the gap
contradicts the idea that cryptanalysis of F ensures the security of
OAEP(F).

I've now posted a paper providing the same type of evidence regarding FO
derandomization: a family of ROM PKEs C for which the derandomized
system T(C) provably has much less ROM OW-CPA security than C does (so
typical CCA conversions have much less IND-CCA2 security).

Beyond this, the paper exhibits a non-ROM PKE C for which T(C) has much
less OW-CPA security than C does against known attacks. This example
uses only well-known design techniques and existing cryptanalysis; new
cryptanalysis is outside the scope of the paper.

This does _not_ imply that T(C) is _always_ less secure than C, but it
means that in general derandomization has a provable-security gap,
contradicting the idea that cryptanalysis of C ensures the security of
T(C). One can define away this gap by hypothesizing IND-CPA security of
C, but most of the time cryptanalysts study search problems without
studying the extra risks of distinguishing problems, so either way T(C)
has a cryptanalytic gap.

The security loss is a factor close to the number of attack operations,
which realistically is above 2^90 today. For the ROM, this is provably
the worst case, so one can eliminate the T problem (unlike the OAEP
problem) by pumping up security parameters sufficiently---but this is
not done in any of the NISTPQC submissions that use derandomization.
(Also, QROM security of KEMs built via derandomization could be worse
than ROM security; this is outside the scope of the paper.)

Note that a careful reading of previous proofs was already sufficient to
identify the potential security problem. See in particular Section 6 of
https://cr.yp.to/papers.html#latticeproofs regarding the risk of T(C)
having lower OW-CPA security than C. However, one could previously have
hoped for this gap to be closed through better proofs; the new paper
presents clear obstacles to any such proofs.

Paper link: https://cr.yp.to/papers.html#footloose

---Dan

[Mike Hamburg]

Thanks Dan, this is an interesting result.

I have some comments related to my experience researching

and writing https://eprint.iacr.org/2019/590.pdf.

It may be worth breaking your new result down further.  The

OW-CPA randomized PKE to OW-CPA deterministic T[PKE,G]

reduction takes place with an intermediate OW-PCA step.  In

OW-PCA, the attacker gets q guesses via an oracle instead of

just one.  (In the classical model this is the same as q-OW-CPA,

where the attacker gets q guesses at the end; in the quantum

model, it is not the same because the PCA oracle is typically

quantum accessible, and so can be attacked with Grover’s

algorithm.)

The OW-CPA to OW-PCA reduction is loose by a factor of q,

for exactly the reason shown in your new paper: if the attacker

can narrow the message down to k < q results, then it benefits

from q guesses.  In the QROM it benefits by a factor of O(dq)

from Grover’s algorithm, where d <= q is the query depth.

The derandomization to OW-CPA T[PKE,G] step is tight in the

ROM.  In the QROM it’s tight with respect to constants, but has

a square root loss at least if you use the double-sided one-way

to hiding lemma.

In any case, this reinforces what we already largely know about

the tightness of derandomization: it’s not enough if the attacker

can’t guess your plaintext in one guess; they must be unable to

guess it in q guesses (in the quantum case, via an oracle).

The corresponding reductions from IND-CPA, which is as you

mention a stronger assumption, is of the form (roughly)

Adv-OW-CPA(T[PKE,G]) <= Adv-IND-CPA(PKE) + (2q+1) / |M|.

In the QROM, it’s:

Adv-OW-CPA(T[PKE,G]) <= (d+2)(Adv-IND-CPA(PKE) + 8(q+1) / |M|).

This can be seen in your ElGamal example, which is plausibly

IND-CPA secure (against classical computers; for quantum ones

we can substitute CSIDH).  Here the guessing attack, or in the

quantum case the Grover attack, comes from the second term in

the reduction: it’s an attack by guessing the message, and it does

correspond to the O(q/M) or O(dq/M) terms.  These terms correspond

to a known attack (your attack in this paper), and are less threatening

because we already know to make |M| large for these reductions.

For this case, as far as I’m aware the (d+2) Adv-IND-CPA(PKE) term

in the QROM case does not correspond to a known attack, and so we

might hope to improve it, or to prove with a counterexample that this

is not possible.  Perhaps someone already has; I’m not up-to-date on

the field.

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.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20210705140027.1933129.qmail%40cr.yp.to.

[Michael Hamburg]

I wrote:

 

> The derandomization [of OW-PCA rPKE] to OW-CPA T[PKE,G]

step is tight in the ROM.  In the QROM it’s tight with respect to

constants, but has a square root loss at least if you use the

double-sided one-way to hiding lemma.

 

Nope, I had recalled incorrectly: it isn’t tight in the QROM, because you

need to use semiclassical O2H instead of double-sided.  Thanks to

Eike Kiltz, Vadim Lyubashevsky, Kathrin Hövelmanns, Julien Duman and

Gregor Seiler for pointing this out in our discussion.

 

Sorry about that,

• Mike