Función aleatoria verificable

En criptografía , una función aleatoria verificable ( VRF ) es una función pseudoaleatoria de clave pública que proporciona pruebas de que sus resultados se calcularon correctamente. El propietario de la clave secreta puede calcular el valor de la función, así como una prueba asociada, para cualquier valor de entrada. Cualquier otra persona, utilizando la prueba y la clave pública asociada (o clave de verificación ^{[ 1 ]} ), puede comprobar que este valor se calculó correctamente; sin embargo, esta información no puede utilizarse para encontrar la clave secreta. ^{[ 2 ]}

Una función aleatoria verificable puede considerarse como un análogo de clave pública de una función hash criptográfica con clave ^{[ 2 ]} y como un compromiso criptográfico con un número exponencialmente grande de bits aparentemente aleatorios. ^{[ 3 ]} El concepto de función aleatoria verificable está estrechamente relacionado con el de función impredecible verificable (VUF), cuyos resultados son difíciles de predecir, pero no necesariamente parecen aleatorios. ^{[ 3 ] [ 4 ]}

El concepto de VRF fue introducido por Micali , Rabin y Vadhan en 1999. ^{[ 4 ] [ 5 ]} Desde entonces, las funciones aleatorias verificables han encontrado un uso generalizado en criptomonedas, así como en propuestas para el diseño de protocolos y la ciberseguridad.

En 1999, Micali, Rabin y Vadhan introdujeron el concepto de VRF y propusieron el primero de ellos. ^{[ 4 ]} La construcción original era bastante ineficiente: primero produce una función impredecible verificable , luego usa un bit de núcleo duro para transformarla en un VRF; además, las entradas deben mapearse a números primos de una manera complicada: es decir, usando un generador de secuencias de primos que genera primos con una probabilidad abrumadora usando una prueba de primalidad probabilística . ^{[ 3 ] [ 4 ]} La función impredecible verificable así propuesta, que es demostrablemente segura si una variante del problema RSA es difícil, se define de la siguiente manera: La clave pública PK es${\displaystyle (m,r,Q,monedas)}$, donde m es el producto de dos primos aleatorios, r es un número seleccionado aleatoriamente de${\displaystyle \mathbb {Z} _ {m}^{*}}$, coins es un conjunto de bits seleccionado aleatoriamente, y Q una función seleccionada aleatoriamente de entre todos los polinomios de grado${\displaystyle 2k^{2}-1}$sobre el campo${\displaystyle GF(2^{k})}$La clave secreta es${\displaystyle (PK,\phi (m))}$Dado un valor de entrada x y una clave secreta SK , el VUF utiliza el generador de secuencias primas para seleccionar un número primo correspondiente.${\displaystyle p_{x}}$(el generador requiere entradas auxiliares Q y monedas ), y luego calcula y produce${\displaystyle r^{1/p_{x}}{\pmod {m}}}$, lo cual se hace fácilmente conociendo${\displaystyle \phi (m)}$. ^{[ 4 ]}

En 2005, Dodis y Yampolskiy propusieron una función aleatoria verificable, eficiente y práctica. ^{[ 3 ] [ 6 ]} Cuando la entrada${\displaystyle x}$Si se trata de un dominio pequeño (los autores luego lo extienden a un dominio más grande), la función se puede definir de la siguiente manera:

${\displaystyle F_{SK}(x)=e(g,g)^{1/(x+SK)}\quad {\mbox{y}}\quad p_{SK}(x)=g^{1/(x+SK)},}$

donde e (·,·) es una aplicación bilineal . Para verificar si${\displaystyle F_{SK}(x)}$Se calculó correctamente o no, se puede comprobar si${\displaystyle e(g^{x}PK,p_{SK}(x))=e(g,g)}$y${\displaystyle e(g,p_{SK}(x))=F_{SK}(x)}$. ^{[ 3 ] [ 6 ]} Para extender esto a un dominio más grande, los autores utilizan una construcción de árbol y una función hash universal . ^{[ 3 ]} Esto es seguro si es difícil romper la "suposición de inversión q-Diffie-Hellman", que establece que ningún algoritmo dado${\displaystyle (g,g^{x},\dots ,g^{x^{q}})}$puede calcular${\displaystyle g^{1/x}}$y la "suposición de inversión bilineal q-decisional de Diffie-Hellman", que establece que es imposible que un algoritmo eficiente se dé${\displaystyle (g,g^{x},\ldots ,g^{(x^{q})},R)}$como entrada para distinguir${\displaystyle R=e(g,g)^{1/x}}$del azar, en el grupo${\displaystyle \mathbb {G} }$. ^{[ 3 ] [ 6 ]}

En 2015, Hofheinz y Jager construyeron un VRF que es demostrablemente seguro dado cualquier miembro de la "familia de supuestos (n − 1)-lineales", que incluye el supuesto lineal de decisión . ^{[ 7 ]} Este es el primer VRF de este tipo construido que no depende de un "supuesto de complejidad de tipo Q". ^{[ 7 ]}

En 2019, Bitansky demostró que existen VRF si también existen pruebas no interactivas indistinguibles por testigo (es decir, versiones más débiles de pruebas de conocimiento cero no interactivas para problemas NP que solo ocultan el testigo que usa el probador ^{[ 1 ] [ 8 ]} ), compromisos criptográficos no interactivos y funciones pseudoaleatorias restringidas de clave única (es decir, funciones pseudoaleatorias que solo permiten al usuario evaluar la función con un subconjunto restringido preestablecido de posibles entradas ^{[ 9 ]} ). ^{[ 1 ]}

Cuando una función pseudoaleatoria ciega se basa en criptografía asimétrica , la posesión de la clave pública puede permitir al cliente verificar el resultado de la función, comprobando una firma digital o una prueba de conocimiento cero .

En 2020, Esgin et al. propusieron un VRF seguro post-cuántico basado en criptografía basada en retículos . ^{[ 10 ]}

Los VRF proporcionan pre-compromisos deterministas para entradas de baja entropía que deben ser resistentes a ataques de pre-imagen de fuerza bruta . ^{[ 11 ]} Los VRF se pueden utilizar para la defensa contra ataques de enumeración fuera de línea (como ataques de diccionario ) en datos almacenados en estructuras de datos basadas en hash. ^{[ 2 ]}