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
| ||
|
Message-ID: <CAOU__fzFsjmJn_-M7BkFnPu3urNx=yTbXdRPsbp2rAZLrHxO1A@mail.gmail.com> 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
Powered by blists - more mailing lists