Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:11:00
Berke Durak (berke@gsu.linux.org.tr)
Fri, 21 Aug 1998 22:23:17 +0300 (EEST)
No-one seems to have given attention to the proposition about the "anonymous
identification protocol". Maybe it is logically infeasible, however it would
prove useful. This is a quote from my first posting:
And some kind of "anonymous identification protocol" that would
allow users knowing each other to mutually identify themselves,
without revealing any information on their identities if they don't,
while allowing individuals to remain "unknown" for people they know
but do not wish to discuss with that day would be very useful.
I hope this will be a clearer explication:
Problem Level I
Two people meet on an anonymous chat network. They wish to know, without
revealing information to the network, if they already know eachother, and if
this is the case, they want to identity themselves.
Naive/Trivial Solution I
Establish a crypted link. Send identities. Authenticate using public keys or
whatever.
Problem Level II
Two other people meet on the same network. They again wish to identify
eachother, but no one wants to reveal his identity (i.e. his public key ID
or whatever) to strangers.
Naive/Trivial Solution II
Each user encrypts, using his secret key, a random challenge. They then
exchange this encrypted data, WITHOUT ANY KEY ID INFO. Each user then
attempts to decrypt the encrypted challenge using ALL THE PUBLIC KEYS HE
HAS. If he succeeds, he identifies the other party. Of course, this is in
O(n), and here, the "hidden constant" for computational cost is very high,
since we all know that public key operations are very costy.
Problem Level III
Two people, Alice and Bob, engage in deep conversation on an anonymous
chat network. They find that they have so much interest areas in common that
they wonder if they do not know eachother already. But Bob owes money
to Alice and does not want to talk to her, nor does he want to reveal
his true identity to her. They wish to conduct the "anonymous identification
protocol", but Bob does not want Alice to know who he is.
Naive/Trivial Solution III
Bob takes a random challenge number X from Alice (but he does not (yet) know
the identity of Alice). He appends to it a challenge number Y he creates.
He then encrypts this using his secret key S_B, and for every person he
wishes to speak with, makes a separate encrypted copy with that
person's public key. Let n be the number of people Bob wishes to have
a talk with that night; let P_1,P_2,...,P_n be these people's public
keys. Bob sends E_{P_1}(E_{S_B}(X.Y).X), E_{P_2}(E_{S_B}(X.Y).X), ...,
E_{P_N}(E_{S_B}(X.Y).X) where dot "." means concatenation.
He then sends all these n vectors to Alice.
Alice then tries to decrypt all the n vectors using her secret key;
if she processes a vector encrypted using her public key, she will
get Z.X, where X is the challenge number she sent to Bob, and
Z is the vector encrypted using Bob's secret key, which is still
"opaque" to her, but she knows she succeeded the first decryption
from the "X" that is appended. She now tries every public key
she has on the "Z" vector; when she obtains X.Y, she knows
the identity of Bob. If Bob does not wish to talk with Alice,
he simply does not use her public key to encrypt a vector.
The challenge numbers are used against replay attacks; I guess there would
have to be more subtleties for a real implementation.
If Alice does not wish to talk to Bob, she responds negatively
to the protocol. Bob has no means of knowing if Alice succeeded
in determining his identity or not.
Thus, this protocol is unfair. The protocol initiator (Bob)
has disadvantage over Alice, since she can learn Bob's identity
without Bob learning hers. Therefore we have:
Problem Level IV
Same as Problem Level III, except that if one party does not want to talk to
the other, the identification fails, but no party has information on the
identity of the other one.
Now I have read the "simultaneous secret exchange" and "all-or-nothing
disclosure of secrets" in A.C. but I can't figure out how to apply these
protocols to this situation. I don't even know if this is feasible.
However, if feasible, it would provide, on an anonymous communication
network, means for people to manage the knowledge of their identity, i.e.
they could choose "who can learn who they are", and this, mutually.
Any ideas ?
Berke Durak - berke@gsu.linux.org.tr - http://gsu.linux.org.tr/kripto-tr/
PGP bits/keyID: 2047/F203A409 fingerprint: 44780515D0DC5FF1:BBE6C2EE0D1F56A1
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:11:00