Subject: Re: [Cfrg] reductions vs. random-oracles

From: Ran Canetti <[email-masked]>
Date: Thu, 10 Apr 2003 01:05:53 -0400

Bodo,

> From: Bodo Moeller <[email-masked]>
> 
> On Thu, Mar 27, 2003 at 12:33:49PM -0500, Shai Halevi wrote:
> > 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. 
> 
> 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.
 
Good to see someone actually reads those proofs.
But I agree with Shai that the asymptotics here are, as usual, only used 
for convenience of exposition and are not essential. Using the standard 
modeling of SHA1 as a function family that is keyed via the 160-bit IV, 
the [CGH] result can be interpreted as saying the following: There exist 
signature schemes that are secure in the RO model, and are able to sign 
at least 160 bits, and such that any instantiation of the RO using a 
function family whose key length is at most 160 bits causes  the scheme 
to be (completely) insecure. 

Ran

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