[Demexp-dev] A first draft of a cryptographic protocol to ensure anonymous voting

[David MENTRE]

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>