Quelle est la différence entre faible et forte résistance

la propriété de faible résistance aux collisions est parfois aussi appelée deuxième résistance au préimage:

Donné un arbitraire x il n'existe pas de x' avec x' != x de sorte que h(x) = h (x')

par contre, la forte résistance aux collisions est définie comme suit:

Il n'existe pas de x et x' avec x != x', de sorte que h(x) = h(x')

la différence évidente dans leurs définitions est que pour les collisions faibles nous supposons que la résistance est liée à un choix particulier de x, alors que dans la définition de résistance de collision forte nous sommes libres de choisir arbitrairement nos x et x'. Encore cela semble être très similaire, alors regardons deux exemples.

faible résistance à la collision

un bon exemple où nous ne sommes réellement intéressés que par une faible résistance aux collisions serait un système de stockage de mot de passe simple. Supposons que nous stockons les mots de passe fournis par l'utilisateur dans une base de données par le stockage de leurs hachage. L'authentification réussirait lorsque le hachage d'un mot de passe fourni par un utilisateur est égal à la valeur stockée précédemment (il s'agit d'un schéma intrinsèquement non sécurisé, mais s'il vous plaît, supportez-moi pour le moment). Maintenant, dans ce cas, le x donné est le mot de passe original (inconnu) qui a été fourni plus tôt. Si un attaquant était capable de résoudre le problème du "second préimage" efficacement, il pourrait obtenir un x ' dont la valeur de hachage est la même que celle du x original, et donc être authentifié avec succès. Veuillez noter que la capacité de produire des collisions arbitraires (c.-à-d. résoudre le problème de collision) est inutile en général dans ce scénario parce qu'il n'est pas trop probable que les X et x' que nous obtenons ressemblent à des mots de passe réels dont les hachures ont déjà été stockées dans la base de données.

forte résistance à la collision

un autre scénario où notre préoccupation est une forte résistance à la collision est par exemple un l'application où vous voulez être en mesure de regarder arbitraire des données stockées dans une base de données à l'aide d'identifiants uniques. Au lieu d'envoyer des requêtes sur les données originales (qui seraient souvent très lentes en raison de la taille potentiellement illimitée des données), vous computeriez des hachures des données à la place. Les Hashes sont très compacts, limités dans leur taille et peuvent donc être demandés beaucoup plus efficacement. En fait, dans ces cas-là, la propriété de résistance (deuxième) pré-image d'un hachage ne vous dérange pas. fonction du tout, surtout parce que les préimages eux-mêmes ne sont pas un secret. Ce qui vous importe, cependant, c'est que vous voudriez absolument éviter deux ensembles de données distincts pour hachurer à la même valeur, qui est essentiellement une collision. Vous ne vous souciez pas d'une collision en particulier, mais vous voulez que cette propriété tienne universellement-i.e. vous ne voulez pas deux ensembles de données ont la même valeur de hachage (imaginez qu'il y ait une 'contrainte unique' définie sur cette colonne). Parce que la sécurité est souvent aucun problème dans ces applications, nous utilisons souvent des hachages Non cryptographiques, principalement parce qu'ils fonctionnent mieux.

La relation entre les deux

intuitivement et aussi sous-entendu par leurs noms, nous pourrions supposer qu'une forte résistance à la collision est quelque chose qui est plus difficile à fournir qu'une faible résistance à la collision. Heureusement pour nous, notre intuition peut être prouvée être correcte sous le modèle Oracle aléatoire. Nous pouvons le prouver par contrapositive en supposant que si nous avions un algorithme polynomial probabiliste efficace pour résoudre "second preimage", alors cela nous donnerait aussi un algorithme efficace pour résoudre"collision".

de Considérer une fonction de hachage h et de ce simple algorithme probabiliste [1]:

Laissez 2ndPreimage être un autre probabiliste (e, Q)-algorithme qui résout "deuxième preimage" pour la fonction de hachage h.

Choose x uniformly at random
value = 2ndPreimage(h, x)
case value == failure -> return failure
case value == x' (!= x) -> return (x, x')

Il est facile de voir que c'est aussi un (e, Q)-algorithme cela résout le gros problème de collision. Cela implique qu'étant donné que nous avons un algorithme pour résoudre "second preimage", nous pouvons également utiliser cet algorithme qui est susceptible de produire une collision. Comme nous n'avons fait aucune supposition sur la fonction de hachage sous-jacente h, nous pouvons maintenant dire en toute sécurité que

une forte résistance à la collision implique une faible résistance à la collision, mais le contraire ne tient pas nécessairement.

[1] e est la probabilité de succès du algorithme, 0 <= e < 1. Q est le nombre maximum de requêtes oracle (c'est à dire "évaluations" de l'algorithme). En cas de succès, l'algorithme retourne une solution valide, sinon il renvoie une valeur indiquant l'échec.