Is pay-per authentication possible absent trust?

[Jason W Solinsky <solman@MIT.EDU>]

I'm having a problem patching up a serious hole in one of my protocols
and I was wondering if anybody here had a solution. [Actually I suspect
that the hole is impossible to patch, but I haven't been able to convince
myself of that yet so intuitive "proofs" would also be appreciated]

Here is the situation. Charles runs a certification agency. He might be
certifying that you have some basic competency so that people will hire
you. Or he might be certifying that you buy lots of computers with big
brother inside microprocessors, thus making advertisers who want to
sell software for big brother inside computers [i.e. Microsquish] willing
to pay extra money for your time.

Either way, Charles's certification is worth money to you. But the value to
you isn't a constant amount. Each time you use the certification, you derive
additional value from it. So Charles figures that it makes much more sense
to sell his certifications on a per use basis... People who only occasionally
need the certification will be able to afford it and Charles can gouge people
who need the certification frequently for all they are worth.

To do this Charles adopts a protocol in which his signatures are time
dependent. Everybody can verify that his signatures a valid for the time
at which a signature is required, but only Charles can figure out what
the correct signature is for time T in polynomial time. [Note: There are
many alternative methods of accomplishing this, but they all seemed to have
the same hole... If you can find a way to patch the hole that requires
changing this protocol it would still solve my problem].

So Charles sells you one-time certifications, and Microsquish pays you extra
for those certifications and everybody is happy. Then, one day, Microsquish
decides that Charle's certifications aren't worth as much as they used to
be, so it lowers its price (for your time) to slightly greater than what
Charles is charging you. Well this makes you unhappy so you complain to
Charles, but he refuses to change his price. This makes you angry at Charles
and causes you to wonder if there isn't a way to lower your certification
costs.

Enter Ingve the insurance salesman. Ingve will guarantee to others that you
are certified by Charles by offering them bets. So suppose that Microsquish
sends you its advertising agent and the agent is offering a 10 nano-slinkys
[a cyberspatial monetary unit] bonus if you can produce one of Charles's
certifications. Charles is charging 8 nano-slinkys. In steps Ingve. You've
told Ingve that you are certified by Charles as a frequent purchaser of big
brother inside computers. So Ingve says: "I'll convince Microsquish to accept
my word that you have Charles's certification in exchange for just four
nanoslinkys. But if at my request you ask for the certification and Charles's
says you aren't certified then you owe me 64 nano-slinkys." Since you are sure
that you are certified you accept the deal. Then Ingve goes to Microsquish
and offers to insure your certification. Each time Microsquish accepts a
certification from Ingve for you, Ingve will pay Microsquish 2 nano-slinkys
but will be able to get your business (and thus offset that with the four
nano-slinkys). But, if it turns whenever Microsquish wants to it can check
up on your certification from Charles at cost (8 nano-slinkys). If Charles 
certifies you all is well. Otherwise, you owe Ingve 64 nano-slinkys and
Ingve has to pay up Microsquish's insurance claim (which could be quite large
depending on the policy.

The result of all this is that Charles is cheated out of his revenue. Ingve,
You and Microsquish profit, but Charles fails to reap the benefits of his
certification. The question is: Is there a secure method that charles can
use to prevent the "Ingve the insurance salesman attack"?

Cheers,

Jason W. Solinsky