[Cfrg] On using ROs for analyzing randomness extraction functions

[David Wagner <daw at cs.berkeley.edu>]

Ran Canetti writes:
>More concretely, regarding the problem of "deterministic computational
>randomness extraction" - namely, coming up with a public function H that
>turns inputs with high computational entropy into pseudorandom values. We
>know that if the distribution of inputs to H can depend on the definition
>of H then this task is impossible.
>
>One way to get around this impossibility is to model H as a RO. Then
>ofcourse this problem becomes not only doable but also trivial: almost any
>way of feeding the input to the RO will be equally as secure as any other
>way. But, alas, this doesnt change the fact that the task is impossible
>in reality... in particular, we have learned nothing regarding which
>constructions are better than others.

I guess I have a different take on this.  I wouldn't say that the RO
model proves security for some task is impossible in practice.  Rather,
I would say that the RO model idealization implicitly assumes that the
source does not depend on H in any way.  Consequently, in any real world
protocol, we have an obligation to convince ourselves that the source
does not depend on ("is independent of" / "does not interact badly with")
the hash function if we want the RO security proofs to mean anything.
The RO model cannot help us with the latter obligation; that's something
we have to assess heuristically via some other kind of reasoning.  But in
many cases the "no bad interactions" hypothesis looks very plausible
(even if we cannot prove it), and in such cases one would expect the RO
model to form good evidence for security in real life.

Let me try an analogy.  When we analyze "hash-then-sign" (FDH signatures)
in the RO model, our RO idealization implicitly assumes that the
trapdoor permutation is independent of the choice of H.  That's an
assumption that is never proved; and one has to look at the real world
scheme and guess whether the assumption is met.  But if we take, say,
a FDH signature where we hash with SHA256 and then sign with raw RSA, it
boggles the imagination that there could be any bad interaction between
SHA256 and RSA.  Consequently, the "no bad interactions" looks like a
fairly plausible assumption, even though it is not something we know how
to prove.  We wouldn't say that the "hash-then-sign" task is impossible in
reality, even though it is true that there do exist (contrived-looking)
trapdoor permutations that interact with SHA256 badly enough to make
"hash-then-sign" insecure with those trapdoor permutations.

So the random oracle model, and the assumptions needed to make it
meaningful, doesn't seem so bad to me in this setting.

_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg