Re: namedroppers, continued

[ned.freed@mrochek.com]

[ post by non-subscriber.  with the massive amount of spam, it is easy to miss
  and therefore delete posts by non-subscribers.  if you wish to regularly
  post from an address that is not subscribed to this mailing list, send a
  message to <listname>-owner@ops.ietf.org and ask to have the alternate
  address added to the list of addresses from which submissions are
  automatically accepted. ]

> In message <Pine.LNX.4.44.0212071209090.2775-100000@commander.av8.net>, Dean An
> derson writes:
> >This seems clever, however, it will also take significant computational
> >effort to verify the computational effort was actually done. Even if a
> >class of functions are found that are "easier" to verify than to compute,
> >they will no doubt still take up a significant fraction of time.

> In fact, that's the easy part.  You could demand that the sender
> compute 1,000,000 HMACs of the text, the envelope, the time of day, and
> a counter.  The verifier could check 100 randomly-chosen ones -- if any
> fail, there's a forgery.  (Well, you probably wouldn't want those
> values, since 1,000,000 HMACs would be a lot of data to transmit.  But
> you get the general idea.)

The exmaple given in the Microsoft paper was square roots in a finite field.
These are computationally difficult to compute (lots of multiplication mod p)
but easy to check (single multiplication mod p).

I'm sure there are other examples -- finding candidate functions of this
sort is *much* easier than finding, say, a public key algorithm.

				Ned





--
to unsubscribe send a message to namedroppers-request@ops.ietf.org with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>