[Cryptography] Looking for sequential-memory-hard hashing

[Ray Dillinger]

On 03/15/2015 09:28 PM, Zooko Wilcox-OHearn wrote:

> Another piece of related work is John Tromp's Cuckoo Hashing Proof Of
> Work: https://raw.githubusercontent.com/tromp/cuckoo/master/cuckoo.pdf
> 
> I think there is a pretty close relationship between your proposal of
> partially-colliding triplets which have a relationship between the
> three pre-images and Cuckoo. To see what I mean, read the part of the
> cuckoo PDF about "Momentum", which is a lot like your proposal and
> which Cuckoo is a generalization of.

It looks like the "momentum function" is very much the same thing
as the "triplet search" I had proposed.  This is good, because it
means it's in published literature and I can search published
literature for attacks on it now. I'm a little worried about
susceptibility to some application of Bloom Filters for example.

The cuckoo cycle construction -- wow that's neat.  Nice algorithm
for it, supralinear memory-to-difficulty curve, sequential
memory hard, and even more contention for memory bandwidth and
write locks on its table than the triplet birthday/momentum
hashing.  It's a *LOT* heavier to compute though.  Hmmm.  I'll
have to run simulations and see how much of a burden it is.

There is a unifying notion that these memory-intensive algorithms
have in common.  What we're all doing is looking for sets of hashes
that have some relationship to each other, where the appearance
of the new members of that relationship is not predictable.  That
requires saving previous results because new results are equally
likely to join *any* of the already-computed results to make the
relationship.  But, wow, I was only looking for sets of three.
Tromp's Cuckoo cycle construction is looking for a similarly
precise relationship on sets of forty-two.

Bear
---------
"Kitten hockey has rules that every kitten understands.  They are
subtle, but we humans at least know that goals are scored when
things go under furniture where they cannot be retrieved."

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150315/36068c6b/attachment.sig>