¿Es difícil el problema de un registro más discreto en el modelo de grupo genérico?

Question

En el modelo de grupo genérico (GGM), un grupo cíclico concreto de orden (conocido) $n$se reemplaza con una versión idealizada: se elige una codificación aleatoria para los elementos del grupo, y el adversario solo obtiene acceso a la forma codificada de cualquier elemento del grupo de entrada (como el generador / clave pública / ...), y un oráculo para aplicar la operación de grupo en ellos. La codificación es única, por lo que se puede probar la igualdad de los elementos del grupo. Puede verse como el análogo del modelo de Oracle aleatorio para grupos en lugar de hashes.

Es bien sabido que el problema del logaritmo discreto es difícil en el GGM: Shoup demostró que cualquier algoritmo genérico necesita$\Omega(\sqrt{p})$ operaciones de grupo, donde $p$ es el factor primo más grande de $n$.

Mi pregunta es si el problema de un logaritmo discreto más (OMDL) también es difícil en el GGM. Para romper OMDL, se le da a un adversario$k+1$ elementos de grupo aleatorio, puede hacer $k$ consultas a un oráculo DL, y luego debe tener éxito en encontrar el logaritmo discreto de todos $k+1$ entradas.

Answer 1

Sí, esto se demostró en un trabajo reciente de Coretti et al [CDG]. Hablando libremente, el límite inferior establece que un adversario que hace como mucho$T$ consultas al oráculo GGM tienen éxito con probabilidad como máximo $T^2/N$, dónde $N$es el tamaño del grupo. De hecho, consideran un modelo más sólido en el que se permite al adversario un cálculo previo arbitrario en el GGM. Ver §5 para declaraciones más precisas y Tabla 2 para un resumen de sus resultados.

[CDG]: Coretti, Dodis y Guo, Límites no uniformes en los modelos de permutación aleatoria, cifrado ideal y grupo genérico , Crypto'18