En el campo matemático y de la informática de la criptografía , se dice que un grupo de tres números ( x , y , z ) es una garra de dos permutaciones f 0 y f 1 si
Se dice que un par de permutaciones f 0 y f 1 no tienen garras si no existe un algoritmo eficiente para calcular una garra.
La terminología claw-free fue introducida por Goldwasser , Micali y Rivest en su artículo de 1984, "A Paradoxical Solution to the Signature Problem" (y más tarde en un artículo de revista más completo), donde demostraron que la existencia de pares de permutaciones de trampilla sin garras implica la existencia de esquemas de firma digital seguros contra ataques adaptativos de mensajes elegidos . [1] [2] Esta construcción fue reemplazada más tarde por la construcción de firmas digitales a partir de cualquier permutación de trampilla unidireccional. [3] La existencia de permutaciones de trampilla no implica por sí misma que existan permutaciones sin garras; [4] sin embargo, se ha demostrado que existen permutaciones sin garras si la factorización es difícil. [5]
La noción general de permutación sin garras (no necesariamente trampilla) fue estudiada más a fondo por Ivan Damgård en su tesis doctoral The Application of Claw Free Functions in Cryptography (Universidad de Aarhus, 1988), donde mostró cómo construir funciones hash resistentes a colisiones a partir de permutaciones sin garras. [5] La noción de ausencia de garras está estrechamente relacionada con la de resistencia a colisiones en funciones hash. La distinción es que las permutaciones sin garras son pares de funciones en las que es difícil crear una colisión entre ellas, mientras que una función hash resistente a colisiones es una función única en la que es difícil encontrar una colisión, es decir, una función H es resistente a colisiones si es difícil encontrar un par de valores distintos x , y tales que
En la literatura sobre funciones hash, esto se denomina comúnmente colisión hash . Se dice que una función hash en la que es difícil encontrar colisiones tiene resistencia a colisiones .
Dado un par de permutaciones sin garras f 0 y f 1 es sencillo crear un esquema de compromiso . Para comprometerse con un bit b, el emisor elige un x aleatorio y calcula f b ( x ). Dado que tanto f 0 como f 1 comparten el mismo dominio (y rango), el bit b está estadísticamente oculto para el receptor. Para abrir el compromiso, el emisor simplemente envía la aleatoriedad x al receptor. El emisor está ligado a su bit porque abrir un compromiso con 1 − b es exactamente equivalente a encontrar una garra. Nótese que, al igual que la construcción de funciones hash resistentes a colisiones, esta construcción no requiere que las funciones sin garras tengan una trampilla.
{{cite journal}}: Requiere citar revista |journal=( ayuda )