I've been reading up on different authentication protocols recently while I implemented the sign-in functionality for my website. Many of the suggested methods password-based authentication seem to either rely on non-quantum safe maths (eg. ECC, DH, SRP), or be really complex (eg. aPAKEs), or offer slightly reduced security in my eyes (eg. SCRAM).

I'm especially interested in the password-based authentication protocols as they are the ones that I have this issue with.


How could one design a password-based authentication protocol that satisfies the following constraints?

  1. It's relatively easy to understand the protocol.
  2. The protocol is quantum safe.
  3. The data needed to pass a future authentication challenge shouldn't be stored on the server or sent by the client (besides possibly during initial registration).

Maybe there are existing protocols that comes to mind?


What I meant with constraint 3 is that it seems like an unnecessary vulnerability for the server to have access to all data needed to pass a future authentication challenge. E.g. in SCRAM the server gets access to the clientKey which is all that's needed to pass all future challenges as the client. If the server security is not perfect then a potential attacker could get access to this data as well and impersonate the client. I know that some data will always have to be stored, but it would be better if the data had more limited usability to a potential attacker.

  • 1
    $\begingroup$ There is an RLWE version of SRP, which should satisfy all three requirements. I can't find the full proof anywhere, so I can't vouch for its security. But that's maybe an option. $\endgroup$
    – rozbb
    Commented Nov 16, 2023 at 7:55
  • $\begingroup$ Yes that is interesting. Thank you for the reply! $\endgroup$
    – n-l-i
    Commented Nov 16, 2023 at 11:13
  • $\begingroup$ I think requirement (1) might benefit some reconsideration. The complexity of these protocols also reflects on the kind of issues these protocols are trying to solve. So that would be beneficial for yourself. Furthermore, if you do not wish to use an existing implementation, then it's an opportunity to lear as well. $\endgroup$ Commented Nov 16, 2023 at 16:19

2 Answers 2


It sounds like you need an aPAKE here. Any other form of password authentication will inherently leak pw information.

The omega-method aPAKE is pretty straightforward imo, and instantiable from PQ primitives of PAKE and sigs. For a PQ PAKE you can use CHIC over Kyber.


Assume we're using a security parameter of "keylength |K| is 256 bits", say for AES.

You're asking two things:

  1. Is it OK to use less than |K| bits of input entropy?
  2. Is this still OK in a PQC context?

The answer to (1.) of course is "no". But it's hard to get humans to offer a passphrase with more than a few dozen bits of entropy, so we use password stretchers like argon2id to fake it. To the extent that a simple brute force generator, or dictionary lookup, may stumble upon the chosen passphrase, then nothing will save you. There's no substitute for |K| bits of input entropy. But deliberately CPU-intensive and memory-intensive hashes like Argon2 can make such a search more costly for the attacker. And forcing attacks to be online attacks allows lower input entropy to still offer useful security. Using a password stretcher is compatible with techniques like SCRAM.

The answer to (2.) is "yes", it is.

The data needed to pass a future authentication challenge shouldn't be stored on the server or sent by the client

It's hard to see how that could be workable. It sounds like DH, which has some nice properties, but suffers from MitM exposure. We will need a hash of something, and that is "data" we must store. A server with no list of registered users won't be a very secure server.

  • $\begingroup$ Thank you for your answer! I added an edit to the question clarifying what I meant with the third constraint I outlined. Does that affect the last paragraph of your answer? $\endgroup$
    – n-l-i
    Commented Nov 16, 2023 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.