Date: Thu, 10 Apr 2014 10:27:04 +0200
From: Krisztián Pintér <pinterkr@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Gambit review


Bill Cox (at Wednesday, April 9, 2014, 11:18:25 AM):

> In short, the modified approximation is easy to pebble (exactly zero
> recomputations) down to 1/8th pebbles (relative to a 4-row graph
> size), and then my code fails completely to find any pebbling solution
> for even 1 fewer pebbles.  I was not able to pebble any sized graph I
> tried with 1/8th - 1 pebbles

> recomputation weakness I haven't found, then it is *very* strong
> against TMTO's below the 1/8th memory mark, very likely the strongest
> cache-timing resistant entry in the PHC at the 1/8th mark.  All of the

i'y very grateful for your efforts. these results are reassuring. this
is a very crucial point for gambit, since i don't have a proof. i do
have a rationale, but it is more in the "educated voodoo magic"
category than anything else.

> Because Gambit XORs over memory, the reality of pebbling Gambit may be
> quite a bit harder.

i suspect, based on my earlier attempts of analysis, that lack of
xoring lowers the memory footprint by a constant factor. that is, you
can achieve the same time using c*m memory instead of m, where c is a
constant like 0.7 or something, i don't have an exact value.

> Catena uses a faster hash function (Blake2b).

please bear in mind that there is the (real!) possibility to use
reduced round keccak. keccak authors have a paper on that, but i was
unable to find it. when i find it, i will include this in the pdf as a
footnote. without any actual knowledge, i suspect we can get a speedup
of 2x - 6x.

granted, the same thing probably can be done with catena, which as of
now uses a probably unnecessarily strong internal hash.

Powered by blists - more mailing lists