Resumen Técnico: PIVOT – Funciones Pseudorandomum de Umbral Proactivas y Verificables a partir de Acciones de Grupos de Isogenias

1. Declaración del Problema

Las Funciones Pseudorandomum Obliviosas (OPRF, por sus siglas en inglés) permiten que un cliente evalúe una función con clave sin revelar la entrada al servidor. En una OPRF de umbral (threshold OPRF), la clave secreta se distribuye entre $n$ servidores, requiriendo que al menos $t$ servidores cooperen para la evaluación. Mientras que los esquemas de umbral estándar protegen contra la corrupción estática (donde un conjunto fijo de servidores es comprometido), estos fallan ante un adversario móvil. En un modelo de amenaza móvil, un atacante puede comprometer diferentes servidores a lo largo del tiempo, acumulando fragmentos (shares) de diferentes épocas. Si los fragmentos permanecen estáticos, el adversario puede eventualmente recolectar $t$ fragmentos del mismo estado de distribución y reconstruir la clave maestra, incluso si nunca controla $t$ servidores simultáneamente.

Las OPRF basadas en isogenias existentes están diseñadas principalmente para modelos de corrupción estática. Además, los mecanismos de intercambio de secretos proactivos existentes en grupos clásicos no se traducen fácilmente al entorno de las isogenias debido a la necesidad de vincular los compromisos polinómicos (en el campo escalar) con las acciones de grupos de isogenia (en curvas elípticas). Existe una falta de una construcción que ofrezca simultáneamente:

1. Seguridad post-cuántica (basada en isogenias).
2. Verificabilidad (asegurando que los servidores evalúan bajo la clave correcta).
3. Seguridad proactiva (refrescando periódicamente los fragmentos para frustrar a un adversario móvil).
4. Generación de claves sin distribuidor (dealerless) (sin configuración de confianza).
5. Migración de comités (cambiando el conjunto de servidores o el umbral sin re-encriptar los datos de la aplicación).

2. Metodología y Construcción

El artículo introduce PIVOT (Isogeny-based Verifiable Oblivious Threshold PRF Proactiva), un marco construido sobre acciones de grupos de isogenias efectivas (por ejemplo, CSIDH). La estructura algebraica central se basa en la propiedad conmutativa de las acciones de isogenia: $[a]([b]E) = [a+b]E$.

Arquitectura Central

PIVOT mantiene una única clave maestra de larga duración $k$ y una clave pública $pk = [k]E_0$. Sin embargo, la representación de $k$ cambia con el tiempo. El sistema opera en épocas. En la época $e$, los servidores poseen fragmentos $s^{(e)}_i = F_e(i)$ de un polinomio de Shamir $F_e(X)$ donde $F_e(0) = k$. El vector de compromiso de coeficientes públicos $A^{(e)}$ certifica el polinomio $F_e$.

El protocolo consta de cinco procedimientos principales:

1. Generación de Claves Distribuida sin Distribuidor (DKG):

   • Cada servidor actúa como un distribuidor de Compartición de Secretos Verificable (VSS), muestreando un polinomio aleatorio y distribuyendo fragmentos.
   • Las contribuciones calificadas se agregan para formar el polinomio maestro inicial $F_0(X) = \sum f_j(X)$.
   • Pruebas de Vínculo (Link Proofs): Una innovación crítica es el uso de pruebas de Conocimiento Cero No Interactivas (NIZK) para vincular el término constante del polinomio comprometido (el fragmento escalar) con el exponente utilizado en la cadena de acción de isogenia secuencial que genera la clave pública $pk$. Esto asegura que la clave pública corresponde al secreto compartido sin reconstruir $k$.

2. Evaluación de Umbral:

   • El cliente ciega su entrada $x$ mapeándola a una curva $X = H_1(ctx \| x)$ y aplicando una acción aleatoria $[r]$, enviando $B = [r]X$.
   • Un cuórum de $t$ servidores aplica sus fragmentos ponderados por Lagrange secuencialmente: $Q_h = [\lambda^I_{i_h} s^{(e)}_{i_h}] Q_{h-1}$.
   • Debido a la propiedad aditiva de la acción, la curva final es $Q_t = [k]B$.
   • El cliente desciega para obtener $Y = [k]X$ y deriva la salida.
   • Verificación: Cada servidor proporciona una prueba NIZK ($\pi_{eval}$) certificando que la acción realizada corresponde al fragmento comprometido en el vector público $A^{(e)}$ de la época actual.

3. Refresco Proactivo de Fragmentos:

   • Para contrarrestar a los adversarios móviles, los servidores refrescan periódicamente los fragmentos sin cambiar $k$.
   • Los "distribuidores de refresco" calificados muestrean polinomios de fragmentos cero $z_j(X)$ donde $z_j(0)=0$.
   • El nuevo polinomio es $F_{e+1}(X) = F_e(X) + \sum z_j(X)$. Dado que los términos constantes suman cero, $F_{e+1}(0) = k$.
   • Los compromisos de los coeficientes se actualizan de forma homomórfica. Los fragmentos antiguos se eliminan de forma segura tras la transición.

4. Verificación, Culpa y Reinicio Robusto:

   • Si un servidor envía una prueba o un fragmento malformado, la parte detectora genera un certificado de culpa (blame certificate) (un registro firmado de la falla).
   • El servidor culpado es eliminado y el protocolo se reinicia con un nuevo cuórum. Esto asegura abortos identificables.

5. Recompartición de Comité:

   • Permite la migración a un nuevo conjunto de servidores o a un nuevo umbral $t'$.
   • Un cuórum antiguo trata sus fragmentos ponderados por Lagrange como términos constantes para nuevos polinomios distribuidos al nuevo comité.
   • Crucialmente, esto transfiere el secreto $k$ sin reconstruirlo, preservando la clave pública y todas las salidas de OPRF generadas previamente.

Desafíos Técnicos Abordados

• Consistencia de Testigos entre Dominios: El artículo formaliza la necesidad de relaciones NP conjuntas (por ejemplo, $R_{link}, R_{eval}$) que vinculen un escalar comprometido en el campo con el mismo escalar utilizado en la acción de isogenia. Probarlos por separado es insuficiente; el testigo debe ser idéntico a través de los dominios.
• Consistencia de Época: El protocolo garantiza que las cadenas de evaluación utilicen fragmentos de un único certificado de época para evitar la mezcla de fragmentos de diferentes polinomios.

3. Contribuciones Clave

1. Funcionalidad Formal: Los autores definen una funcionalidad ideal $\mathcal{F}_{pTVOPRF}$ para una VOPRF de umbral proactiva de larga duración, modelando explícitamente adversarios móviles que pueden cambiar el conjunto de servidores comprometidos entre épocas.
2. Construcción sin Distribuidor: Una construcción que combina acciones de grupos de isogenias efectivas con la compartición de secretos de Shamir y compromisos aditivamente homomórficos, donde la clave maestra nunca es reconstruida por ninguna sola parte.
3. Mantenimiento Proactivo: Un mecanismo para renovar los fragmentos de los servidores contra adversarios móviles mientras se preserva la clave maestra, la clave pública y todas las salidas históricas de OPRF. Esto incluye un protocolo de transición de época coordinado.
4. Relaciones NP Conjuntas: La identificación y formalización de relaciones NIZK específicas requeridas para vincular el dominio de la compartición de secretos (coeficientes polinómicos) con el dominio de la acción de isogenia (transformaciones de curvas).
5. Recompartición de Comité: Un protocolo para migrar el secreto a un nuevo comité o cambiar el umbral sin invalidar las bases de datos ya encriptadas indexadas por las salidas de OPRF.
6. Análisis de Seguridad: Una prueba de seguridad basada en simulación en el modelo de oráculo aleatorio bajo los supuestos de vectorización y una acción de grupo oculta adicional (one-more hidden-group-action), probando la privacidad de la entrada y el secreto de la clave contra adversarios semi-honestos móviles.

4. Resultados y Rendimiento

• Corrección: El artículo demuestra que el protocolo mantiene el invariante de que la clave maestra $k$ y la clave pública $pk$ permanecen constantes a través de las operaciones de DKG, evaluación, refresco y recompartición.
• Seguridad: La construcción se demuestra segura contra un adversario semi-honesto móvil que compromete menos de $t$ servidores en cualquier época individual. La seguridad se basa en el borrado seguro de los fragmentos antiguos y la privacidad de información teórica de la compartición de Shamir.
• Compromisos de Eficiencia:
  • Tamaño del Registro (Transcript): A diferencia de los enfoques de servidores virtuales basados en MPC que ofrecen registros de cliente de tamaño constante, PIVOT tiene un registro de cliente de $O(t)$ porque expone la cadena secuencial de $t$ evaluaciones parciales y pruebas.
  • Latencia: La evaluación requiere $t$ acciones de grupo secuenciales y pruebas, creando un cuello de botella de latencia lineal respecto al umbral.
  • Mantenimiento: El refresco proactivo y la recompartición de comités implican una comunicación de $O(n^2)$ (debido a la distribución de fragmentos punto a punto) pero no requieren acciones de isogenia, lo que los hace adecuados para amortizar durante largos periodos.
  • Aplicaciones: El artículo destaca que, si bien el costo en línea es mayor, la capacidad de refrescar fragmentos y migrar comités sin re-encriptar grandes bases de datos (por ejemplo, en servicios de búsqueda privada) proporciona una eficiencia operativa significativa para servicios de larga duración.

5. Significación y Reclamaciones

El artículo afirma presentar la primera VOPRF de umbral desde acciones de grupos de isogenias que proporciona seguridad proactiva contra un adversario móvil.

Los autores posicionan a PIVOT no como una optimización de rendimiento sobre las OPRF existentes de un solo servidor o basadas en MPC, sino como un marco completo de funcionalidades. La significación reside en la elección arquitectónica de exponer explícitamente la estructura de umbral en lugar de ocultarla tras un servidor virtual. Esta explicitud permite:

• Aplicación directa de refresco proactivo (añadiendo polinomios de fragmentos cero).
• Responsabilidad individual (atribución de culpa).
• Migración fluida de comités sin reconstrucción de la clave.

El artículo concluye que para los servicios que requieren longevidad operativa durante años ante un compromiso gradual, el costo de un registro de $O(t)$ es un compromiso necesario para la capacidad de renovar periódicamente el estado de seguridad del sistema sin interrumpir el servicio criptográfico subyacente o re-encriptar los datos dependientes.