## π Multi-Instance Unrecoverability of iMHF-Based Password Hashing
βοΈ Charles John Dodd, Pooya Farshim, Siamak F. Shahandashti, Karl Southern
ποΈ OpenAlex Β· π
2026-09-18
---
This paper gives the first formal treatment of unrecoverability for graph-based data-independent memory-hard functions in the multi-instance setting, which is the model that matters for breached password databases. The authors connect pebbling complexity and attacker cumulative memory cost to concrete bounds on password recovery, showing when memory hardness actually translates into linearly scaling attacker effort.
**π Key Findings:**
- Separates plain memory-hardness guarantees from the stronger question of whether compromised password-bank inputs remain unrecoverable.
- Formalizes multi-instance unrecoverability for graph-based data-independent MHFs, where attacker effort should scale with the number of cracked instances.
- Extends ex-post-facto pebbling and unguessability-reduction techniques to derive compatible security bounds.
- Produces concrete unrecoverability results for Argon2i, Catena, and Balloon hashing.
- Shows attacker advantage scales linearly with both the number of targeted instances and cumulative memory complexity under the derived bounds.
---
π [Read paper](https://openalex.org/W7135164833)
#cryptography #cybersecurity #privacy
β±οΈ 2026-04-27 21:00 UTC