Decidir DDH basado en información parcial

La suposición decisiva de Diffie-Hellman , o DDH en resumen, es un problema famoso en criptografía. La suposición DDH se mantiene en un grupo cíclico de orden (primo) q , si es para un generador g ∈ G , y para aleatoriamente a , b , c ∈ \ mathbb {Z} _q $$, los siguientes pares son indistinguibles (para algoritmos probabilísticos de poli-tiempo):$(G,*)$$q$$g \in G$$a,b,c \in$

• Tipo 1: $(g,g^a,g^b,g^{ab})$
• Tipo 2: $(g,g^a,g^b,g^{c})$

Ahora, suponga que es un grupo en el que DDH es difícil, y considere la siguiente pregunta informal :$G$

¿Conocemos un algoritmo probabilístico de poli-tiempo (PPT), que obtiene un par Diffie-Hellman, junto con alguna información parcial sobre (por ejemplo, a es impar), y puede generar correctamente si el par de entrada es "Tipo 1" o "Tipo 2" (con probabilidad no despreciable)?$a$$a$

Por información parcial, me refiero a una cadena , de modo que dado z y un par Diffie-Hellman, ningún algoritmo PPT puede calcular a , con una probabilidad no despreciable.$z$$z$$a$

Es posible formalizar la pregunta anterior. Sin embargo, dado que la cantidad de notación requerida es tediosa, trato de usar una analogía.

Una suposición criptográfica no estándar famosa se llama Conocimiento del exponente (KEA).

Para cualquier adversario A que toma la entrada , g , g un y vuelve ( C , C a ) , existe un "extractor" B , que da las mismas entradas como A retornos c tal que g c = C .$q$$g$$g^a$$(C,C^a)$$A$$c$$g^c = C$

Intuitivamente, se afirma que, puesto que el adversario no puede resolver logaritmo discreto para obtener , la única forma de salida un par ( C , C a ) es "saber" el exponente c donde g c = C .$a$$(C,C^a)$$c$$g^c = C$

Ahora, yo estoy haciendo una pregunta similar, basado en la DCC (en lugar de registro discreto): para distinguir "tipo 1" y "2" Tipo pares de Diffie-Hellman, debemos "saber" ya sea o b ?$a$$b$

Un poco más formal (pero aún no completamente formal):

Sea un grupo de primer orden q , y sea f ( ⋅ ) una función arbitraria cuya longitud de salida es polinómica en la longitud de su entrada. Escoja una , b , y c azar de Z q , y dejar que z = f ( un ) . Lanza una moneda y deja que X = a b si el resultado es cara. De lo contrario, sea X = c .$(G,*)$$q$$f(\cdot)$$a$$b$$c$$\mathbb{Z}_q$$z=f(a)$$X = ab$$X=c$

Para cualquier adversario PPT A que tome datos y decida correctamente entre Tipo 1 y Tipo 2 con probabilidad no despreciable, existe un "extractor" PPT B , que toma la misma entrada que a , las salidas ya sea una o b (con probabilidad no despreciable).$(q,g,g^a,g^b,g^X,z)$$a$$b$

Dada la última formulación de su pregunta, esto parece ser imposible. Consideremos el caso en que tenga (familias) de grupos cíclicos y H , en donde G ≠ H y tenemos un mapa bilineal e : G × H → T . Bajo el supuesto de XDH podemos suponer que DDH es difícil en G y del logaritmo discreto es difícil en H .$\mathbb{G}$$\mathbb{H}$$\mathbb{G} \ne \mathbb{H}$$e: \mathbb{G} \times \mathbb{H} \to \mathbb{T}$$\mathbb{G}$$\mathbb{H}$

Deje ser un generador de G y h sea un generador de H . Luego defina f : Z | G | → H como f ( a ) = h a .$g$$\mathbb{G}$$h$$\mathbb{H}$$f : \mathbb{Z}_{|\mathbb{G}|} \to \mathbb{H}$$f(a) = h^a$

Ahora dado , podemos determinar fácilmente si X = a b marcando e ( g b , z ) ? = e ( g X , h ) . (También puede verificar de manera similar la corrección de z si lo desea). Sin embargo, parece poco probable que un extractor pueda extraer$(g, g^a, g^b, g^X, z=f(a)=h^a)$$X = ab$$e(g^b, z) \overset{?}= e(g^X,h)$$z$ o b de tal tupla. Extraer b es obviamente equivalente a un registro discreto; si hay un mapa de distorsión de H a G (no puede haber uno en la otra dirección), extraer un equivalente es un registro discreto (en H ).$a$$b$$b$$\mathbb{H}$$\mathbb{G}$$a$$\mathbb{H}$