Pàgina d'inici > Criptografia, Matemàtica, Política > Sistema de votació electrònic amb garantia d’autenticació i anonimat

Sistema de votació electrònic amb garantia d’autenticació i anonimat

Ahir a la nit, mentre donava voltes al llit sense poder dormir, vaig estar rumiant sobre un problema que ja fa temps que em balla pel cap : Com s’hauria de dissenyar un sistema de votació electrònic amb garantia d’autenticació i anonimat ?

Perquè ens entenguem, la idea és intentar traslladar el, per exemple, tradicional sistema presencial de votació de les eleccions generals del proper 20N, a un sistema amb les mateixes prestacions que funcioni íntegrament per suport electrònic (a Internet, per exemple). A primer cop d’ull sembla una idea poc útil, però de ben segur que els milers de persones que han estat convocades (per obligació) alguna vegada a les taules dels col·legis electorals durant els comicis, sabran apreciar els avantatges d’utilitzar un mètode no presencial.

Analitzant el problema, ràpidament s’observa que les principals condicions que requereix el sistema són l’autenticació i l’anonimat.

És a dir, cal que l’entitat que s’encarrega de centralitzar i fer el recompte dels vots pugui cerciorar de forma inequívoca que cadascun d’aquests vots prové d’un elector vàlid, alhora que també cal conservar l’anonimat de l’elector, és a dir, no s’ha de poder conèixer de cap manera quina ha estat l’elecció del seu vot. Aquests requisits que semblen tant simples, com es pot comprovar si s’hi reflexiona una mica, son totalment contraproduents, de manera que aconseguir dissenyar un sistema que compleixi les dues condicions, lluny de ser trivial, començo a tenir dubtes de si realment és possible.

Així doncs, el disseny d’un sistema de tals característiques ja ha començat a transcendir de les meves inquietuds nocturnes, i de fet avui s’ha convertit en tema de debat durant l’hora d’esmorzar, juntament amb un bon company molt especialitzat en el tema, i amb el que, tot i plantejar esquemes força interessants, hem estat incapaços d’arribar a una solució factible. És per això que m’agradaria fer-ne encara més ressò, per veure si realment algú és capaç d’arribar a alguna bona conclusió.

Sobre el plantejament, i entrant ja en l’anàlisi estrictament del problema, cal dir que la garantia que dona el fet de realitzar les eleccions de forma presencial, a mètode d’urna amb un sobre tancat per cada vot, i un interventor independent responsabilitzant-se i verificant la identitat de cada votant, tot i ser una manera àmpliament consensuada d’aconseguir l’anonimat i l’autenticació, tampoc és fiable al 100%, ja que l’autenticació pot ser falsejada, al mateix temps que l’anonimat pot tenir un percentatge baix d’entropia quan es divideix el total  del cens en moltes urnes (com menys vots per urna, més fàcilment es pot elaborar una estimació estadística de quin ha estat el vot de cada elector). Per exemple, si en un municipi només hi ha censades 2 persones, tot i entregar el vot en un sobre tancat de forma anònima, es pot estimar en un mínim d’un 50% l’elecció de cada participant, o encara més, si els 2 resultats són els mateixos, sabrem del cert al 100% què ha votat cadascú. Així doncs, aconseguir l’anonimat en el sistema de votació no és tant senzill com sembla, doncs inclús els utilitzats actualment de forma oficial tenen els seus defectes, que depenen directament de la quantitat de resultats diferents que es comptabilitzen, i de la segmentació amb que es fa l’escrutini, per la qual cosa sempre s’ha de tenir en compte que l’anonimat al 100% és impossible d’aconseguir, i tant sols se’n podrà garantir un llindar percentualment acceptable.

Son però, aquests petits i despreciables defectes, els que a l’hora de traslladar el problema al món electrònic impossibiliten un mètode fàcil i fiable d’implementació. El problema de l’autenticació és fàcilment resoluble amb una firma digital, assignant a cada elector una paritat de claus asíncrones. De fet, i des de fa molt de temps, existeixen múltiples solucions que ja ho implementen de diverses maneres (l’anomenat vot electrònic), a més de ser un tema que actualment està sobre la taula de molts debats polítics a arrel de les recents crítiques al sistema “democràtic” amb que s’escull l’actual representació de l’organisme executiu i legislatiu, com pot posar de manifest amb un clar exemple la proposta de Democràcia 4.o.

El problema però, recau a l’hora de voler introduir en aquest mateix sistema la garantia de l’anonimat, tal com evidencia el fet de que cap d’aquests sistemes existents ofereixi tal característica. Podem pensar que xifrant i firmant el nostre vot es pot conservar l’anonimat vers els demés electors, però al moment d’enviar al centre autoritzador la teva firma juntament amb la teva elecció de vot, queda en mans d’aquest garantir que aquesta vinculació es trencarà, i que ningú coneixerà quin ha estat el teu vot. Així doncs, penso que fer recaure la confiança de l’anonimat en un tercer no és garantia pel sistema, doncs la bona voluntat mai hauria de ser un factor, ja que aporta un grau indeterminista al problema, i impossibilita la seva resolució.

Buscant l’analogia en el sistema presencial, es pot traslladar la idea de llançar varis sobres tancats dins d’una urna i barrejar-los, un cop autenticada la validesa de cadascun d’aquests vots, trencant així la vinculació entre elector vàlid i vot. Implementar aquest concepte dins d’un entorn digital però és força complicat, doncs es requereix d’una operació que aporti un factor d’atzar, que a més, pugui ser garantit per a tots els participants. Aquí és on es troba la principal qüestió del problema, i on hem divergit en les possibles solucions.

Jo particularment, la solució més viable que fins ara he trobat, tot i que no m’agrada per la seva alta complexitat, consisteix en un sistema on s’implementa un recorregut del missatge que representa el conjunt de tots els vots (cadascun xifrat), de manera que circuli per tots els electors, els quals, un per un, reordenen el missatge per generar una assignació on, cadascú coneix quina és la seva posició (on ubicarà el seu vot), però li és impossible saber a qui li corresponen les demés posicions on la resta ubicarà el seu vot. El fet de que cada elector del sistema faci una reordenació aleatòria, garanteix que realment es trenca la vinculació entre elector i elecció, doncs per tornar reconstruir l’ordenació inicial és imprescindible saber totes (sense excepció) les reordenacions que s’han fet, de manera que des del punt de vista d’un elector, no publicar quina ha estat la seva reordenació li atorga la garantia de que el seu vot serà realment anònim. Caldria detallar una mica millor la idea (que de moment està en forma d’esborrany sobre el tinter), però de moment penso que aquesta hauria de ser la direcció a prendre per trobar la solució més correcte. No cal dir però, que de ben segur que deuen existir altres mètodes que no he tingut en compte, de manera que deixo el debat obert a noves idees o propostes.

Lluny de semblar doncs un problema particular en l’àmbit acadèmic, crec que dissenyar solucions a aquest tipus de plantejaments aporta un valor més que tangible en la nostra societat, demostrant la interrelació que hi pot haver en disciplines tant distants com poden ser la política i la matemàtica, i deixant en evidència que a vegades, aquelles coses a que menys importància ens reflecteixen, acaben sent les que realment aconsegueixen canviar el món.

Afegir com a últim repunt en forma de complement, la idea relacionada que sempre he manifestat sobre la validació / publicació de l’elecció de vot. Crec que un sistema que vulgui ostentar un mínim de garanties de ser fidedigne (no corruptible), hauria de poder incorporar de facto la possibilitat de que cada elector pogués comprovar que el seu vot realment s’ha comptabilitzat allà on ell ha indicat. De fet, qualsevol analista a qui se li plantegés el problema consideraria intrínseca aquesta mesura en la solució. No obstant, no cal ser cap geni per donar-se compte que els actuals sistemes que tanta acreditació popular se’ls confia no implementen tal característica, atorgant a mans d’una minoria la bona voluntat de que el sistema realment sigui fiable… A vegades és atònit comprovar la bona fe amb que la gent acredita el seu futur a altres desconeguts. En definitiva, i sense voler encetar un nou debat paral·lel (ho reservo per un nou post), crec que és remarcable aquesta qüestió que per tants sol ser d’irrellevant importància a l’hora d’analitzar aquest tipus de sistemes. Inclús aprofundint fins al final sobre el tema de l’anonimat, i essent conscient de que existeixen formules per garantir la prestació de validació del vot conservant l’anonimat, crec que la millor solució, tot i ser conscient de que això pot comportar coacció, és el vot públic. Si alguna cosa m’ha ensenyat la criptografia, és que el sistema més segur i fiable no és aquell que ningú coneix, sinó aquell que tothom coneix.

Dit això, la meva proposta de procediment per aconseguir resoldre el problema és :

Donats N usuaris que realitzen una votació amb R resultats. Cada usuari disposa d’un par de claus pública/privada (U[N].pub / U[N].pri).
Existeix un “Centre autorizador” (CA) que acredita que els usuaris són vàlids, a l’hora que els comunica entre ells.
El CA també disposa d’un par de claus pública/privada (CA.pub / CA.pri).
El procediment a seguir és :
1. Tots els usuaris escullen un vot fals aleatori qualsevol, el seu vot autèntic, i dos identificadors aleatòris (Id.pri1, Id1.pri2). Cadascu xifra (amb CA.pub) el vot fals juntament amb el Id.pri1, i el voto autèntic amb el Id.pri2, obtenint un vot xifrat fals (vf) i un vot xifrat autèntic (va).
2. El CA selecciona un usuari al atzar per començar la votació (U1).
3. U1 escull un altre identificador aleatòri (Id1.pub1) i l’afageix a vf1 (m1 = vf1+Id1.pub1). Ho xifra amb la clau pública del següent usuari (U2), ho firma, i li envia al següent usuari a través del CA.
4. U2 rep el missatge de U1 i el desxifra (obtenint Id1.pub1 i vf1). Escull un altre identificador aleatorio (Id2.pub1), diferent a Id1.pub1, i l’afegeix a vf2 (m2=vf2+Id2.pub1). U2 uneix m1 y m2 (en qualsevol ordre), ho xifra amb la clau pública del següent usuari, ho firma, i li envia al següent usuari a través del CA.
5. El següent usuari realitza la mateixa acció, afegint el seu vot.
6. L’últim usuari (UN), realitza la mateixa acció, i envia el missatge (ja amb tots els vots falsos), al primer usuari (U1).
7. U1 comprova que el seu vot fals xifrat (vf) segueix estant al missatge, juntament amb el identificador Id1.pub1. Substitueix el vot fals xifrat per el seu vot autèntic xifrat (va1), i li asigna un nou identificador aleatori (Id1.pub2), diferent a tots els identificadors Id.pub1 del missatge. Reordena tots els vots xifrats amb els seus identificadors, ho xifra, i li envia al següent usuari (U2).
8. U2 realitza la mateixa acció (substitueix el seu vot fals per l’autèntic, li asigna un nou identificador Id.pub2, ho reordena, i ho envia al següent usuari).
9. L’últim usuari (UN), realitza la mateixa acció, i li envia el resultat a CA.
10. CA rep tots els vots autèntics xifrats, juntament amb els seus Id.pub2. Els desxifra un per un, obtenint cada vot vinculat al seu Id.pri2 i Id.pub2.
11. CA Publica la llista. Cada usuari pot comprovar que el seu vot correspon al que ha realitzat mitjançant Id.pub2 i Id.pri2, sense ser capaç de distingir a quí pertany cadascun dels demés Id.pub2 / Id.pri2.

Amb un exemple pràctic :

4 usuaris (U1, U2, U3, U4) realitzen una votació amb 3 opcions (A, B, C) :

usr vot fals vot aut. Id.pri1 Id.pri2 Id.pub1 Id.pub2 VF VA m a
1 C A 33 5 21 39 [C33|CA.pub] [A05|CA.pub] VF01,21 VA01,39
2 B A 45 50 20 33 [B45|CA.pub] [A50|CA.pub] VF02,20 VA02,33
3 C C 33 39 59 9 [C33|CA.pub] [C39|CA.pub] VF03,59 VA03,09
4 A B 12 27 18 44 [A12|CA.pub] [B27|CA.pub] VF04,18 VA04,44

1. U1 escull Id1.pub1 (21), i genera m1 = VF01,21. Ho xifra amb U2.pub, i genera el missatge M1. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U2 :

M1 [m1|U2.pub]

2. U2 escull Id2.pub1 (20), i genera m2 = VF02,20. Ho reordena aleatòriament amb m1, ho xifra amb U3.pub, i genera el missatge M2. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U3 :

M2 [m2,m1|U3.pub]

3. U3 escull Id3.pub1 (59), i genera m3 = VF03,59. Ho reordena aleatòriament amb m1 i m2, ho xifra amb U4.pub, i genera el missatge M3. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U4 :

M3 [m2,m3,m1|U4.pub]

4. U4 escull Id4.pub1 (18), i genera m4 = VF04,18. Ho reordena aleatòriament amb m1, m2 i m3, ho xifra amb U1.pub, i genera el missatge M4. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U1 :

M4 [m2,m4,m1,m3|U1.pub]

5. U1 verifica que m1 segueixi al missatge, escull Id1.pub2 (39), genera a1 = VA01,39, i ho substitueix per m1 dins del missatge. Ho reordena aleatòriament amb m2, m3 i m4, ho xifra amb U2.pub, i genera el missatge A1. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U2 :

A1 [m4,a1,m3,m2|U2.pub]

6. U2 verifica que m2 segueixi al missatge, escull Id2.pub2 (33), genera a2 = VA02,33, i ho substitueix per m2 dins del missatge. Ho reordena aleatòriament amb a1, m3 i m4, ho xifra amb U3.pub, i genera el missatge A2. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U3 :

A2 [m3,a1,m4,a2|U3.pub]

7. U3 verifica que m3 segueixi al missatge, escull Id3.pub2 (09), genera a3 = VA03,09, i ho substitueix per m3 dins del missatge. Ho reordena aleatòriament amb a1, a2 i m4, ho xifra amb U4.pub, i genera el missatge A3. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U4 :

A3 [a2,m4,a3,a1|U4.pub]

8. U4 verifica que m4 segueixi al missatge, escull Id4.pub2 (44), genera a4 = VA04,44, i ho substitueix per m4 dins del missatge. Ho reordena aleatòriament amb a1, a2 i a3, ho xifra amb CA.pub, i genera el missatge A4. Ho firma i li envia a CA.

A4 [a1,a3,a4,a2|U1.pub]

9. CA rep el missatge, el dexifra, sencer, i a continuació dexifra cadascun dels vots. Publica la següent llista :

Id.pri2 Id.pub2 vot aut.
5 39 A
50 33 A
39 9 C
27 44 B

És necessari donar dues voltes completes per assegurar que tots els usuaris poden barrejar tots els vots xifrats, impedint així que el següent usuari de la cadena pugui identificar quin és el seu vot (encara que estigui xifrat).

Anuncis
  1. 03/11/2014 a les 10:51 am

    6. L’últim usuari (UN), realitza la mateixa acció, i envia el missatge (ja amb tots els vots falsos), al primer usuari (U1).

    Hmm, ¿”hecho” en catalan se escribe igual que “falso” en español? Mira, eso va a explicar muchos problemas de entendimiento mutuo.

    En serio, lo de que voten en secuencia parece bastante problematico. Tu sistema es mas bien una alternativa al mezclado/aleatoriedad durante el recuento, no al problema completo de la votacion. Ahora, para la fase de recuento, podria funcionar.

    • 03/11/2014 a les 3:29 pm

      No, “falsos” en catalán es “falsos” igual que en castellano.
      Lo que se refiere, es que el sistema funciona en 2 fases (o rondas). En la primera, los votos que se generan son falsos, ya que aún no se tiene una lista autenticada y anónima, donde cada usuario puede verificar su posición valida, sin que los demás puedan saber cual es esta. En la segunda fase (o ronda), como la lista ya ha sido mezclada por todos los usuarios, estos pueden intercanviar el voto falso por el voto autentico sin compromiso de que otro usuario conozca de quien es este voto.

      Lo de realizar la votación de forma secuencial es solamente la versión simplificada del sistema. Está claro que para llevar esto a la práctica no basta en depender de que todos los votantes colaboren de forma ordenada, así que se deberían hacer algo como generar múltiples respuestas dedicadas a todos los usuarios que falten por votar, y dar por valida la del siguiente que lo requiera.

      El sistema se centra básicamente en la parte de generar la aleatoriedad suficiente para garantizar el anonimato, puesto que este es el principal problema del sistema. Generar una identidad valida de los usuarios (mediante pares de clave publica/privada) es un problema que nunca va a tener una solución 100% segura. Lo mejor para estos casos es quizás el procedimiento de verificación presencial que usa la policía con los DNIs.

  1. No trackbacks yet.

Deixa un comentari

Fill in your details below or click an icon to log in:

WordPress.com Logo

Esteu comentant fent servir el compte WordPress.com. Log Out / Canvia )

Twitter picture

Esteu comentant fent servir el compte Twitter. Log Out / Canvia )

Facebook photo

Esteu comentant fent servir el compte Facebook. Log Out / Canvia )

Google+ photo

Esteu comentant fent servir el compte Google+. Log Out / Canvia )

Connecting to %s

Enfilant el camí

Visualitzant el present per construir el futur

El Noguer

Visualitzant el present per construir el futur

Visualitzant el present per construir el futur

%d bloggers like this: