[Cryptography] Quantum hardness of key stretching

[Arnold Reinhold]

I was recently asked how to pick passphrases for quantum computing resistance. The questioner noted that standard advice is to use twice the key length one would normally use pre-QC (based on Grover's algorithm). To get a passphrase with 256-bit security would require 50 random characters from {a-z, 0-9} or 20 Diceware words, well beyond most people’s ability to memorize. 

I replied suggesting the real solution is to only use security software that incorporates key stretching for passphrases. Algorithms that use a lot of memory as well as processing power, such as scrypt or argon2, should be much more resistant to quantum attack, though I have not seen a formal analysis. 

Assuming there isn’t a time-memory trade off for a key stretcher that requires lots of memory, the number of coherent q-bits needed would seem to be at least the number of required memory bits, by design potentially millions or billions. That should be orders of magnitude more q-bits than needed for cracking RSA, say. That could make QC attacks infeasible or at the very least give plenty of warning, since practical QC attacks would have appeared for current public key systems long before attacks on large memory key stretchers would be possible. Am I missing something? Is argon2-level key stretching enough to allow passphrases of current strength to be secure in a post quantum world? Is there any literature on quantum hardness of key stretching? 

Arnold Reinhold