From: Alex Strasheim <alex@proust.suba.com>
Date: Fri, 29 Dec 1995 13:00:08 +0800
To: cypherpunks@toad.com
Subject: blind validation
Message-ID: <199512281849.MAA08259@proust.suba.com>
MIME-Version: 1.0
Content-Type: text/plain


With all the recent Congressional activity, I've been thinking
about blind validation.  I know that other people (Chaum, for
one) have considered it, but it's not something that's talked
about online very often.  I'd like to kick off a discussion. 

I'm not good with protocols, there are almost certainly some
flaws in my thinking, and I'm not familiar with much of what
others have written on the subject.  Any pointers or constructive
criticism will be greatly appreciated.


I    Basicd

(Almost everyone here will be familar with this stuff;  I'm
including it for completeness.)

By "blind validation", I mean allowing someone to prove that
they're entitled to do something without making them tell you who
they are.

One obvious application of blind validation is to allow people to
download adult material anonymously while making sure that
children don't have access.  Other applications might be allowing
US citizens to download crypto software anonymously, or giving
members of a University community anonymous access to computing
resources that aren't available to the general public.

Why is blind validation desireable?  Without blind validation,
it's possible to build large and intrusive databases by linking
together the various fields on your ID cards, especially your
social security number.

When someone goes to a liquor store and shows an ID, he doesn't
just prove he's over 21.  He tells the clerk his name and
address, and whether or not he wears glasses, among other things.

This isn't a big problem when you're showing your ID to a clerk,
because the clerk is a human being who won't remember your name
or address.  But a computer has a very good memory, and groups of
computers are very good at assembling data from disparate
sources.  There are already online services that do this.  

Westdata, for example, offers a service that allows customers to
search a database assembled from a variety of sources -- census
information, real estate transactions, credit information,
telephone directories, and the like.  It's pretty easy to go
online and find someone's SSN, and once you've got that it's
possible to retreive all sorts of information.

This is why it's sensible for us to give out as little
information as is ncessary to accomplish whatever it is we're
trying to do.  That's what blind validation is all about.



II   Transferability -- blind validation's big problem.

Suppose Alice is allowed to do something.  How can we prevent her
from giving Carol the right to do it as well?

We can't.  This is true of any (ok, I don't know that -- most)
validation scheme, not just blind scehems.  I can give away a
unix account's login name and password, or even my PGP key.  

But conventional validation schemes have a big advantage over
blind ones:  in non-blind validation, users can be held
accountable for the people they let in.  If I give someone access
to my unix account and they post photoshop disk images to usenet,
I'll be held responsible.  I have a strong incentive to keep my
password secret.

If I can get blind validation to do something, I can't be held
accountable for my own actions, or for giving access to someone
else.  This fact drastically reduces the number of situations in
which blind validation is useful.

Here's a simple blind validation protocol that won't work:

1.   Alice generates a random number, blinds it, and sends it to
     Trent along with proof that she's validateable.

2.   Trent checks Alice's proof of validatability, signs her
     blinded number, then returns it to her.

3.   Alice unblinds her number and sends it to Bob, along with a
     request for a download.

Then Alice uses a remailer to post her number to usenet, along
with Trent's signature, and Bob has to let everyone who reads net
news download files.

Even a ticket based protocol similar to ecash won't work.  Let's
assume that Bob wants a ticket in exchange for a file, and that
he checks the tickets people give him for double spending. 
What's to stop Alice for getting a thousand tickets from Trent
and giving them to her friends?  Tickets aren't ecash -- they
don't cost anything.  Trent will give a ticket to anyone who can
prove he's validatable, and there's nothing preventing Alice from
going back for tickets over and over again.


III  Kids and Liquor Stores

Imagine a group of teenagers who want to buy some booze.  Let's
consider two attacks they can mount on a liquor store:  they can
go in and try to trick the clerk into selling to them, or they
can hang around in the parking lot and try to convince an adult
to buy for them.

The liquor store wants to keep its license, so it tries hard to
defend against the first attack.  But there's nothing they can do
about the second attack, and what's more, they really don't have
to worry about it.  If they give booze to minors, they can lose
their license or possibly even face criminal charges.  But if
some other adult gives booze to the minors, he's responsible. 
It's not the liquor store's problem.

If the kids get their booze from the clerk or another customer,
the end result is the same:  the kids are able to get drunk.  But
from the store's point of view, there's a big difference, the
difference between losing their license and keeping it.

This is very different from the attitudes of the participants in
most crypto protocols.  If I use a protocol to exchange secure
email, I don't want anyone except the recipient to read it.  It's
not much comfort for me to be able to say, "It's not my fault,"
if the mail becomes public.

But the liquor store has to be able to live with the possibility
that a kid will get ahold of some booze from their shelves.  If
that's absolutely unacceptable to them, the only thing they can
do is close their doors or make patrons drink up in front of the
clerk, because they can't prevent a customer from giving a bottle
to a minor.  The main interest of the liquor store is to avoid
blame for underage drinking, not to make absolutely sure that
kids can't drink.



IV   Alice, Bob, and Sam.

Let's assume that Bob is running an FTP archive with crypto
software, and Alice wants to download it.  Alice wants to remain
anonymous.  Let's assume that a blind validation scheme, where
Alice proves that she's a US citizen while remaining anonymous,
is acceptable to both of them.

If a blind validation scheme is acceptable, why isn't no
validation at all?  Obviously Alice ought to be satisfied with no
validation.  She wants the file, and she wants to remain
anonymous.  If Bob doesn't use any validation, Alice is still
happy.

But what about Bob?  Bob's not an idiot.  He knows that if he
distributes crypto software on the net, someone's going to send a
copy to Europe, and if he uses blind validation he won't be able
to find out who did it.  Consequently, if the software's
appearance in Europe is totally unacceptable to Bob, he won't
distribute it with blind validation.

If Bob can live with the software appearing in Europe, why does
he want to use blind validation to check for citizenship?  The
answer, obviously, is that Sam (as in Uncle, the government) has
told Bob he'll be imprisoned if he exports the software.  The
blind validation scheme will let Bob distribute the software
anonymously (which is what he wants to do) and prove to Sam that
he's followed the letter of the law.

In general, it doesn't seem that there are many situations that
only involve Alice and Bob where blind validation makes sense.
If Bob is willing to accept the increased risk of transferability
that comes with blind validation, he'll probably be willing to
accept no validation at all.  Blind validation becomes useful
primarily when you add Sam to the mix.

This isn't an absolute truism of course.

Let's think about a library card catalog at a University.

I remember a conversation I once had with an INS investigator, in
which he told me that he sometimes asked for a list of all the
books his targets had taken from the public library.  You can
learn a lot about someone from what they read, or even from their
card catalog searches.

I know that some universities restrict access to their card
catalogs to students, faculty, and staff.  Why?  Because they
don't want to shoulder the cost of providing a research tool to
the entire net.  They're not trying to protect the information --
they're trying to reduce load on their library computer.

Perhaps a University might recognize that there there's some
value in using a blind authentication system to grant access to
the catalog.  It could protect the privacy of the people using
the catalog, and still do a reasonably good job of keeping out
people who shouldn't be involved.

The role of Sam in this discussion might be one of the reasons
that blind validations haven't generated much interest on the net
in general or on the cypherpunk list specifically.  If blind
validation is privarily useful for cooperating with laws we don't
agree with, then it's not unreasonable to look at it as a
technology of collaboration.  A viable blind validation scheme
might make censorship more attractive.


V    A protocol

Let's assume that Alice knows that Bob and Trent are who they
claim to be, and that she can talk to Bob anonymously, perhaps
through a chain of remailers or a dc net.  This protocol isn't
intended to protect Bob's privacy, only Alice's.

We also assume that there's some sort of system in place for non-
blind validations.

1.   Alice initiates a transaction with Bob.  (Perhaps by asking
     him for a file.)

2.   Bob generates a random number and sends it back to Alice.

3.   Alice blinds Bob's number and sends it to Trent, along with
     proof of her validatability.

4.   Trent checks Alice's proof, signs the blinded number, and
     then returns it to Alice.

5.   Alice unblinds Bob's number, then sends it to Bob.

6.   Bob checks Trent's signature and makes sure that the number
     he recieved matches the one he sent out.  Then Bob processes
     Alice's transaction.

If Bob always follows this protocol, he can prove to Sam that
he's followed the law.  Alice remains anonymous.  Alice can still
transfer the file, but she has to give it away herself:  she
can't give away the ability to get it directly from Bob without
giving away the ability to prove Aliceness to Trent.  This means
that she'd have to accept all the consequences of giving away
non-blind validatability.

The main problems that I can see with this protocol are:

1.   It's vulernable to traffic analysis.
2.   Sam has to trust Trent, which he may be unwilling to do.
3.   You can infer stuff about Alice from the kinds of requests
     she makes of Trent.  Someone who always asks Trent for proof
     that he's not a felon might tag himself as a person who buys
     a lot of guns or ammunition, for example.

I'd like to put Trent out of a job, but it's hard to imagine a
Trentless system without Chaum's observer chips.  I've read Hal's
criticisms of observer chips, and what he says makes sense to me.

But observer chips could be more appropriate in a blind
validation situation than they are with ecash.  Ecash security
has to be bullet proof, but if we can live with transferability
in a blind validation system we've already given up on such
rigorous security.