Y a-t-il un hachage continu?

8

Des questions:

Peut-il y avoir un hachage (cryptographiquement sécurisé) qui préserve la topologie des informations de {0,1}?

Pouvons-nous ajouter un prédicat de proximité efficacement calculable qui, étant donné hk(X) et hk(y) (ou y lui-même) nous dit si yest très proche deX (par exemple la distance de Levenshtein ou la distance de Hamming de X et y est inférieur à une constante fixe c)?


Contexte:

Par topologie d'information sur Σ sur je veux dire l'espace de topologie avec des points Σ et avec la base {XΣ:XΣ}.

Une bonne façon de penser à la topologie est de considérer les ensembles ouverts comme des propriétés de points qui peuvent être affirmés / vérifiables (c'est-à-dire si c'est vrai, il peut être vérifié / observé que c'est vrai). Dans cet esprit, les ensembles fermés sont des propriétés réfutables .

Une fonction F:ΣΣest continue si l'image inverse des ensembles ouverts est ouverte. Dans notre cas, cela signifie que pour tousyΣ, il y a jeΣ tel que

f1(yΣ)=xIxΣ.

Une bonne façon de penser à la topologie de l'information est de la considérer comme un arbre de chaînes binaires. Chaque sous-arbre est un ensemble ouvert de base (et d'autres ensembles ouverts peuvent être obtenus en prenant une union d'ensembles ouverts de base).

Ceci est parfois appelé topologie de l'information des chaînes car chaque point Σ peut être considéré comme une approximation finie d'une chaîne / séquence binaire. x se rapproche y ssi x est une sous-chaîne initiale de y (xy). Par exemple0011Σ est une approximation de 00110 parce que 001100110.

Et pour la continuité, si nous prenons une séquence {xi}i qui se rapprochent et convergent en séquence binaire y (penser à y comme une branche infinie dans l'arbre et xis comme points sur cette branche) puis {f(xi)} converger vers f(y),

F(y)=jeF(Xje).
Kaveh
la source
J'ai oublié tout ce que je savais sur la topologie. Serait-il possible de décortiquer ce que signifie «préserver la topologie de l'information» en termes autonomes? De plus, lorsque vous dites sécurité cryptographique, de quelle version parlez-vous? Voulez-vous dire «se comporte comme un oracle aléatoire», ou voulez-vous dire «à sens unique et résistant aux collisions»?
DW
@DW J'ai ajouté quelques explications, mais en écrivant cela me fait remarquer que ma première question n'est pas claire. Je dois réfléchir un peu pour le clarifier. La deuxième question semble correcte.
Kaveh
1
Le hachage sensible à la localité peut être pertinent. en.wikipedia.org/wiki/Locality-sensitive_hashing
zenna

Réponses:

5

Pour les fonctions de hachage cryptographiques modernes, non, il n'y a pas de prédicat de proximité efficacement calculable, en supposant que la distribution sur Xa une entropie suffisante. L'intuition est que ces fonctions de hachage sont conçues pour "ne pas avoir de structure", donc elles n'admettent rien de tel.

En termes techniques, les fonctions de hachage cryptographiques modernes se comportent "comme un oracle aléatoire". Pour un oracle aléatoire, il n'y a pas un tel prédicat de proximité: le mieux que vous puissiez faire semble être d'inverser la fonction de hachage, puis d'énumérer toutes les chaînes proches et de les hacher. En conséquence, il n'y a aucun moyen de le faire pour les fonctions de hachage cryptographiques modernes.

Heuristiquement, il est possible de concevoir une fonction de hachage personnalisée qui admet un prédicat de proximité efficace et qui est (à peu près) "aussi sécurisé que possible" étant donné ce fait. Supposons que les chaînes que nous allons hacher sont de longueur fixe. Supposons que nous ayons un bon code correcteur d'erreurs, et laissons être l'algorithme de décodage (donc il mappe une chaîne de bits à un mot de code à proximité, s'il le peut).

Pour obtenir un schéma simple mais imparfait, imaginez définir h(X)=SHA256((X)). SiX,y sont deux chaînes aléatoires qui sont suffisamment proches, alors il y a une chance décente que h(X)=h(y). SiX,y ne sont pas proches, alors h(X) ne ressemblera en rien h(y), et nous n'obtiendrons aucune information au-delà du fait que X,yne sont pas proches. C’est simple. Cependant, il est également imparfait. Il y a plusieurs pairesX,y qui sont proches, mais où nous ne pouvons pas détecter ce fait h(X),h(y) (par exemple, parce que la fonction de décodage échoue).

Heuristiquement, il semble possible d'améliorer cette construction. Au moment de la conception, choisissez des chaînes de bits aléatoiresr1,,rk. Maintenant, définissez la fonction de hachage suivante:

h(X)=(SHA256((Xr1),,SHA256((Xrk)).

Maintenant si X,y sont suffisamment proches, il est probable qu'il existe je tel que (Xrje)=(yrje), Et ainsi h(X)je=h(y)je. Cela suggère immédiatement un prédicat de proximité: sih(X) allumettes h(y) dans l'un de ses k composants, puis X,ysont proches; sinon, déduisez qu'ils ne sont pas proches.

Si vous souhaitez en outre une résistance aux collisions, une construction simple est la suivante: laissez h1()être une fonction de hachage avec un prédicat de proximité; puish(X)=(h1(X),SHA256(X)) est résistant aux collisions (toute collision pour cela est également une collision pour SHA256) et a un prédicat de proximité (utilisez simplement le prédicat de proximité pour h1). Vous pouvez laisserh1() être la fonction de hachage définie ci-dessus.

C'est tout pour la distance de Hamming. La distance d'édition est probablement beaucoup plus difficile.

En proposant la construction ci-dessus, je me suis inspiré du document suivant:

Ari Juels, Martin Wattenberg. Un plan d'engagement flou .

Ari Juels, Madhi Sudhan. Un système de voûte floue . Dessins, codes et cryptographie 38 (2): 237-257, 2006.

Incidemment: en cryptographie, les fonctions de hachage sont sans clé. Si vous vouliez une chose à clé, vous voudrez peut-être jeter un œil aux fonctions pseudo-aléatoires.

DW
la source