[E-Lang] Ownership certificates via capabilities?
Sat, 24 Feb 2001 13:32:45 -0800
I had a crypto dream last night. I'd gone to visit a couple of
cryptographers at a university. They had invited me to show me a bug in
a pseudo random number generator I had written, but then we got talking
about another problem.
These two guys were into trading card games, like Magic The Gathering.
These games are played with cards that represent different characters
and artifacts that have certain powers. Players buy these cards at the
store or from each other, and then they play against each other by laying
their cards out according to the rules of the game.
In the dream these guys actually set up a folding table in front of the
school cafeteria and began laying out the cards to sell to the students.
But then they were talking about wanting to implement the same kind
of game in electronic form. People would have electronic files which
represented the cards and use them when they played the game.
The question was, could this be done in an offline way, since players
often get together at a place where there is no Internet connection.
Perhaps they could each bring a portable computer and hook them together
directly or via an IR connection.
The cryptographers said they were trying to find a way to do it with
capabilities. Each card would be represented by a capability. I thought
about that and it seemed that the problem would be that when you used
your card in a game, the other player could see its value and steal it
by copying the capability. So it does not appear that it can be done.
That was as far as it went in the dream, but afterwards I was trying to
decide if it could be done using a different technology, certificates.
The idea would be that each card would be represented by a certificate
signed by the game manufacturer which said what the card type was. If
this was all there was, people could easily copy cards. So I think what
you would have to do is to have the game owner operate a database of
who owns what cards. This could be a distributed database represented
by the certificates.
Each certificate would therefore hold both the card type and the owner
ID. This would be cryptographically signed by the game manufacturer.
When you bought a new card from the manufacturer they would issue you
a new certificate. When you sell a card to someone else, the game
manufacturer would revoke your certificate and issue a new cert for the
new owner. It might do this by adding the revoked certificate to its
Certificate Revocation List (CRL).
I know certificates are not particularly well thought of around here, and
CRLs are even less well respected among cryptographers. Nevertheless both
of these seem to be necessary to solve the problem.
Timeliness is always an issue with CRLs. You might have to have a rule
that game cards can be transfered between players only during certain
hours, and then games are played at other times. Then if at least one
of the players were able to supply an up to date CRL at the beginning
of the game (having downloaded it earlier), each player would know that
the other could not falsely misrepresent a sold card as one he still owns.
So, with these caveats and restrictions, the problem seems to be just
barely solvable with certificates and CRLs. The question is, then, is
there any corresponding way to achieve this with capabilities? That is,
could you have virtual objects which are owned, and people can interact
with them off-line under agreed-upon rules, but be confident that people
in fact own the objects which they claim to?