El modelo de grupo genérico [1] [2] es un modelo criptográfico idealizado, en el que el adversario solo tiene acceso a una codificación elegida al azar de un grupo , en lugar de codificaciones eficientes, como las utilizadas por el campo finito o los grupos de curvas elípticas utilizados. en la práctica.
El modelo incluye un oráculo que ejecuta la operación de grupo . Este oráculo toma dos codificaciones de elementos de grupo como entrada y genera una codificación de un tercer elemento. Si el grupo permitiera una operación de emparejamiento , esta operación se modelaría como un oráculo adicional.
Uno de los usos principales del modelo de grupo genérico es analizar supuestos de dureza computacional . Un análisis en el modelo de grupo genérico puede responder a la pregunta: "¿Cuál es el algoritmo genérico más rápido para romper un supuesto de dureza criptográfica?". Un algoritmo genérico es un algoritmo que solo hace uso de la operación de grupo y no considera la codificación del grupo. Esta pregunta fue respondida para el problema del logaritmo discreto por Victor Shoup utilizando el modelo de grupo genérico. [1] Otros resultados en el modelo de grupo genérico son, por ejemplo. [3] El modelo también se puede extender a otras estructuras algebraicas como anillos . [4]
El modelo de grupo genérico sufre algunos de los mismos problemas que el modelo de oráculo aleatorio . En particular, se ha demostrado [5] utilizando un argumento similar [6] que existen esquemas criptográficos que son demostrablemente seguros en el modelo de grupo genérico pero que son trivialmente inseguros una vez que la codificación de grupo aleatorio se reemplaza con una instanciación computable eficiente de la función de codificación.
Referencias
- ↑ a b Victor Shoup (1997). "Límites inferiores para logaritmos discretos y problemas relacionados" (PDF) . Apuntes de conferencias en Ciencias de la Computación . Avances en criptología - Eurocrypt '97. 1233 . Springer-Verlag. págs. 256–266 . Consultado el 9 de abril de 2010 .
- ^ Ueli Maurer (2005). "Modelos abstractos de computación en criptografía" (PDF) . Apuntes de conferencias en Ciencias de la Computación . X Conferencia IMA sobre criptografía y codificación. 2796 . Springer-Verlag. págs. 1-12 . Consultado el 1 de noviembre de 2007 .
- ^ Ueli M. Maurer, Stefan Wolf: límites inferiores en algoritmos genéricos en grupos. EUROCRYPT 1998: 72-84
- ^ Divesh Aggarwal, Ueli Maurer: Romper RSA genéricamente es equivalente a factorizar. EUROCRYPT 2009: 36-53
- ^ Alexander W. Dent: Adaptación de las debilidades del modelo de Oracle aleatorio al modelo de grupo genérico. ASIACRYPT 2002: 100-109
- ^ Ran Canetti, Oded Goldreich y Shai Halevi, La metodología de Oracle aleatoria revisada, STOC 1998, págs. 209-218 (PS y PDF) .