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**

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

2 Asked on October 24, 2021 by super

0 Asked on October 24, 2021 by mallea

0 Asked on October 24, 2021 by bastet-santiago

1 Asked on October 24, 2021 by wecanbefriends

1 Asked on October 24, 2021

0 Asked on October 24, 2021 by kyb3r

1 Asked on October 24, 2021 by user9414424

0 Asked on October 24, 2021

des homomorphic encryption proxy re encryption public key symmetric

0 Asked on October 24, 2021

0 Asked on October 24, 2021 by venkat-chenam

1 Asked on October 24, 2021 by user991

0 Asked on October 24, 2021

blinding chosen ciphertext attack chosen plaintext attack padding rsa

0 Asked on October 24, 2021 by scott-brickey

0 Asked on October 24, 2021 by alfe

Get help from others!

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

Recent Answers

- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir