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  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 <>
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?


Powered by blists - more mailing lists