[Cfrg] On using ROs for analyzing randomness extraction functions

[canetti <[e-mail]>]

I'd like to share some thoughts regarding the use of the RO modeling in
the randomness extraction problem.

Beyond the known formal problems with the
applicability of analysis in the RO model, such analysis usually leaves me
with an uneasy feeling of being "cheated out" of a real proof. One main
reason is that the RO, being so powerful, blends within it many different
idealizations. And I never know for sure what idealizations were actually
used in the proof at hand, and what are unnecessary.  (For instance, was the
"programmability" used? was the fact that the output is always uniform for
any two different inputs used? was the "perfect one wayness" used? was the
"hardness to find inputs such that the output has a given property" used?)
I would much rather have analysis in the standard model that makes explicit
assumptions on the hash functions and the adversary. This way, we'll at
least know for sure what I'm assuming away.

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.

An alternative way to get around this impossiblity would be to remain in
our real world (without ROs) and instead make assumptions on the input
distribution of H. (For instance,  we can assume that the description of H
contains some public and random key k, and that the input distribution is
indistinguishable from a distribution that does not depend on k.)
This would indeed be a weaker result than what we'd like, but at least it
we will have some concrete result in our hands.


Ran


PS. One more, loosely relate point: As was already pointed out in this
thread, randomness extraction is actually possible when the extracting
function has some public random input that is independent from the secret
input. Many key exchange protocols give such public randomness "for free",
eg via the nonces etc., while others dont. This should be a good
motivation to (1) prefer the key exchange protocols that give out this
"public randomness", and (2) design randomness extraction functions that
make used of this public randomness.




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