Kyunghoon Han
is a one-way function
shows significant avalanche effect
has fast computation speed
is injective (dramatically)
is deterministic
from hashlib import md5
str_val = "Se fai fisica ti do una testata"
str_diff= "Se fai fisica ti do unP testata"
hashed = md5(str_val.encode())
hashed_d= md5(str_val.encode())
print("The first hashed sentence? \n")
print(hashed.hexdigest())
print("The second hashed sentence? \n")
print(hashed_d.hexdigest())
The first hashed sentence?
49f75a928653d2efae3e501af30afd70
The second hashed sentence?
fe6c2c08643a137cdb8fc28f8ec25173
Common approach: Weisfeiler-Lehman kernel (2009)
Perform the following on the entire graph
Sort: represent each node $v$ as a sorted list $\ell_v$ of its neighbours.
Compress: compress the list into its hash value $h\left(\ell_v\right)$.
Relabel: relabel $v$ with $h\left(\ell_v\right)$.
import networkx as nx
graph = nx.Graph()
graph.add_edges_from(
[
(1,2, {"label": "A"}),
(2,3, {"label": "B"}),
(3,1, {"label": "A"}),
(1,4, {"label": "B"}),
]
)
nx.weisfeiler_lehman_graph_hash(graph)
the result is...
'7bc4dde9a09d0b94c5097b219891d81a'
import networkx as nx
graph = nx.Graph()
graph.add_edges_from(
[
(1,2, {"label": "A"}),
(2,3, {"label": "B"}),
(3,4, {"label": "A"}),
(1,4, {"label": "B"}),
]
)
nx.weisfeiler_lehman_graph_hash(graph)
the result is...
'20a60ed013bc1976376f734be7d8d92c'
which seems promising... but
import networkx as nx
graph = nx.Graph()
graph.add_edges_from(
[
(1,2, {"label": "A"}),
(2,4, {"label": "B"}),
(3,1, {"label": "A"}),
(1,4, {"label": "B"}),
]
)
nx.weisfeiler_lehman_graph_hash(graph)
the result is...
'7bc4dde9a09d0b94c5097b219891d81a'
a single change (second node) couldn't produce the avalanche effect...