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__fxEARphifYiwej+a9ay3eUYS8HArooCLS=NszAo+M5_Zg@mail.gmail.com> Date: Wed, 30 Sep 2015 17:58:25 -0400 From: John Tromp <john.tromp@...il.com> To: discussions@...sword-hashing.net Subject: Re: [PHC] Re: Asymmetric proof-of-work based on the Generalized Birthday problem dear Dmitry, > I could not obtain explicit statements of the time and memory requirements > of your scheme from the paper. Have you read the latest version of the paper at https://github.com/tromp/cuckoo/blob/master/doc/cuckoo.pdf?raw=true or https://eprint.iacr.org/2014/059.pdf ? >From the abstract: "Our cycle finding algorithm uses one bit per edge, and up to one bit per node. Runtime is linear in graph size" So for a graph with N nodes, time is O(N) and memory is 1.5N bits. This can be tweaked to time O(2^k N) for memory (0.5+2^{-k})N bits. > Some claims in our paper possibly came from > some misunderstanding. > > Andersen's analysis stated that what previously can be done in time T and > memory M That refers to my "The basic algorithm" in the same named section, which uses time O(N) and memory 32N bits (NlogN to be precise for arbitrary N). > in some form to claim any positive statements about amortization and > tradeoff resilience. Amortization is completely orthogonal and is achieved by having an expected 0.025 42-cycles per random graph (i.e. 2.5% chance of having a 42-cycle). Tradeoff resilience is considered in the section on TMTOs. The TMTO algorithm uses time O(kN) and memory N/k bits, and we study the quite important constant factors involved in that O(). > Currently it is unclear from the paper how much > Andersen's analysis affected the scheme properties. As a result, I had to > rely on his analysis first and parallelizability he explains. Andersen's edge-trimming reduced the memory from NlogN to (0.5+2^{-k})N bits. > If you could make more rigorous claims about behaviour of your scheme under > certain memory reductions and increases, this would help me to reference > your work properly. Memory increases don't help, since runtime is still Omega(N). regards, -John
Powered by blists - more mailing lists