Thursday, February 11, 2010

Álgebra de votaciones para procesos electorales

Últimamente se ha hecho una modita el rechazar elecciones electrónicas por razones las cuales siento que carecen de fundamentos.

Hice una presentación la cual no fue del todo aprovechada ya que donde lo iba a exponer no sirvió el proyector, pero tambien expongo un punto de vista distinto al usual para realizar votaciones electrónicas (con criptografía y no con solo contadores electrónicos y cables), como valor agregado obviamente salvarás millones de árboles.

En el documento no toco temas socio-políticos los cuales son los que causan polémica, sino tres algoritmos necesarios para

poder realizar un proceso electoral electrónico.

Este documento puede ser un poco complicado, así que a manera de resumen explico los tres algoritmos:


1.Zero-Knowledge: Este algoritmo permitirá a una persona A poderle demostrar a B que A conoce un secreto "s" y B quedará totalmente convencido de que "s" existe pero sin que A haya revelado s, solamente a B se le revelara la veracidad de la existencia de "s". (Se utiliza el problema de logaritmo discreto), un poco mas técnico, el algoritmo podrá mostrarle a B que A posee una llave que abre un mensaje sin que el mensaje sea revelado ni la llave.
Un ejemplo que luego ocupo para explicar es: "¿Cómo puedo convencerte de que realmente si tengo la receta de la coca-cola para que me la pagues primero y luego te la de?"

2. Shamir threshold: Este algoritmo permitirá que N personas tengan un "pedazo" de secreto "s" y que si k personas (k menor que s) se juntan puedan reconstruir el secreto "s" de tal manera que los pedazos de secreto nunca podrán construirse a partir k-1 personas.

Por ejemplo, imaginen que una bóveda es de 10 personas, pero por alguna extraña razón quieren que si se juntan cualesquiera 3 personas de esos 10 puedan abrirla. La bóveda tiene un password y este solo se puede construir cuando se juntan 3 personas y no menos. (Este algoritmo utiliza polinomios de Lagrange)


3. Diffie-Hellman

¿Cómo podemos negociar una llave secreta dos personas aunque haya un tercero oyendo TODA nuestra negociación?
Esto utiliza logaritmo discreto.

Y por ultimo utilizando Elgamal se simula un esquema de votación de en el conjunto {-1,1} (si o no) , esto es suficiente ya que si hay mas candidatos es como hacer (a,b) o c es ( (a,b), c) (suma directa) .


Como les digo, aquí no discuto la honradez o la educación de la banda para poder votar, sino que hipotéticamente es posible y es seguro.

Con este esquema los votantes podrían hacer lo siguiente:

1. Checar que su voto realmente fue contado
2. Checar que su voto fue contado por quién ellos eligieron
3. Sufragio total, solo el votante puede verificar el punto 2 (todo esto protegido con criptografía asimétrica y certificados)
4. Los votantes pueden contar los votos y quedar convencidos de que el conteo no fué truqueado

A diferencia de los esquemas habituales (Brasil , Australia, Estados Unidos) , con criptografía se pueden asegurar cosas.

y no solamente incrementar un contador como lo ha sido en esos paises. Con criptografía se puede hacer que realmente el voto sea secreto, efectivo y robusto ante tramposos.


Les dejo la liga: aquí


Saludos Eduardo Ruiz Duarte (beck)

5 comments:

Gunnar Wolf said...

Inicias diciendo:

Últimamente se ha hecho una modita el rechazar elecciones electrónicas por razones las cuales siento que carecen de fundamentos.
(…)
En el documento no toco temas socio-políticos los cuales son los que causan polémica, sino tres algoritmos necesarios para poder realizar un proceso electoral electrónico.
(…)
Con este esquema los votantes podrían hacer lo siguiente:

1. Checar que su voto realmente fue contado
2. Checar que su voto fue contado por quién ellos eligieron
3. Sufragio total, solo el votante puede verificar el punto 2 (todo esto protegido con criptografía asimétrica y certificados)


El problema, mi querido y tan matemático amigo, es que no puedes contemplar el proceso bajo la pureza y belleza algorítmica a secas. Estoy de acuerdo con lo que expones, claro, pero en el momento en que dices que no tocas temas sociopolíticos, lo siento – No estás hablando de votaciones.

El voto, por donde lo abordes, está cargado de política. De trucos de todo tipo, de fraudes de todo tipo. Con este pedacito que citas… Bueno, en una democracia es importante el principio del voto secreto – nadie debe poder ejercer presión sobre tí basado en el sentido de tu voto, y por tanto, debes poder votar sin que nadie lo sepa. Ahora, ¿qué pasaría si alguien ofrece una despensa a todo quien pruebe inequívocamente que votó por determinado partido? ¿O que te condicionen el espacio de venta en el tianguis a un voto? Ahí abres un bote de corruptelas criptográficamente demostrables.

alvarezp said...

Dejando de lado lo que dice Gunnar, y asumiendo que el proceso fuera 100% confiable (tal vez por que el cliente sea software libre), aún falta un detalle que hasta el momento me parece imposible: garantizar el anonimato cumpliendo con los siguientes dos requisitos:

1) No permitir duplicidad de votos.

2) No permitir que el usuario ponga en duda el sistema. Como contraejemplo: "dame tu clave del IFE y nosotros en server garantizamos que no la almacenaremos" no es una solución válida porque yo desconfiaría de que el segundo paso realmente ocurra).

Anonymous said...

Hola a todos, yo soy politólogo y entusuasta del software libre, así que considero que puedo hablar más o menos objetivamente sobre el tema, coincido con Gunnar en que si no le pones la parte política a las elecciones entonces no són elecciones y son sólo matemáticas, ojo, no digo que sea malo, qué bueno que existan métodos más y más seguros para proteger los datos de votaciones, pero además de los puntos que expuso Gunnar hay otro detalle que incumbe más con la parte teorico política:
Según la Constitución todos ciudadanos mexicanos tenemos derecho a votar y ser votados (esto incluye una pequeña variable de la que casi nadie se acuerda pero que no es posible medir) las candidaturas independientes, en una hoja de papel podemos votar lo mismo por cualquiera de los candidatos registrados que por "Batman" o por nosotros mismos, esto lejos de ser un juego es una práctica de participación ciudadana que puede responder a varios factores que van dese la inconformidad hacia los candidatos "oficiales" o hacia los partidos, hasta la de elegir libremente a quienes queramos, en lo que entendí de tu post, en ningún momento tomas en cuenta esto y sin embargo es uno de los pilares de la democracia.
Ya para terminar te recomiendo que si te leas algunas cosas políticas antes de decir que la parte política es la que hace los conflictos, desde mi punto de vista las matemáticas sin aplicación (o sin alguna representación en la vida social) no son más que numeritos acomodados de forma elegante.
Saludos.

Anonymous said...

Me quedé atónito al leer los comentarios de este post, y aunque siempre evito contestar a gente mal informada o con poca voluntad para el pensamiento, esta vez decidí que era necesario. Me refiero en particular al comentario del tal libertadzero que incluye la siguiente frase: "las matemáticas sin aplicación (o sin alguna representación en la vida social) no son más que numeritos acomodados de forma elegante". A él me dirijo: si nunca has trabajado en matemáticas no puedes hacer un comentario de esta gravedad. Si no tienes la capacidad o el interés por hacer matemáticas (i.e. investigación en matemáticas) por lo menos intenta leer a quienes las hacen. Te recomiendo e.g. el sitio web de Laurent Lafforgue, matemático francés (medalla Fields) y quien emprendiera hace algunos años una polémica sobre la educación en Francia, logrando poner sobre la mesa de discusión ciertos puntos cuya relevancia no había sido notada o expuesta con seriedad. En su página puedes encontrar entrevistas muy enteresantes; recuerdo haber leído en alguna de ellas que Lafforgue ponderaba la relación entre educación y cultura, enfatizando por ejemplo, el desempeño de las matemáticas a nivel cultural. Este papel es el que debes entender antes de hacer un comentario bobo acerca del valor de las matemáticas que no tienen -aparentemente- una "aplicación".

Lo que veo acá aparte de la ignorancia en este comentario que acabo de tocar, es un desconocimiento total acerca de lo que es un modelo matemático. Si bien el que presentan acá no es completo y necesitaría bastantes modificaciones, el hecho de que no toque la parte política no tiene nada de malo para la parte matemática. Y me refiero sólo a la parte política, no a la legal, entre la cual van las hipótesis a partir de las cuales se construye el modelo.

luciano said...

de lo que entiendo de las diapositivas es que es necesario firmar el voto. No se... creo que cae por su propio peso...