Re: Fujisaki-Okamoto Hybrid Encryption

Peter van Liesdonk <peter@xxxxxxxxxxx> wrote:
Would someone like to look in to this proof and give his opinion?The proof of Lemma 11 is 3 1/2 pages long. Would you care to indicate
more precisely what you think is wrong?

Sure.

They start with the description of an algorithm. This algorithm either
returns a plaintext that encrypts to a given ciphertext (c1,c2). Yet it
can only do this if certain queries have been asked. Otherwise it fails
and returns $\bot$.
Next they define several events, among which 'Fail', which is true if
the output of the algorithm is not equal the decryption of (c1,c2).
Obviously (according to me), when the algorithm returns $\bot$, it does
not return a valid decryption of (c1,c2) and thus 'Fail' is true.

The rest of the proof is about giving an upper bound for the
probability of 'Fail'.
They claim: Pr[Fail | 0111] = 0, with which i agree (top of second page
of proof). In the same line they claim it is obvious that Pr[Fail |
0110] = 0. According to me, 0110 is an event in which the algorithm
returns $\bot$. Thus Pr[Fail | 0110] should be 1.
The same for the claims Pr[Fail | 00], Pr[Fail | 010]...they should
also be 1.

I guess that either I somehow misunderstood this part (probably how the
algorithm works), or the authors mean something different from what
they write. But I cannot make any sense of what they do mean.
Especially the 'Here we can easily find that Pr[Fail|0110]=0'.

OK, I'm going way out on a limb here since I haven't read this paper.
I have read other proofs on hybrid encryption schemes (for example in
the Cramer-Shoup paper or the Kurosawa-Schmidt-Samoa paper), and think
I see the problem however.

My guess is that "Fail" is the probability that the simulator fails,
NOT that the algorithm (or decryption oracle) fails. When the oracle
returns $\bot$ that means that it has refused to give an answer. That
is NOT the same as the simulator failing.

Just remember that you've got two things going on in a proof like
this: an attacker that's written to attack the overall hybrid scheme,
and a second system that attacks something else (like the CCA security
of the KEM) in which you simulate the view of the hybrid scheme for
the first attacker. Both of these interact with it's own notion of a
decryption oracle. Just because the decryption oracle fails to
produce an answer in some cases doesn't mean that the simulator fails
(and the simulator can fail even if every call to the decryption
oracle gives a meaningful answer).

So how's that for a wild guess without even looking at the paper? :-)

--

Steve Stringer
sillybanter@xxxxxxxxx

.

Relevant Pages