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: Tue, 29 Sep 2015 11:28:52 +0200
From: Dmitry Khovratovich <>
To: "" <>
Subject: Asymmetric proof-of-work based on the Generalized Birthday problem

Dear all,

we have recently developed a memory-hard proof-of-work, which is based on
the well known Generalized Birthday problem: given a list of binary vectors
X_1,X_2,..X_N and number k find i1,i2,..ik such that
X_i1 + X_i2 +.. + X_ik =0.

The non-trivial algorithm for it was developed by Wagner in 2001 and has
been studied extensively since then.

Our proof-of-work is tunable for time, memory, and time-memory tradeoff
independently, and verification is instant. Uniquely, by varying k  any
tradeoff resilience level can be chosen (e.g., one may require that the
time grows as 4-th power of the memory reduction).

 For example, the proof for 700-MB memory is 148 bytes long. The
implementation exists but is not optimized.

In our paper we explore in details all the related time-space tradeoffs,
compare the scheme to existing alternatives, discuss its implementations on
ASICs and GPUs, and estimate its performance and bandwidth requirements.

The full paper is available at

Comments are welcome.
Best regards,
Alex Biryukov
Dmitry Khovratovich

Content of type "text/html" skipped

Powered by blists - more mailing lists