Protocol Wanted!!

Here is a simple problem.

Late one night, Bob discovers a clever new method of factoring
large products of distinct odd primes.  Bob may now perform such
factorizations in only a few hours for numbers up to 1024 bits on
his trusty old 486.

Bob spent a lot of time coding and testing his new algorithm, and
wishes to recover some of his expenses by factoring a few RSA
keys for well-to-do clients. Bob wants to do this without
disclosing his identity, so a certain evil three-letter agency
will not cover him with rubber hose marks trying to learn how his
algorithm works.

Alice is the CEO of a company who suspects PGP-encrypted mail is
being used by an employee to transfer trade secrets to a foreign
competitor.  Alice would pay any amount of money to read this
mail and confirm her suspicions.

Alice is a potential client for Bob.  Now for the hard part...

How does Bob make Alice, and other potential clients, aware of
the service he wishes to offer?

How do Bob and Alice conduct business anonymously while making
absolutely sure that neither is spoofing the other?  Alice needs
to know Bob isn't lying about being able to factor.  Bob needs to
know Alice has the means to pay him before he cracks a key.  Bob
and Alice need to exchange a factored key for money with no
chance that either will back out at the last moment and try to
steal from the other.

How much work should Bob expect to come his way if he charges $10
a bit for his factoring service?  $100 a bit?  $1000 a bit?

Comments anyone?

-- 
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $

Commenting on Mike Duvos's original article:

> 
> Here is a simple problem.
> 
> Late one night, Bob discovers a clever new method of factoring
> large products of distinct odd primes.  Bob may now perform such
> factorizations in only a few hours for numbers up to 1024 bits on
> his trusty old 486.
> 
> Bob spent a lot of time coding and testing his new algorithm, and
> wishes to recover some of his expenses by factoring a few RSA
> keys for well-to-do clients. Bob wants to do this without
> disclosing his identity, so a certain evil three-letter agency
> will not cover him with rubber hose marks trying to learn how his
> algorithm works.
> 
> Alice is the CEO of a company who suspects PGP-encrypted mail is
> being used by an employee to transfer trade secrets to a foreign
> competitor.  Alice would pay any amount of money to read this
> mail and confirm her suspicions.
> 
> Alice is a potential client for Bob.  Now for the hard part...
> 
> How does Bob make Alice, and other potential clients, aware of
> the service he wishes to offer?
> 
> How do Bob and Alice conduct business anonymously while making
> absolutely sure that neither is spoofing the other?  Alice needs
> to know Bob isn't lying about being able to factor.  Bob needs to
> know Alice has the means to pay him before he cracks a key.  Bob
> and Alice need to exchange a factored key for money with no
> chance that either will back out at the last moment and try to
> steal from the other.
> 
> How much work should Bob expect to come his way if he charges $10
> a bit for his factoring service?  $100 a bit?  $1000 a bit?
> 
> Comments anyone?
> 
> -- 
>      Mike Duvos         $    PGP 2.6 Public Key available     $
>      mpd@netcom.com     $    via Finger.                      $
> 
> 

Of the several problems stated above, I find the pricing protocol
the easiest to deal with. There are a few things that need to be
known. For example, what is the complexity of Bob's algorithm? Does
it do it in polynomial time or (even better) some variant of logarithmic
time? The cost should bear relation to this fact. The cost should also
be related to the number of bytes in the message. If Bob was canny
enough, he probably would set the price P (in $ or DM or Magic Money or
any other currency I'm grouping under the title "cypherbucks") to be:

			P = F(KB) * L * D

where K (in bits) is the length of the key, L (in bytes) is the length of
the message, D (in cypherbucks/bytes) is the "decoding" cost, B (in
cypherbucks/bits) is the "factoring" cost for the key, and F is a function
from the set of cypherbucks amounts to itself that is proportional to
the complexity of Bob's algorithm. If the algorithm is logarithmic, F should
be logarithmic. If the algorithm takes O(n^2) time, F should be O(n^2); and
so on.

	There are other choices for deriving P; one such is:

			P = F(KB) + (L * D)

and of course others can make their own up. Of course, it is assumed that
Bob is operating as a monopoly, and can set whatever pricing policy he
pleases. For example, 20% discount for students and unemployed. He could
even barter for goods ("I'll decode this 100K message for one of your 
Cray computers.") If the monopoly disappears, the price would be driven
down.

	Alas, I can't say anymore at the moment. Study beckons. :-(
I hope this was of some help.

=======================================================
| Peter Murphy. <pkm@maths.uq.oz.au>.  Department of  |
| Mathematics - University of Queensland, Australia.  |
-------------------------------------------------------
| "What will you do? What will you do? When a hundred |
| thousand Morriseys come rushing over the hill?"     |
|                                       - Mr. Floppy. |
=======================================================

Peter Murphy <pkm@maths.uq.oz.au> writes:

 > Of the several problems stated above, I find the pricing
 > protocol the easiest to deal with. There are a few things
 > that need to be known. For example, what is the complexity
 > of Bob's algorithm? Does it do it in polynomial time or
 > (even better) some variant of logarithmic time? The cost
 > should bear relation to this fact.

[Thud](Sound of Bruce Henderson fainting) This is an interesting
perspective.  I would find myself arguing almost the opposite. It
would seem to me that the price one charges for a product or
service should depend only on its value to ones clients.  Not
upon ones cost to produce it.

If the value of your product to your customers is $100,000, then
the price should be $100,000 regardless of whether it costs you
$1 or $10,000 to make.

 > The cost should also be related to the number of bytes in
 > the message.

I'm not sure about this either.  A short message about a hidden
bomb which reads "under your chair" is infinitely more valuable
than a lengthy message containing the last six months of postings
to rec.pets.cats.

Once Bob gives Alice the factors, all messages encrypted with
that RSA public key can be decrypted, so the number of messages
and the length of each aren't really an issue. Bob could keep the
factors and sell Alice the plaintext of individual messages, but
this requires a continuing business relationship which the
anonymous Bob may not want.

If the messages contain confidential information, Alice may not
want Bob to see them.  Since Alice is paying Bob big bucks to
factor the key, it is unlikely Alice would agree to let Bob keep
the factors to himself.

-- 
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $

> 
> Peter Murphy <pkm@maths.uq.oz.au> writes:
> 
>  > Of the several problems stated above, I find the pricing
>  > protocol the easiest to deal with. There are a few things
>  > that need to be known. For example, what is the complexity
>  > of Bob's algorithm? Does it do it in polynomial time or
>  > (even better) some variant of logarithmic time? The cost
>  > should bear relation to this fact.
> 
> [Thud](Sound of Bruce Henderson fainting) This is an interesting
> perspective.  I would find myself arguing almost the opposite. It
> would seem to me that the price one charges for a product or
> service should depend only on its value to ones clients.  Not
> upon ones cost to produce it.

Not quite. I thought that the price that Bob would set would be as
high as he could get away with, without alienating the clients. If
Alice sends Bob a message to be decrypted, and shells out $100,000,
then Bob (assuming he's honest) will decrypt it. It's too bad if it
turns out to be just a juicy love letter - Bob's purpose was there
to decrypt it, and not to work out the value to the customer. After
all, if it turns out that the file was actually a design to some
FTL vehicle, then setting a flat price in the negotiation phase
prevents Bob from going around and upping the price to $10,000,000.

> 
> If the value of your product to your customers is $100,000, then
> the price should be $100,000 regardless of whether it costs you
> $1 or $10,000 to make.

I'm sorry - we seem to be thinking differently. The way I was thinking
was that Alice was actually giving Bob the message only, and that
Charlie (our suspected criminal) was smart enough to keep his public
key away from the office (or on a floppy disk). Of course, if Charlie
is stupid enough to leave his public key around, then Alice can send
only this key to Bob, and leave the 'naughty' message at the office.
Otherwise, Bob has only the ciphertext to go on - or possibly a bit
of plaintext, although Alice probably won't do that either.

> 
>  > The cost should also be related to the number of bytes in
>  > the message.
> 
> I'm not sure about this either.  A short message about a hidden
> bomb which reads "under your chair" is infinitely more valuable
> than a lengthy message containing the last six months of postings
> to rec.pets.cats.

But again, that's assuming that Alice does know what is in the
encrypted file. She (rightly) suspects that Charlie is giving stolen
goods away.... but she doesn't know that. See above. Anyway, Bob may
have other clients, and the time on his 486 is fairly precious.

> 
> Once Bob gives Alice the factors, all messages encrypted with
> that RSA public key can be decrypted, so the number of messages
> and the length of each aren't really an issue. Bob could keep the
> factors and sell Alice the plaintext of individual messages, but
> this requires a continuing business relationship which the
> anonymous Bob may not want.
> 
> If the messages contain confidential information, Alice may not
> want Bob to see them.  Since Alice is paying Bob big bucks to
> factor the key, it is unlikely Alice would agree to let Bob keep
> the factors to himself.

Ooh.. this is a tough subject to police. It is possible that we have
a company rep (Denise - isn't alphabetical naming beautiful :-)) looking
over Bob's shoulders while he's doing his stuff, and checking that he's
not saving the information to a private file. Possibly, Bob would do the
encrypting in Denise's office. After all, he may have built in an option
that saves all information acquired to a "key ring". Denise does not want
him to do this, and makes sure that he only bring the executable file
with him. She also makes sure that no suspicious files are created .
Remember that Bob does not want to give the program to Denise - it contains
his secret special recipe for factorization, and doesn't want anyone else
to examine the program too closely.

> 
> -- 
>      Mike Duvos         $    PGP 2.6 Public Key available     $
>      mpd@netcom.com     $    via Finger.                      $
> 
> 

=======================================================
| Peter Murphy. <pkm@maths.uq.oz.au>.  Department of  |
| Mathematics - University of Queensland, Australia.  |
-------------------------------------------------------
| "What will you do? What will you do? When a hundred |
| thousand Morriseys come rushing over the hill?"     |
|                                       - Mr. Floppy. |
=======================================================

From: Peter Murphy <pkm@maths.uq.oz.au>
    Date: Sun, 12 Jun 1994 14:40:54 +1000 (EST)

    > It would seem to me that the price one charges for a product or
    > service should depend only on its value to ones clients.
    
    Not quite. I thought that the price that Bob would set would be as
    high as he could get away with, without alienating the clients.

Value can be reasonably defined in terms of what the market will bear.

			Rick