# Is Argon2 "sequential memory hard"?

Cryptography Asked by Modal Nest on January 22, 2021

The Scrypt paper here defines memory-hard and sequential memory hard functions as follows:

Definition 1. A memory-hard algorithm on a Random Access Machine is an algorithm which uses $$S(n)$$ space and $$T(n)$$ operations, where $$S(n) in Omega (T(n)^{1-epsilon})$$

Definition 2. A sequential memory-hard function is a function which

(a) can be computed by a memory-hard algorithm on a Random Access Machine
in $$T(n)$$ operations; and
(b) cannot be computed on a Parallel Random Access Machine with $$S∗(n)$$ processors and $$S ∗(n)$$ space in expected time $$T∗(n)$$ where $$S∗(n)T∗(n) =mathcal{O}(T(n)^{2-x})$$ for any $$x > 0$$.

Put another way, a sequential memory-hard function is one where not only the
fastest sequential algorithm is memory-hard, but additionally where it is impossible
for a parallel algorithm to asymptotically achieve a significantly lower cost. Since
memory-hard algorithms asymptotically come close to using the most space possible given their running time, and memory is the computationally usable resource
general-purpose computers have which is most expensive to reproduce in hardware8
,
we believe that, for any given running time on a sequential general-purpose computer, functions which are sequential memory-hard come close to being the most
expensive possible functions to compute in hardware.

However the specification for Argon2 refers only to ‘memory hard’ functions.

In the case of the password hashing, we suppose that the defender allocates certain amount of time (e.g., 1
second) per password and a certain number of CPU cores (e.g., 4 cores). Then he hashes the password using the
maximum amount M of memory. This memory size translates to certain ASIC area A. The running ASIC time $$T$$ is determined by the length of the longest computational chain and by the ASIC memory latency. Therefore,
we maximize the value $$AT$$. The other use cases follow a similar procedure.
Suppose that an ASIC designer that wants to reduce the memory and thus the area wants to compute $$H$$
using $$αM$$ memory only for some $$α < 1$$. Using some tradeoff specific to $$H$$, he has to spend $$C(α)$$ times as much
computation and his running time increases by at least the factor $$D(α)$$. Therefore, the maximum possible gain
$$E$$ in the time-area product is:

$$E_{max} = max α frac{1}{(αD(α)}$$
.

The hash function is called memory-hard if $$D(α) > 1/α$$ as $$α → 0$$.

Questions

1. Is Argon2 sequential memory hard per the specification set out in the Scrypt paper?
2. If not, why? Is it a case of different definitions or a completely different approach?

## Related Questions

### Binomial distribution sampling – concrete example

0  Asked on January 4, 2022

### Using xor encryption in the following use case

1  Asked on December 31, 2021 by kaa

### How to justify the lightweight symmetric PRESENT encryption algorithm is more secure?

0  Asked on December 31, 2021 by sunitha-tappari

### Difference Between an Authentication Token and an OTP (One Time Password)

0  Asked on December 28, 2021 by dawnforce

### Using XOR to derive a data key for ECIES

2  Asked on December 26, 2021 by maarten-bodewes

### Digital Signature or MAC Yielding Non-Binary Verification Predicate

0  Asked on December 24, 2021

### Computing PGP ed25519 and curve25519 keygrips?

2  Asked on December 21, 2021 by skaht

### Find Consecutive X-Coordinate algorithm

1  Asked on December 21, 2021 by kmart875

### Is there any proof for ECDSA signature algorithm?

1  Asked on December 19, 2021 by sanket1729

### What basic knowledge is required to understand SIKE?

1  Asked on December 19, 2021 by vivekanand-v

### Why we can’t implement AES 512 key size?

3  Asked on December 17, 2021 by hamedb71

### MD5 – Chosen Prefix Collision Attack

1  Asked on December 17, 2021

### Does selectively generating keypairs with particular public-key hash prefix weaken the security?

2  Asked on December 17, 2021

### Difference between polynomial embedding and canonical embedding

0  Asked on December 17, 2021

### How can Cipher Block Chaining (CBC) in SSL be attacked?

3  Asked on December 14, 2021 by antonpug

### Subset Sum Hashes

1  Asked on December 14, 2021 by lev-knoblock

### Why is this authenticated Diffie–Hellman key exchange insecure?

1  Asked on December 14, 2021 by beroal

### Homomorphic encryption scheme for modulo reduction

0  Asked on December 8, 2021

### Can we say that password authentication contains registration phase, authentication phase and authenticated key exchange phase?

0  Asked on December 6, 2021 by z-p

### LWR parameter estimation

0  Asked on December 4, 2021 by mev