phc-discussions - Re: Asymmetric proof-of-work based on the Generalized Birthday problem

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date: Wed, 30 Sep 2015 09:40:32 -0400
From: John Tromp <john.tromp@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: Asymmetric proof-of-work based on the Generalized Birthday problem

dear Dmitry,

> Comments are welcome.--

Your statements on Cuckoo Cycle appear to be based
on an obsolete version of the paper.

Dramatic optimization has been impossible for over a year,
ever since I incorporated Andersen's edge-trimming into the
reference implementation in May 2014.

Cuckoo Cycle is amortization free, as you need multiple graphs
to find multiple 42 cycles (chances of a single graph having
multiple 42-cycles are exceedingly small).

Why do you qualify Cuckoo Cycle as parallellizable, rather than
parallelism constrained as it is by RAM bandwidth?

Btw, Cuckoo Cycle graphs are undirected, contrary to your description.

There is good evidence of edge trimming being optimal,
as it uses just 1 bit per edge (as well as the most trivial of code),
and there is a quadratic lower bound on the
product of time and space for graph traversal
(a different but closely related problem).

In comparison, the algorithm in the paper is quite a bit more complicated,
with tables of hashes and pairs of indices.

Could I please get a copy of your source code?

regards,
-John