Re: [Cfrg] On using ROs for analyzing randomness extraction functions

[canetti <[e-mail]>]

David,

I think our takes on this are not as different as it might seem.
We agree that randomness extraction when the input distribution depends on
the definition of the extraction function H is impossible in general.
we also agree that we should not stop here, but rather try to get around
this by somehow finding a meaningful way to assume that the input
distribution does not depend on the definition of H. we differ in how to
make this assumption: You seem satisfied with using the RO abstraction.
To me, this abstraction seems unsatisfactory, since it does not allow me
to *precisely state what it is that I'm assuming*. I'm not talking here
about proving anything, just on precise statement of the "non
dependence" assumption. (It sounds great in English, but does it really
mean?)

This is why I'd rather make an explicit, well-defined assumption within
the standard model. Note: I'm not claiming that I have such an assumption
formulated. I also agree that this would probably end up being much more
messy than the RO stuff. But I think it's worth it here to not take the
"easy way out" and try to formulate those things precisely. In some cases,
such as FDH,  the RO seems indispensable (as pointed out by Ilya). I have
a strong feeling that in our case it is dispensable.)

Ran

PS - forgot to agree before - this discussion is indeed very insteresting
and illuminating.

On Fri, 28 Oct 2005, David Wagner wrote:

> 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
> [e-mail]
> https://www1.ietf.org/mailman/listinfo/cfrg
>

_______________________________________________
Cfrg mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/cfrg