[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Demexp-dev] A first draft of a cryptographic protocol to ensure anonymo
From: |
David MENTRE |
Subject: |
[Demexp-dev] A first draft of a cryptographic protocol to ensure anonymous voting |
Date: |
Thu, 11 Mar 2004 23:33:14 +0100 |
User-agent: |
Gnus/5.1006 (Gnus v5.10.6) Emacs/21.3 (gnu/linux) |
Hello,
You'll find below my first attempt at designing a cryptographic protocol
that ensure needed properties for the DemExp voting part.
I'll be glad if you can find flaws in this protocol, so we could try to
fix them. I'll be more than glad if you try hard but do not find any
flaw. ;)
Of course, it is recommended to give this protocol to people having
knowledge in cryptographic protocols for review.
[ Special note for frédéric: this protocol is different from the one I
presented to you yesterday. I think I have fixed the one major flaw of
the previous one: now a participant cannot change another participant
vote. Moreover, I think we have a recovery procedure in case A's table
is made public. ]
Protocol to make anonymous voting in DemExp
===========================================
Version: 1.0 / 2004-03-11
Notations:
- "h(D)" is the cryptographic hashing of data D (i.e. it is impossible
to find D from h(D));
- a message "m(...)" from A to B is written "A->B: m(...)";
- an action on entity A is written "A:";
- "T_A" is a cryptographic token (i.e. inability to guess the value of
a new T_A);
- "q" is a question identifier, "v" is a vote.
We consider three entities:
- a participant P;
- an authentication server A;
- a question server Q.
We assume we have three secured channels P<->A, P<->Q and A<->Q. The
three of them are encrypted (i.e. nobody can snoop the communication).
Channels P<->A and A<->Q are authenticated (i.e. both ends authenticate
the other remote end). On channel P<->Q, P authenticates Q but P is
anonymous for Q.
We assume that A and Q are correctly programmed (i.e. are not
evil). Following protocol is not valid if A and Q try to vote.
We assume that information stored on P (tokens T_A, T_Q, T_C and vote v,
see below) are not accessible to others (i.e. are securely stored).
* Procedure for first vote:
1. P: creates three tokens T_A, T_Q and T_C
2. P->A: initial_vote_token(q, T_A, T_C)
3. A: A knows P. It checks that this is indeed the first vote and store
state initial_vote# with token h(h(T_A, T_C), T_C) in a table for
question q: |q|P|initial_vote#h(h(T_A, T_C), T_C)|. This table is
private and should be securely stored.
3b. A->P: token_set()
4. P->Q: initial_vote(q, T_Q, T_C, h(T_A, T_C), v)
5. Q->A: initial_vote_check(q, h(T_A, T_C), T_C)
6. A: from previous message, A computes and finds h(h(T_A, T_C), T_C)
for q in its table, with state initial_vote#, so everything is ok.
7. A->Q: vote_ok()
8. Q: stores vote v in a table for question q. This table is indexed by
a cryptographic hash made with T_Q and T_C: |q|h(T_Q, T_C)|v|. This
table is public. Q forgets all other information.
9. Q->P: vote_done()
10. P: P stores T_A, T_Q, T_C and vote v for question q.
* Procedure to change a vote:
1. P: creates two new tokens T_A' and T_Q'
2. P->A: change_vote_token(q, T_A', T_C)
3. A: P is authenticated, table of question q contains state
initial_vote#, so A stores state changed_vote# with token h(h(T_A',
T_C), T_C): |q|P|changed_token#h(h(T_A', T_C), T_C)|
3b. A->P: token_set()
4. P->Q: change_vote(q, T_Q, T_C, T_Q', h(T_A', T_C), v')
5. Q->A: change_vote_check(q, h(T_A', T_C), T_C)
6. A: from previous message, A computes and finds h(h(T_A', T_C), T_C)
for question q in its table, with state changed_vote#, so everything
is ok.
7. A->Q: vote_ok()
8. Q: Q finds vote for key h(T_Q, T_C). It stores new vote v' in the
table for question q with a new index made with T_Q' and T_C:
|q|h(T_Q', T_C)|v'|. Q forgets all other information.
9. Q->P: vote_done()
10. P: P stores T_A', T_Q' and T_C and vote v' for question q.
* General remarks:
o T_A, T_Q and T_C can be seen as stamps on a vote card. Their
combination uniquely identifies P with agreement of A and Q. T_C can
be seen as a checking token.
o Hashes are explicitely made on A and Q at steps 3, 6 and 8, so nobody
cannot impose its own arbitrary strings for hash results. In other
words, we are sure that keys in A and Q tables are made with part of
information coming from the other server.
o We could probably reconsider the protocol without secure and
authenticated channels. It might bring more security (we could hide
some information to all except one entity) but it would be more
complicated and probably more difficult to implement.
* Guaranteed properties
o Only P knows about its vote. Regarding A, A knows identity of P, T_A
and T_C but only store h(h(T_A, T_C), T_C). It does not know about
T_Q. Regarding Q, it knows the vote, T_Q and T_C but does not know
T_A (masked through h()). From the public table |q|h(T_Q, T_C)|v| of
Q, it is impossible to guess the link between T_Q and T_C (because of
h()). Similarly for table |q|P|state#h(h(T_A, T_C), T_C)|.
o Only P can change its vote. Only P knows T_A, T_Q and T_C and all
tokens are necessary to change a vote. Most notably, T_A is never
seen by Q and T_Q is seen by A.
o Nobody can monitor vote change. A new key for a vote in Q's table is
created each time a vote is created or changed.
o The vote can be checked. As table |q|h(T_Q, T_C)|v| is public, every
participant P can check its own vote v (using stored T_Q, T_C and v)
and recount the whole vote result.
o P cannot set initial vote for another participant. P is authenticated
on A when it sets an initial_vote# token, and a participant P' can
always set its initial token. In other words, in A there is always at
most one initial token for each participant.
o P cannot change another participant vote. To change a vote, one needs
the three initial tokens T_A, T_Q and T_C which are known only by the
participant. One cannot guess T_Q neither T_C from public table
|q|h(T_Q, T_C)|v| of Q. Similarly for T_A and T_C from private table
|q|P|state#h(h(T_A, T_C), T_C)|. Moreover, entries in A and Q tables
are synchronised through the use of T_C.
o P cannot vote twice. Q and A are synchronized for first vote and
subsequent changes through the storage of states initial_vote# and
changed_token# in A and use of messages initial_vote_check() and
change_vote_check() in Q. Once P as set its initial token, it cannot
set a new initial token. For initial vote, in step 8, h(T_Q, T_C) is
made by Q from T_Q and T_C so P cannot set an arbitrary string for
h(T_Q, T_C). P checks h(T_A, T_C) validity with A. Idem for step 8
for vote change procedure.
o A's table |q|P|state#h(h(T_A, T_C), T_C)| is private. However, if it
is made public, nobody can find the vote of P from h(h(T_A, T_C),
T_C) and h(T_Q, T_C). Moreover, if one forces all participants to
start a vote change procedure from step 1 (by invalidating all tokens
in changed_vote# or initial_token# state and letting participants to
set a new token), participants can change their vote without Q being
able to guess the voter.
* Known weaknesses
o Timing attacks have not yet been considered.
o The A's table should remain private.
== End of protocol ==
Yours,
d.
--
David Mentré <address@hidden>
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Demexp-dev] A first draft of a cryptographic protocol to ensure anonymous voting,
David MENTRE <=