Hash of the Future?
Have you ever struggled to solve a
maze? Then imagine trying to find a path through a tangled,
three-dimensional maze as large as the Milky Way. By incorporating such
a maze into a hash function, Kristin Lauter of Microsoft Research in
Redmond, Washington, is betting that neither you nor anyone else will
solve that problem.
Technically, Lauter's maze is called an "expander graph" (see figure,
right). Nodes in the graph correspond to elliptic curves, or equations
of the form y2 = x3+ ax + b.
Each curve leads to three other curves by a mathematical relation, now
called isogeny, that Pierre de Fermat discovered while trying to prove
his famous Last Theorem.
CREDIT: MICROSOFT RESEARCH
To hash a digital file using an expander graph, you would convert the
bits of data into directions: 0 would mean "turn right," 1 would mean
"turn left." In the maze illustrated here, after the initial step 1-2,
the blue path encodes the directions 1, 0, 1, 1, 0, 0, 0, 0, 1, ending
at point 24, which would be the digital signature of the string
101100001. The red loop shows a collision of two paths, which would be
practically impossible to find in the immense maze envisioned by Lauter.
Although her hash function (developed with colleagues Denis Charles and
Eyal Goren) is provably secure, Lauter admits that it is not yet fast
enough to compete with iterative hash functions. However, for
applications in which speed is less of an issue--for example, where the
files to be hashed are relatively small--Lauter believes it might be a