Función hash y operación que se desplaza sobre la composición.

Pregunta:

¿Existe una función hash $ H $ y una operación $ \ otimes $ que cumplan la siguiente propiedad?

$$ H (A) \ a veces H (B) = H (A \ veces B) $$

$ A $ y $ B $ son dos bloques de bytes de idéntica longitud, si es necesario restringidos a una longitud fija (por ejemplo, 128 bytes). $ H $ debería ser una función hash criptográfica, en particular, debería ser resistente a la imagen previa y a las colisiones.

Ocurrencia

Una idea basada en un sistema de ecuaciones usando $ XOR $ que pregunté en el foro de matemáticas . Pero lo que más me interesa son los enfoques existentes o el razonamiento de por qué esto podría no ser posible.

Respuesta:

Si permite diferentes operaciones $ (\ oplus, \ otimes) $ en la entrada y la salida, entonces existe una propiedad de este tipo para la función hash de Pedersen. Arregle un grupo $ \ mathbb {G} $ de orden $ p $ con dos generadores $ (g, h) $ , y suponga que calcular el logaritmo discreto de $ h $ en base $ g $ es difícil. Entonces la función $ H: \ mathbb {Z} _p \ times \ mathbb {Z} _p \ mapsto \ mathbb {G} $ que mapea $ (a, b) \ in \ mathbb {Z} _p \ times \ mathbb {Z } _p $ a $ H (a || b) = g ^ ah ^ b $ es una función hash resistente a colisiones (bajo la suposición de logaritmo discreto) que se comprime aproximadamente en un factor 2 (sobre grupos donde los elementos del grupo se pueden representar de forma compacta).

Luego, definiendo $ \ oplus: ((a, b), (a ', b')) \ rightarrow (a + a ', b + b') $ y $ \ otimes $ como la operación de grupo, tenemos $ H (a, b) \ a veces H (a ', b') = H ((a, b) \ oplus (a ', b')) $ .

No conozco ningún ejemplo en el que $ \ oplus = \ otimes $ .

Entonces

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top

web tasarım