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-prev] [day] [month] [year] [list]
Date: Wed, 30 Sep 2015 17:58:25 -0400
From: John Tromp <>
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

>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).


Powered by blists - more mailing lists