Subject: [Cfrg] reductions vs. random-oracles

From: Shai Halevi <[email-masked]>
Date: Thu, 27 Mar 2003 12:33:49 -0500

On Thursday 27 March 2003 13:58:43 +0100, Bodo Moeller wrote:
> [...]
> It should be noted that all such counterexamples make statements about
> *asymptotic* security: they assume that a fixed description of the
> hash function is used across all security parameters and exploit
> anomalies in this setting.  

That's just not true. These examples have nothing to do with "asymptotic" 
vs. "concrete" security. 

> But to me, the random oracle methodology
> is something that you can resort to if you want to *avoid* asymptotic
> security considerations.  Please read on: 
> [...]
> One the other hand, such reduction-based proofs make only asymptotic
> statements, since the underlying assumptions (such as intractability
> of factoring) are asymptotic.  

That's not true either. The reduction typically relates the complexity of 
breaking your scheme to the complexity of solving the underlying 
problem. And the underlying assumptions can be concrete if you want it 
to be (i.e., nothing stops you from assuming that factoring a 1024-bit 
integer takes at least 2^xxx computational steps and 2^yyy space, or 
whatever). 

> [...]
> Either methodology has its inherent problems.  [...] 
> A more positive view is to
> acknowledge that in both cases we end up relying on heuristical
> considerations, and that we cannot get far if we are not willing to do
> so.

Sigh. I guess that this is already in the realm of philosophy, but let me 
try to answer it anyway. 

Security reductions are just that: they reduce your belief in the 
security of your cryptosystem, to the belief that a well-specified 
problem (with sell-specified parameters) cannot be solved using 
"reasonable resources". There are no heuristics involved here. (Of 
course, you can always argue that the belief in the infeasability of 
solving the problem is only a heuristic.)  

On the other hand, proofs (or reductions) in the random oracle model 
involve the heuristic assumption that the attacker only uses the hash 
function as a "black box" (and then some assumptions on top of that). 
This is an exceedingly successful heuristic, however. 

Regards, 

-- Shai
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 28 Mar 2003 18:12:30 +0100

> That's just not true. These examples have nothing to do with "asymptotic" 

The asymptotic aspect in your paper lies in enumerating "efficiently
computable" function ensembles.  Sloppily said, the examples assume
that function descriptions  <i, s>  are shorter than the complete
function table of a random oracle: polynomial size compared with
exponential size.  This certainly makes a lot of sense, but it's
inherently asymptotic.

>>> [...]                                              It's true that when
>>> you hear about a "proof of security" in the context of reduction-based
>>> analysis, typically there is some computational assumption, like
>>> that factoring is hard.  [...]

> to be

Right, sorry, I was being led astray by the example that was given in
the message that I was commenting on: "Factoring is hard" is an
oversimplified short form of an assumption that translates into an
asymptotic statement.  (Factoring random integers is not hard -- quite
a lot of them are notoriosly easy to factor because they are prime --,
so a statement such as "factoring integers of the form  p*q  with
p, q  prime is hard" would be closer to the actual assumption.  Of
course we'd also have to say something on the distributions of  p
and  q.)

I had wrongly assumed that the above quote was about asymptotics.  The
hardness of factoring could also be expressed in terms of concrete
security, but I have not seen anyone do this so far.  Actually I used
the words "*such* reduction-based proofs" precisely because not *all*
reduction-based proofs use asymptotics ... see my comment to Anton's
follow-up.  David has pointed out that "reduction-based concrete
security is [his] preferred paradigm, when applicable", and I hope
that my reply to Anton's message has already made it clear that I
agree.

>       (i.e., nothing stops you from assuming that factoring a 1024-bit 

Yes, something like this is possible (although not literally like this:
even if we restrict to composite integers  p*q  with  p, q  prime,
an assumption of this form does not work; but we can make assumptions
on upper bounds on the success probability that an adversary can have
for factoring such 1024-bit composites).  (As an aside -- recently I
was looking for a quantitative version of the assumption on the
hardness of factoring expressed in this style, but did not find
anything.  If someone knows appropriate citations, I'd by very
interested in seeing these.)

> solving the problem is only a heuristic.)  

Exactly; and the machine model that we need for defining
"infeasability" non-asymptotically is not really well-specified, so
there are actually multiple heuristical aspects involved here.  For
example, we usually silently assume that the machine model does not
include an atomic instruction that directly inverts SHA-1.
(Asymptotic analysis does not have to worry too much about such
gadgets, inverting SHA-1 is just an  O(1)  problem anyway ...)

-- 
Bodo Möller <[email-masked]>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. +49-6151-16-6628, Fax +49-6151-16-6036
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg