Is pay-per authentication possible absent trust?

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

Jason W Solinsky <solman@MIT.EDU> writes:

>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.

One thing I don't follow here is under what circumstances a "challenge"
will occur.  Presumably Microsquish will not blindly accept all of
Ingve's assurances since they are backed only by promises.  Can
Microsquish force Ingve to go to his clients and make them produce
certificates?  Who pays for that?  Maybe if you factor in that cost it
won't look so bad for Charles.

Also, just because Charles can't get what he wants for his certifications
doesn't mean he is being cheated.  It's a market, after all.  You could
just as well say that somebody else opens up a certification shop that
sells certifications just like Charles' for less.  It's not the fault of
the protocol that Charles' business dries up.  If the value of his
certifications drops (as in your scenario) then his business should decrease.

Last, I'd say your problem exists just as clearly without Ingve.  You
could make a deal with Microsquish promising that you would be able to
get certifications if asked, with some agreed-upon procedure by which
Microsquish could demand that you produce one, with appropriate
penalties.  In that case probably Microsquish would believe some
percentage of people and Charles' business would again fall off.  In
practice Ingve might be useful to help even up fluctuations but the
problem arises just as clearly without him.

You might look at it in terms of a priori vs a posteriori probabilities
that you do in fact have the ability to gain a certification.  If
Microsquish was inclined to believe you before (say, because you had
demonstrated good faith in the past), then the exhibition of an actual
certificate is less valuable to Microsquish because it adds less
information.  So it makes sense that certificate challenges, with their
associated costs to you and Microsquish, would occur less frequently in
that case.  Again, it appears that the situation is simply reflecting
market values of information.

Hal

> Jason W Solinsky <solman@MIT.EDU> writes:
> 
> >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.
> 
> One thing I don't follow here is under what circumstances a "challenge"
> will occur.  Presumably Microsquish will not blindly accept all of
> Ingve's assurances since they are backed only by promises.  Can
> Microsquish force Ingve to go to his clients and make them produce
> certificates?  Who pays for that?  Maybe if you factor in that cost it
> won't look so bad for Charles.

First, just let me note that there are a thousand ways to structure it.
In my example, Microsquish gets to hold a challenge whenever they want
to. If everybody is being honest Microsquish will lose eight nano-slinkys
each time they challenge so they won't do it frequently. If everybody
is not being honest, Microsquish will collect substantial damages.

> Also, just because Charles can't get what he wants for his certifications
> doesn't mean he is being cheated.

I refuse to get into another vocabulary fight :)

Lets just say that Charles isn't geting as much as he would like. Pay per
use is good for the consumer... note the resentment that high software
prices have created. Although everybody wins by adopting a system that
better approximates reality, ala superdistribution (but we are dealing with
authentication here, not information and after thinking about it alot I have
decided that authentication is NOT necessarily a form of information in that
you can easily demonstrate to somebody that you have been authenticated
without giving them the ability to prove it to somebody else [again lets not
get into a terminology debate, my point is that the intangible asset here
has a different set of properties from the kind we usually deal with in
information economy scenarios]), the consumer with his smaller buying power
wins the most.

So it would really suck for Charles to lose big at the hands of the consumer
because he tried to do something that dramatically improved the consumer's
position.

Now that I think about it, its possible that I'm in error approaching this
problem from a cryptographic standpoint. Maybe the correct course of action
is to establish a cybergovernment which prohibits "Ingve the insurance
salesman" attacks and then set up the fine structure such that the
conspirators will have an enormous incentive to turn each other in.

> It's a market, after all.  You could
> just as well say that somebody else opens up a certification shop that
> sells certifications just like Charles' for less.  It's not the fault of
> the protocol that Charles' business dries up.  If the value of his
> certifications drops (as in your scenario) then his business should decrease.

Agreed, but it is highly desirable for charles NOT to be forced into
selling certifications for a one time fee from the standpoint of all
involved. Assuming Charles is intelligent, unless we can demonstrate
to him a system that prevents these kinds of attacks, he's going to
be stuck with the one time fee payment scheme.

> Last, I'd say your problem exists just as clearly without Ingve.  You
> could make a deal with Microsquish promising that you would be able to
> get certifications if asked, with some agreed-upon procedure by which
> Microsquish could demand that you produce one, with appropriate
> penalties.  In that case probably Microsquish would believe some
> percentage of people and Charles' business would again fall off.  In
> practice Ingve might be useful to help even up fluctuations but the
> problem arises just as clearly without him.

Yeah. I hadn't been looking at it that way because in my model Ingve gets
played by an agent. There IS, however, an argument for giving control of
Ingve to a third party. As I note above, every time Microsquish checks on
the consumer it loses money. An Ingve could act as an intermediary between
Microsquish and a far larger number of consumers. The relationship thus
built (combined with statistical reality) allow Microsquish to use far
fewer test cases and place a significant (but of course not total) amount
of trust in Ingve's methods for guaranteeing valid licenses [whatever
they may be. It is quite conceivable that there are other things which
can alter the probabilities besides actually challenging the consumer
to get a certification from Charles]. This saves Microsquish, and infact
the whole system, money.

Cheers,

Jason W. Solinsky

BTW, perhaps there is an easier solution: only permit Cherles's
certifications to exist in an environment that he controls. Smart
cards and remote computers can easily do this, although remote
computers are undesirable due to their communications overhead.

Jason W Solinsky <solman@MIT.EDU> writes, quoting me:

>> One thing I don't follow here is under what circumstances a "challenge"
>> will occur.  Presumably Microsquish will not blindly accept all of
>> Ingve's assurances since they are backed only by promises.  Can
>> Microsquish force Ingve to go to his clients and make them produce
>> certificates?  Who pays for that?  Maybe if you factor in that cost it
>> won't look so bad for Charles.

>First, just let me note that there are a thousand ways to structure it.
>In my example, Microsquish gets to hold a challenge whenever they want
>to. If everybody is being honest Microsquish will lose eight nano-slinkys
>each time they challenge so they won't do it frequently. If everybody
>is not being honest, Microsquish will collect substantial damages.

One thing I'd add is that Charles still makes money whenever there is a
challenge.  If there were no challenges then there would be nothing to
keep people honest.  So it's not a matter of eliminating pay per use of
certifications, it's just a matter of the frequency with which they are
used vs other kinds.

Also, as the challenges become less frequent, Charles can actually raise
his rates and still let everyone else make money.  He can even charge
more than the 10 that Micro is paying for challenges, which he could
probably not have done in the non-probabilistic (pre-Ingve) system.  It
sounds like Micro is paying the challenge fees (in at least one version)
and if the penalties against cheaters are great enough it won't challenge
very frequently, in which case a larger fee by Charles can be absorbed.

>Lets just say that Charles isn't geting as much as he would like. Pay per
>use is good for the consumer... note the resentment that high software
>prices have created. Although everybody wins by adopting a system that
>better approximates reality, ala superdistribution (but we are dealing with
>authentication here, not information and after thinking about it alot I have
>decided that authentication is NOT necessarily a form of information in that
>you can easily demonstrate to somebody that you have been authenticated
>without giving them the ability to prove it to somebody else [again lets not
>get into a terminology debate, my point is that the intangible asset here
>has a different set of properties from the kind we usually deal with in
>information economy scenarios]), the consumer with his smaller buying power
>wins the most.

Another approach, BTW, is the "undeniable" signature, which allows an
authorization which can only be checked with the cooperation of the
issuer.  (One of the ones Chaum came up with was described in a posting I
made last weekend.)  But again, the same "problem" arises where people
could check only a fraction of signatures with voluntary penalty clauses.
There is also the reseller who checks a signature interactively, paying
Charles' fee, then sells his own certifications that you have a valid
Charles certification, only these are use-many.  The thing is, the amount
of information being provided in a certification like this is so small
(in effect, one bit) that the "information copying" problem hits pretty
hard!  If you can't stop people from copying a 1 MB game you're going to
have a tough time keeping that single bit corralled.

>Now that I think about it, its possible that I'm in error approaching this
>problem from a cryptographic standpoint. Maybe the correct course of action
>is to establish a cybergovernment which prohibits "Ingve the insurance
>salesman" attacks and then set up the fine structure such that the
>conspirators will have an enormous incentive to turn each other in.

These tend to be non-local solutions, with a lot of overhead and extra
mechanisms.  Maybe you can make it work with your "government" but I'm
afraid you may come to lean on it as the solution to all of your
problems.  Why bother with cryptography for anything; just have a
"government" where everybody has posted a ruinous bond which they forfeit
if they break a "law", then legislate communications privacy, non-
duplication of electronic cash, bit commitments, etc., with heavy
incentives for people to report cheaters?

>BTW, perhaps there is an easier solution: only permit Cherles's
>certifications to exist in an environment that he controls. Smart
>cards and remote computers can easily do this, although remote
>computers are undesirable due to their communications overhead.

Again, though, people could just swear they've seen a Charles certificate
and these witnesses will undercut Charles.

As I said, I think there will still be a place for per-use
certifications, but the market will decide how much they are used vs
other kinds.  I don't think you should worry so much about trying to fine
tune the system so this one technology wins.  There are a lot of
possibilities that people may come up with.

Hal

> Jason W Solinsky <solman@MIT.EDU> writes, quoting me:

> >First, just let me note that there are a thousand ways to structure it.
> >In my example, Microsquish gets to hold a challenge whenever they want
> >to. If everybody is being honest Microsquish will lose eight nano-slinkys
> >each time they challenge so they won't do it frequently. If everybody
> >is not being honest, Microsquish will collect substantial damages.
> 
> One thing I'd add is that Charles still makes money whenever there is a
> challenge.  If there were no challenges then there would be nothing to
> keep people honest.  So it's not a matter of eliminating pay per use of
> certifications, it's just a matter of the frequency with which they are
> used vs other kinds.

True, but we desire something that scales linearly with use.

> Also, as the challenges become less frequent, Charles can actually raise
> his rates and still let everyone else make money.  He can even charge
> more than the 10 that Micro is paying for challenges, which he could
> probably not have done in the non-probabilistic (pre-Ingve) system.  It
> sounds like Micro is paying the challenge fees (in at least one version)
> and if the penalties against cheaters are great enough it won't challenge
> very frequently, in which case a larger fee by Charles can be absorbed.

So you are pointing out that Charles has the ability to move the system
towards a one-time fee system. This is true, but the logic in the above
paragraph is tainted by the fact that the insurance company can shift the
payouts so that the frequency of challenges becomes arbitraily small.
Charles becomes unable to properly charge some customers without overcharging
others.
> >Now that I think about it, its possible that I'm in error approaching this
> >problem from a cryptographic standpoint. Maybe the correct course of action
> >is to establish a cybergovernment which prohibits "Ingve the insurance
> >salesman" attacks and then set up the fine structure such that the
> >conspirators will have an enormous incentive to turn each other in.
> 
> These tend to be non-local solutions, with a lot of overhead and extra
> mechanisms. Maybe you can make it work with your "government" but I'm
> afraid you may come to lean on it as the solution to all of your
> problems.  Why bother with cryptography for anything; just have a
> "government" where everybody has posted a ruinous bond which they forfeit
> if they break a "law", then legislate communications privacy, non-
> duplication of electronic cash, bit commitments, etc., with heavy
> incentives for people to report cheaters?

I agree, I only suggested it because it doesn't look likr cryptography
can help me out here.

> Again, though, people could just swear they've seen a Charles certificate
> and these witnesses will undercut Charles.
> 
> As I said, I think there will still be a place for per-use
> certifications, but the market will decide how much they are used vs
> other kinds.  I don't think you should worry so much about trying to fine
> tune the system so this one technology wins.  There are a lot of
> possibilities that people may come up with.

Maybe I'm looking at it wrong. The challenge is to pay the certifier based
on the value he provides. Perhaps in situations like these YOU are providing
the per use value and the service of the certification agency is of the
one-time nature. Suppose you have created a piece of software which is
compatible with system X. You need somebody to certify that compatibility.
Each time you sell a copy of that software you receive a certain amount
extra because its compatibility has been certified, but I could argue that
the extra value is due to the carefulness of the programer and that the
value created by the certifier really is one time.

But what about systems in which selling signatures on a one time basis is
truly critical to operation. Consider the example of a user who is going
to buy a car. This characteristic is worth a lot of money to companies who
sell cars, but they need a way to verify it. I have envisioned (and even
written some code for) agents that would come along and offer gift
certificates good for any car in class X. The gift certificates would sell
below face value. The agent who sells these certificates can then use the
information that it has sold you the certificate to attract advertisers at
a high price. You save the amount by which the gift certificate was
discounted, the agent keeps any money made beyond the discount, and the
advertisers get the attention of a hot prospect. But how could this system
work if pay-per use authentication is not possible?

[now that I think about it, I guess it is possible to contact the
advertisers ahead of time and be promised a bounty for each prospect
found.]

Cheers,

JWS