💻 computer science

From Bits to Mixed-Radix Keys: Horner Decomposition, Uniform Sampling, and the Information-Theoretic QKD Interface of the MR-OTP

Este artículo establece un marco práctico y teóricamente seguro desde el punto de vista de la información para convertir la entropía binaria bruta de fuentes de Distribución de Claves Cuánticas en claves de base mixta uniformes para el One-Time Pad de Base Mixta mediante la utilización del método de Horner para el mapeo, el muestreo de rechazo para eliminar el sesgo, y pruebas rigurosas de seguridad y eficiencia.

Autores originales: Fabio F. G. Buono

Publicado 2026-06-19

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Fabio F. G. Buono

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

La visión general: Un nuevo tipo de cerradura "inquebrantable"

Imagina que quieres enviar un mensaje secreto. El estándar de oro para la secrecía es el Libro de un Solo Uso (One-Time Pad o OTP). Piensa en esto como una cerradura donde la llave es una cadena de números aleatorios exactamente tan larga como tu mensaje. Si la llave es verdaderamente aleatoria y nunca se reutiliza, el mensaje es matemáticamente imposible de descifrar, sin importar qué tan potente sea la computadora que intente romperlo.

Sin embargo, los OTP tradicionales tienen un defecto: solo hablan "Binario" (0s y 1s). Si quieres enviar una letra como la "A" (que es naturalmente un símbolo, no un 0 o 1), primero tienes que traducirla a binario. Esta traducción desperdicia espacio y es ineficiente.

Este artículo presenta el Libro de un Solo Uso de Base Mixta (Mixed-Radix One-Time Pad o MR-OTP). Piensa en esto como una cerradura que habla el lenguaje nativo de tus datos.

Si estás enviando ADN (4 letras), la cerradura usa un dado de 4 caras.
Si estás enviando texto en inglés (26 letras), usa un dado de 26 caras.
Si estás enviando números (10 dígitos), usa un dado de 10 caras.

Este artículo resuelve el problema práctico de cómo construir esta cerradura utilizando una máquina de Distribución de Claves Cuánticas (QKD), que solo produce un flujo de 0s y 1s.

El problema central: El "corte tosco" de la aleatoriedad

La Analogía:
Imagina que tienes una máquina que escupe lanzamientos de dados de 6 caras (0–5) perfectos y justos. Pero tu cerradura requiere un dado de 7 caras (0–6).

El error ingenuo: Podrías pensar: "Tomaré un lanzamiento de 6 caras, le sumaré 1, y si obtengo un 7, simplemente lo haré dar la vuelta hacia el 0".
El problema: Esto crea un "sesgo". Algunos números (como el 0 y el 1) aparecerían con más frecuencia que otros (como el 6). En el mundo de la secrecía perfecta, incluso un pequeño sesgo es como dejar una rendija abierta en la puerta. Arruina la garantía de ser "inquebrantable".

La Solución del Artículo:
Los autores proponen una regla estricta de "Muestreo de Rechazo" (Rejection Sampling).

La máquina genera un número.
Si el número entra dentro de tu rango de 7 caras, lo conservas.
Si es demasiado grande (por ejemplo, sacaste un 7 u 8), lo descartas e intentas de nuevo.
Repites esto hasta que obtengas un número válido.

Esto asegura que cada número de 0 a 6 tenga exactamente la misma probabilidad de ser elegido. El artículo demuestra que este método es lo suficientemente eficiente como para ser práctico, desperdiciando muy pocos bits del flujo cuántico.

El ingrediente secreto: El "Método de Horner"

¿Cómo se convierte una larga cadena de bits binarios (provenientes de la máquina cuántica) en un conjunto específico de lanzamientos de dados de base mixta (por ejemplo, uno de 7 caras, uno de 13 caras, uno de 5 caras)?

La Analogía:
Piensa en una muñeca rusa anidada o en un conjunto de instrucciones para construir una torre.

Hacia adelante (Construcción): Comienzas con el primer dígito, lo multiplicas por el tamaño del siguiente dado, sumas el siguiente dígito, multiplicas por el siguiente tamaño de dado, y así sucesivamente. Esto se llama Método de Horner. Es un truco matemático ingenioso para empaquetar diferentes tamaños de números en un gran entero.
Hacia atrás (Desempaquetado): Para recuperar las llaves, haces lo opuesto. Tomas el número grande, lo divides por el tamaño del último dado para obtener el residuo (la última llave), luego divides el resultado por el tamaño del siguiente dado, y así sucesivamente.

El artículo demuestra que este proceso de "empaquetado y desempaquetado" es una correspondencia perfecta, uno a uno. Es el puente algebraico que permite convertir un flujo de 0s y 1s en un conjunto perfecto y sin sesgo de llaves de base mixta.

La garantía de seguridad: "El Escudo de Dos Capas"

El artículo aborda una pregunta aterradora: ¿Qué pasa si un hacker descubre la "forma" de los dados (la secuencia de bases) que estamos usando?

Los autores demuestran un "Escudo de Dos Capas":

Capa 1: La forma está oculta (Computacionalmente difícil).
Si el hacker no sabe que estamos usando un dado de 7 caras o uno de 13 caras, tiene que adivinar. El artículo muestra que adivinar la secuencia de tamaños de dados es increíblemente difícil, especialmente si el hacker solo ve el mensaje cifrado (texto cifrado) sin el texto original. De hecho, si solo ven el texto cifrado, es matemáticamente imposible conocer los tamaños de los dados.
Capa 2: La llave es inquebrantable (Teórica de la información).
Incluso si el hacker sí descubre los tamaños de los dados (la "forma"), aún no puede leer el mensaje. ¿Por qué? Porque la llave real (los números aleatorios lanzados en esos dados) se genera de nuevo para cada mensaje.

La Analogía: Imagina que el hacker descubre que estás usando un dado de 26 caras. ¡Eso es genial para él! Pero aun así no sabe qué número (A–Z) lanzaste para este mensaje específico. Dado que el lanzamiento fue verdaderamente aleatorio y nunca se reutilizó, saber el tamaño del dado no le dice nada sobre la letra.

La gran conclusión: La seguridad del mensaje no depende de que el hacker sea demasiado lento para adivinar los tamaños de los dados. Incluso si adivinan los tamaños instantáneamente, el mensaje permanece perfectamente secreto porque la llave es aleatoria.

Eficiencia: Ahorrando espacio

El artículo también señala un efecto secundario positivo.

Forma Antigua (OTP Binario): Para enviar una letra "A" (1 de 26), debes usar 5 bits (ya que $2^5 = 32$ ). Desperdicias 6 bits de espacio porque 32 es mayor que 26.
Nueva Forma (MR-OTP): Utilizas exactamente el espacio necesario para 26 opciones.
El Resultado: A lo largo de millones de mensajes, esto ahorra una cantidad masiva de "material de clave" (los bits aleatorios necesarios de la máquina cuántica). Es como empacar una maleta: la forma antigua te obligaba a usar una caja gigante para una camisa pequeña; la nueva forma usa una caja que se ajusta perfectamente a la camisa.

Resumen de afirmaciones

Cómo convertir: Puedes convertir bits aleatorios cuánticos en llaves de base mixta usando un método de "rechazar y reintentar" combinado con un truco matemático llamado descomposición de Horner.
Sin Sesgo: Este método crea una llave perfectamente uniforme, lo cual es un requisito para la garantía de "inquebrantable".
Seguridad de Extremo a Extremo: Todo el proceso (Máquina Cuántica $\to$ Conversión $\to$ Cifrado) es matemáticamente demostrado como inquebrantable.
A prueba del futuro: Incluso si una supercomputadora en el futuro logra adivinar los "tamaños de los dados" (la secuencia de bases) instantáneamente, los mensajes permanecen seguros porque las llaves son frescas y aleatorias.
Eficiencia: Ahorra espacio en comparación con los métodos binarios tradicionales, especialmente para lenguajes naturales y datos biológicos.

El artículo no afirma que esto sea un producto comercial listo para la venta hoy, ni afirma que resuelva todos los problemas criptográficos. Demuestra estrictamente los fundamentos matemáticos y los algoritmos necesarios para que este tipo específico de "secrecía perfecta" funcione con hardware cuántico del mundo real.

Resumen Técnico: De Bits a Claves de Radix Mixto

Planteamiento del Problema
El Unario de un Solo Uso de Radix Mixto (MR-OTP, por sus siglas en inglés), introducido en un trabajo precedente [1], generaliza el clásico Unario de un Solo Uso binario a espacios de dígitos con bases no uniformes. Permite la codificación nativa de alfabetos de datos heterogéneos (p. ej., secuencias de ADN, texto latino) sin conversión binaria intermedia, preservando al mismo tiempo la secrecía perfecta de Shannon. Sin embargo, un despliegue práctico requiere un mecanismo para convertir la salida de entropía binaria bruta de una fuente de Distribución de Claves Cuánticas (QKD) en una tupla de claves uniformemente distribuida sobre el espacio de claves de radix mixto.

Un enfoque ingenuo —leer $k = \lceil \log_2 P \rceil$ bits (donde $P$ es el producto de las bases) y reducir el entero resultante módulo $P$ — introduce una distorsión estadística conocida como "sesgo de módulo" (modulo bias). En el entorno de la teoría de la información, cualquier falta de uniformidad en la distribución de la clave viola la hipótesis del teorema de la secrecía perfecta, lo que hace que el sistema sea inseguro independientemente de la magnitud del sesgo. El artículo aborda el desafío algorítmico de convertir un flujo binario uniforme en una tupla de claves de radix mixto uniforme sin introducir este sesgo, manteniendo al mismo tiempo la seguridad de la información teórica de extremo a extremo.

Metodología
El artículo establece una equivalencia estructural entre los pesos posicionales de radix mixto y la forma anidada de la evaluación polinómica.

Correspondencia Algebraica: Los autores identifican el método de Horner y su inverso como la dualidad algebraica canónica para esta conversión. El mapa hacia adelante (evaluación de Horner) compone una tupla de dígitos en un único entero, mientras que el mapa inverso (descomposición de Horner inversa) recupera los dígitos de un entero mediante reducción modular sucesiva. Esto establece una biyección entre el espacio de claves $\mathcal{K}$ y el intervalo de enteros $\{0, \dots, P-1\}$ .
Muestreo de Rechazo: Para eliminar el sesgo de módulo, el artículo propone un algoritmo de muestreo de rechazo (Algoritmo 1). El algoritmo extrae $k$ bits para formar un entero $V$ . Si $V \ge P$ , la muestra se descarta y el proceso se repite. Si $V < P$ , se aplica la descomposición de Horner inversa para generar la tupla de claves.
Marco de Análisis de Seguridad: El artículo analiza todo el flujo de trabajo (QKD $\to$ Extracción de Clave $\to$ Cifrado MR-OTP) a través de sesiones individuales y múltiples. Emplea un esquema de partición de rotación de claves (key-rolling) donde bloques disjuntos del flujo QKD se utilizan para la clave y la secuencia de bases de cada sesión.
Taxonomía de Adversarios: El análisis de seguridad distingue entre cuatro clases de adversarios: basados en pruebas (testing-based), algebraicos, ilimitados (unbounded) y de solo texto cifrado (ciphertext-only). Separa el "secreto computacional" (la secuencia de bases $B$ ) del "secreto de la teoría de la información" (el pad $K$ ).

Contribuciones Clave y Resultados

Muestreo de Claves Uniformes: El artículo demuestra que la reducción modular ingenua rompe la secrecía perfecta (Proposición 3.1). Demuestra que el muestreo de rechazo combinado con la descomposición de Horner inversa restaura una distribución uniforme sobre el espacio de claves (Teorema 3.4). El costo de bits esperado de este proceso está acotado por $2\lceil \log_2 P \rceil$ , con un número esperado de rondas de rechazo de como máximo 2 (Proposición 3.5).
Seguridad de Extremo a Extremo: La composición de una fuente QKD ideal, el algoritmo de muestreo de rechazo y el MR-OTP logra la secrecía perfecta de Shannon para una sola sesión (Teorema 4.2) y a través de $N$ sesiones bajo un esquema de rotación de claves por partición (Teorema 6.2). Esto se mantiene sin supuestos computacionales.
Eficiencia de Representación: El artículo cuantifica la ganancia de eficiencia del MR-OTP sobre el OTP binario para alfabetos naturales. Al operar en el espacio de símbolos nativo, el MR-OTP elimina el "sobrecosto binario" ( $\lceil \log_2 b \rceil - \log_2 b$ ) inherente a la codificación binaria. Por ejemplo, ofrece una reducción de aproximadamente el $16.9\%$ en el material de clave para dígitos decimales y de aproximadamente el $6.0\%$ para el alfabeto latino (Proposición 5.3).
Problema de Recuperación de la Base (BRP):
- Solo Texto Cifrado: El artículo demuestra que recuperar la secuencia de bases $B$ únicamente a partir del texto cifrado es insoluble desde la teoría de la información (Corolario 8.2). El texto cifrado proporciona cero información sobre $B$ más allá de la restricción $b_i > c_i$ .
- Texto Claro Conocido: En el escenario de texto claro conocido, el artículo establece un límite inferior incondicional sobre la complejidad de consulta para adversarios basados en pruebas, mostrando que identificar $B$ requiere al menos $|F_T| - 1$ consultas, donde $|F_T|$ permanece exponencial en la longitud del mensaje $L$ para valores pequeños de $T$ (Teorema 8.10).
- Invarianza de la Seguridad: Un resultado central (Teorema 8.15) demuestra que incluso si un adversario (limitado o ilimitado) recupera con éxito la secuencia de bases $B$ a partir de datos de texto claro conocido, obtiene cero información sobre cualquier mensaje futuro cifrado bajo una clave fresca. La seguridad de la teoría de la información del pad se preserva independientemente del estatus computacional del problema de recuperación de la base.
Extracción por Lotes: El artículo introduce un algoritmo de extracción por lotes (Sección 9) que extrae un único entero grande para generar $N$ dígitos de clave simultáneamente. Esto reduce el sobrecosto del rechazo en comparación con el muestreo secuencial, acercándose al límite teórico de entropía de $\log_2 b$ bits por símbolo cuando $N \to \infty$ (Teorema 9.2).
Fuentes No Ideales: El artículo extiende las garantías de seguridad a fuentes QKD no ideales que están $\epsilon$ -cercanas a la uniformidad en distancia de variación total. Muestra que la degradación de la seguridad de extremo a extremo está acotada por $2N\epsilon$ para $N$ sesiones (Teorema 10.3).

Significancia y Reivindicaciones
El artículo afirma proporcionar la base algorítmica completa para el despliegue del MR-OTP con fuentes QKD manteniendo una estricta seguridad de la teoría de la información. Su principal significancia radica en:

Resolución del Problema del Sesgo: Proporciona un método demostrablemente correcto (muestreo de rechazo + inversión de Horner) para convertir la entropía binaria en claves de radix mixto sin violar el requisito de uniformidad de la secrecía perfecta.
Seguridad Temporal Incondicional: Establece que la seguridad de los mensajes futuros es independiente de la dificultad computacional de recuperar la secuencia de bases. Incluso si se recupera la secuencia de bases, el sistema mantiene la secrecía perfecta para cifrados frescos. Esto crea una estructura de seguridad de "dos capas" donde la capa computacional (ocultar la base) y la capa de la teoría de la información (ocultar el mensaje) son independientes.
Eficiencia: Demuestra que el MR-OTP no solo es teóricamente sólido, sino también más eficiente en la práctica que el OTP binario para alfabetos que no son potencias de dos, reduciendo el consumo de clave sin sacrificar la seguridad.
Clasificación de Adversarios: Clasifica rigurosamente las capacidades de los adversarios, demostrando que la garantía de la teoría de la información se mantiene incondicionalmente para todas las clases de adversarios, mientras que los resultados de dureza computacional se aplican solo a subconjuntos específicos (pruebas vs. algebraicos) en el escenario de texto claro conocido.

El artículo concluye identificando problemas abiertos, específicamente respecto a la variante de rotación dinámica de claves (donde la secuencia de bases depende de los textos cifrados previos) y la dureza computacional de caso promedio del Problema de Recuperación de la Base para adversarios algebraicos.