# 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

### Is it possible to get the PGP public key from PGP message?

1  Asked on October 24, 2021 by zenxiu

### Construction of a “simple”, nothing-up-my-sleeves, provably KPA resistant symmetric cipher

2  Asked on October 24, 2021 by super

### Non-post quantum primitives in MPC protocols: for and against?

0  Asked on October 24, 2021 by mallea

### OpenSSL FIPS integrity check

1  Asked on October 24, 2021 by guille

### Non-interactive proof of friendship

0  Asked on October 24, 2021 by bastet-santiago

### Signing a GPG Public Key

1  Asked on October 24, 2021 by d-o

### What is the order of the Identity point on prime order elliptic curve groups?

1  Asked on October 24, 2021 by wecanbefriends

### What is different between G1×G1→GT and G1×G2→GT in the bilinear pairing?

1  Asked on October 24, 2021

### Should you pad messages encrypted with stream ciphers?

0  Asked on October 24, 2021 by kyb3r

### Is Computational Indistinguishability quantifiable?

1  Asked on October 24, 2021 by user9414424

### Curve25519 Attacks and Security

0  Asked on October 24, 2021

### DES decryption of the homomorphic encryption ciphertext

0  Asked on October 24, 2021

### LWE versus neural nets

2  Asked on October 24, 2021 by steven-yue

### Proof for, Vectors sampled from $D_{(L,r)}$ have Euclidean norm at most $rsqrt{n}$ with a high probability

0  Asked on October 24, 2021

### How are security proofs performed for Certificateless PEKS schemes?

0  Asked on October 24, 2021 by venkat-chenam

### TLS 1.2 is still secure or should we move to TLS 1.3?

1  Asked on October 24, 2021 by r1w

### FHE over the integers – Is that paper’s scheme known to be insecure against quantum adversaries?

1  Asked on October 24, 2021 by user991

0  Asked on October 24, 2021

### File encryption using per-user-encrypted shared key

0  Asked on October 24, 2021 by scott-brickey

### Encrypting/Decrypting using RSA and AES; standards?

0  Asked on October 24, 2021 by alfe