> 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