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 ℓv of its neighbours.
Compress: compress the list into its hash value h(ℓv).
Relabel: relabel v with h(ℓv).
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...