Re: Weakness in RSA

From: Stefan Katzenbeisser (katzenb@REMOVEdbai.tuwien.ac.at)
Date: 02/05/03 

From: Stefan Katzenbeisser <katzenb@REMOVEdbai.tuwien.ac.at>
Date: Wed, 5 Feb 2003 11:39:52 +0100

In article <TeX%9.251$rj7.90950795@twister1.starband.net>, Roger Schlafly wrote:
> "David Wagner" <daw@mozart.cs.berkeley.edu> wrote
>> >Actually, they don't give "security guarantees". Just some heuristic
>> >arguments.
>> I agree that the random oracle model has some deficiencies, and the
>> controversy continues to rage, but "heuristic" seems a little strong
>> to me. Or rather, if this is what you call a "heuristic", then by all
>> means, give me more some more of those "heuristics"!
>
> Heuristics can be very valuable. Sure. But the arguments do not
> give the "security guarantees" that Stefan claimed. It is not helpful
> to use terminology that misleads people into making false inferences
> -- and that is what most of the random oracle folks do.

I hope that this doesn't turn into a lengthy debate about terminology,
but here is my point of view: a heuristic is something that lacks a
formal flow of arguments, or an argument that relies on some sort of unproven
assertion at some point (like: we don't know an efficient algo for this -- so it
might be hard). BTW, I don't want make the impression that heuristics are
always bad -- I agree with Roger that heuristics can be very
valuable in certain situations.

For me, a proof in the random oracle model is much more than a heuristic.
Once you accept some (reasonable?) assumptions, you get a formal proof.
My opinion is that you can indeed speak of a "guarantee" here. Of course, if
you question the assumptions (or if you think that the assumptions do not
model the real world correctly), then the practical usefulness of the result
is debatable... But you still have a valid statement.

I don't want to start another battle in the ongoing debate about the
usefulness of random oracles here (as I think that both sides have some good
arguments), but I think that seeing proofs in the random oracle model
as "heuristics" greatly underestimates their value...

-S

Relevant Pages

  • Re: Weakness in RSA
    ... > controversy continues to rage, but "heuristic" seems a little strong ... Heuristics can be very valuable. ... -- and that is what most of the random oracle folks do. ...
    (sci.crypt)
  • Re: Whos familiar with random oracle model?
    ... I am not an expert on the random oracle model. ... A practical random oracle is a hash function, ... lines of "the attacker needs X oracle invocations where the average ...
    (sci.crypt)
  • Re: dumb question: why is it called a "reduction"?
    ... I don't know of any paper that calls random oracle proofs a reduction. ... Most papers are clear to state that the random oracle model is a *model*, ... Clearly one can't prove that SHA1 is a random ... Reductions avoid the pitfalls of the random oracle model. ...
    (sci.crypt)
  • Re: AES with constant key
    ... more into the direction of reformating an encrpyted block and ... A random oracle is a hypothetical 'black box' function. ... mode, an attacker could find relations between certain bits easily, ... function with a fixed key in the random oracle model, ...
    (sci.crypt)
  • Re: Computational secure entropy extraction
    ... you want to work in the random oracle model. ... the random oracle model makes very strong assumptions. ... My question about the existence of provably secure distillers was asking ... whether there is any distiller that is provably secure in the standard ...
    (sci.crypt)