Algoritmo de Corrección de Errores (Cascade)

Hola, el día de hoy quiero compartirles un algoritmo que sirve para corregir errores en un canal de transmisión. Este algoritmo es muy usado cuando hablamos de criptografía cuántica, específicamente en el intercambio de claves entre dos interlocutores, por ejemplo entre Alice y Bob.

Cuando Alice quiere hacerle saber a Bob su clave para cifrar, ella se la envía por un canal clásico y la información que le llega a Bob muy posiblemente presente errores, ya sea inducidos por el canal o por un posible espia que este escuchando la comunicación.

Para solucionar este inconveniente, Guilles Brassard y Louis Salvail propusieron en Secret-Key Reconciliation by Public Discussion un algoritmo llamado Cascade.



Sin mas preámbulo, aqui les dejo de forma mas entendible dicho algoritmo:

Cascade

1. Alice y Bob acuerdan el tamaño de bloque inicial, K1, calculado a partir de una tasa de error esperada. Esa tasa de error puede ser estimada intercambiando una pequeña muestra de la clave.
2. Dividimos la clave en bloques de tamaño máximo definido, Ki, en función del número de iteración, que estamos realizando.
3. Para cada uno de los bloques definidos en el paso anterior:

a. Calculamos la paridad del bloque.

b. Intercambiamos las paridades calculadas entre Alice y Bob.

i. Si la paridad es idéntica, saltamos al siguiente bloque (no hemos detectado ningún error).

ii. Si la paridad es diferente, realizamos una búsqueda binaria del error en el bloque actual (ver el algoritmo de búsqueda binaria). Encontrar un error en el paso n-ésimo, implica que en los pasos anteriores hemos dejado errores sin corregir. Puesto que las paridades eran idénticas, el error encontrado nos lleva a deducir que existe otro error en los bloques estudiados con anterioridad (un número par de errores por bloque producen una paridad idéntica a la del bloque sin errores). Por lo tanto, debemos volver a los bloques de los pasos anteriores donde aparezca el bit corregido para realizar una nueva búsqueda. La vuelta atrás se realiza en dos pasos. En primer lugar se regresa a los tamaños de bloque inferiores para corregir aquellos bloques donde se detectó el nuevo error. Y una vez corregidos los errores en bloques de tamaño inferior, se debe avanzar de nuevo a los bloques de mayor tamaño ya estudiados donde puede haberse camuflado un nuevo par de errores. De igual forma, la corrección de un nuevo error por la vuelta atrás implica la reiteración de una nueva vuelta atrás para corregir los errores acumulados (y así sucesivamente, de forma anidada).

4. Una vez que hemos acabado de procesar las paridades de todos los bloques, calculamos el nuevo tamaño de bloque como el doble del tamaño de bloque anterior: Ki+1 = 2Ki.

5. Si el nuevo tamaño de bloque definido es superior al tamaño de la clave, hemos acabado el proceso de corrección de errores. De igual forma, si se han completado al menos cuatro iteraciones del proceso de corrección nuestra clave debe ser idéntica en ambos extremos de la comunicación, y por lo tanto también habríamos acabado.

6. En otro caso, reordenamos la clave de forma aleatoria y similar en Alice y Bob.

7. Realizamos una nueva iteración desde el paso 2.


Algoritmo de Búsqueda Binaria:

1. Si el bloque es de tamaño 1, hemos encontrado el error. Invertimos el bit del bloque en Bob y finalizamos el procedimiento de búsqueda.
2. En otro caso, dividimos el bloque actual en dos nuevos subbloques de igual tamaño.
3. Calculamos la paridad del primer subbloque.
4. Intercambiamos la paridad del primer subbloque entre Alice y Bob.

a. Si la paridad compartida es idéntica, el error está en el segundo subbloque. Saltamos al paso 1 con el segundo subbloque.

b. Si la paridad es diferente, el error está en este primer subbloque. Saltamos al paso 1 con el primer bloque.

Espero les sea de utilidad, de igual forma les he dejado el link del paper.