[4259] in cryptography@c2.net mail archive
Re: Crypto for some of the DNS/TM mess
daemon@ATHENA.MIT.EDU (Anna Lysyanskaya)
Wed Mar 3 12:48:57 1999
Date: Tue, 2 Mar 1999 17:31:20 -0500 (EST)
From: Anna Lysyanskaya <anna@theory.lcs.mit.edu>
Reply-To: Anna Lysyanskaya <anna@theory.lcs.mit.edu>
To: froomkin@law.miami.edu
Cc: cryptography@c2.net
Dear Mr.Froomkin (and cryptography@c2.net),
Ron Rivest, Amit Sahai and I have a scheme that may (or may not) help you.
The current version of the paper "Pseudonym Systems" is available from my
homepage, http://theory.lcs.mit.edu/~anna. Here is a high-level sketch of
how our scheme would work in this instance. The scheme we propose is
relatively simple and practical.
We can use a pseudonym system to implement this domain name question.
Pseudonym systems were introduced by Chaum in 1985, as a way of allowing a
user to work effectively, but anonymously, with multiple organizations. He
suggests that each organization may know a user by a different pseudonym,
or {\em nym}. In this case, we will have a nym associated with each
domain name. These nyms are unlinkable: two organizations can not combine
their databases to build up a dossier on the user. Nonetheless, a user
can obtain a credential from one organization using one of his nyms, and
demonstrate possession of the credential to another organization, without
revealing his first nym to the second organization. For example, Bob may
get a credential asserting his good health from his doctor (who knows him
by one nym), and show this to his insurance company (who knows him by
another nym). The user's identity is in some ways embedded into all the
nyms and credentials that the user owns.
Now, in the domain registration scenario, the registrants will be users,
the owner of the whois database is the central authority that issues
the credential of validity, and anyone who wishes to interact with
a domain owner and grant it privileges or what have you is another
organization.
The setting in the physical world:
---------------------------------
1. There is a trusted center that is able to verify the physical identity
of whoever approaches it. The first time an individual approaches the
system, the cost of this might be high (however I don't see how to avoid
this -- otherwise people can give totally bogus contact info!), but any
subsequent time it can be done automatically (authentication).
2. The trusted center can publish a database of people who have approached
it, with all their contact information and public keys.
3. Each person has a master public/secret key pair, that goes hand in
hand with his physical identity. He wants to protect his secret key at all
times. This requirement is a little bit ahead of its time, and so we can
just require that the user picks his pk/sk when talking to the trusted
center for the first time, but then there won't be anything to prevent
Alice from enabling Bob to impersonate her, which may or may not be a
problem.
Computational assumptions:
--------------------------
Diffie-Hellman-like.
The result:
-----------
Here is what I think is a logical way to implement what you want:
1. Registration.
The user Alice contacts the central authority. The central authority can
verify her identity. In the event that users don't already have pk/sk
pairs that are tied to their identities, Alice establishes her pk/sk at
this point. Now Alice authenitcates herself to the CA with her pk. Once
the central authority is satisfied that it has been talking to user Alice
who has a public key, it enters this public key and Alice's name and
contact information into a world-readable database (note that this
database is totally separate from the domain database), and issues a
credential of validity to Alice. Credential issue operation is like the
blind signature operation: only the recipient knows what the credential
looks like.
Now Alice goes to the domain issuing authority (which may incidentally be
the same organization), establishes a pseudonym with it, and proves to it
that it has a credential of validity from the CA. The domain issuing
authority grants Alice ownership rights for the domain, and enters her
pseudonym, credential and domain name into some database.
2. Transactions.
Once Alice owns a domain, she enters into transactions with various
organizations and authorities. At some point, an organization might want
to grant a credential to a domain that Alice owns (e.g. that the owner of
the domain is allowed to distribute something... or has a bank account...
or what have you). The pseudonym system will allow Alice to prove the
truth of these statements to an organization that knows Alice by another
domain name. Details in the paper.
3. Subpoena.
Alice just points to the entry in the CA's table that contains her public
key, and proves that the corresponding secret key also is the secret key
for all her pseudonyms and credentials. Nobody other than Alice can
compute Alice's identity. If, in the event of a subpoena, the owner of the
domain refuses to cooperate and reveal his identity, he may not use the
domain any longer (which is I think what you asked for).
So that takes care of your requirements 1) and 2). As for 3): when the
need to establish how many domain names a user owns arises, the user can
be asked to reveal the list of all the credentials of validity ever issued
to him by the CA and prove that all these credentials correspond to the
same secret key. With this list, the third party can scan the appropriate
database and find out how many domains a user owns. The CA knows how many
credentials of validity have been issued to a user, and so a cheating user
will be detected. Or we may insist that the CA gives out only one
credential of validity per user, and then anyone can determine which set
of domains belong to the same user.
In my opinion, however, requirement 3) is unnecessarily restrictive. I
don't see why someone should be able to identify a set of domains as
belonging to the same user. This requirement can be an impediment to
online commerce and other such endeavors. A reasonable way of preventing
users from having too many domain names is: set a limit to how many
domain names can be registered with the same credential of validity (say,
ten) and how many credentials of validity a CA grants (say, ten). Then we
can be sure that no user in the system will own more than a hundred domain
names. This seems to accomplish what you want, without the need for
someone to come in and find out specifically which domains belong the same
user.
Alternatively, if the problem is that a user with 100 domains will be able
to vote 100 times, but it's just one user, the solution is even simpler
than that. In that case, we may ask the CA to issue a unique voting
credential to each user, and it is up to the user at which domain to
publish this credential. A vote will only be accepted if it comes from a
domain that holds a voting credential. That gets rid of the multiplicity
problem while retaining all the advantages that anonymity brings.
Anyway, please tell me what you want to accomplish with requirement 3) and
maybe there are ways to relax it in such a way as to better protect
anonymity and privacy.
Hope this helps!
:)
Anna Lysyanskaya
