In this paper (Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-Quantum World), author describe password authenticated key exchange scheme on page 9 and 10 (see Fig. 1 on page number 10).

I have following doubts in my mind

  1. How initially new user starts communication with the server. Whether there is any registration process for new user?
  2. How server gets the client password, as in the protocol client do not send any password. On the contrary, server verifies it as $\gamma$' = -H1(pwc) where pwc is client password. I think Server may ask for password from client during registration phase and then store it in its database but i am not sure.
  3. In Fig. 1 on page number 10, client send $<C,m>$ to server. Is 'C' is client's id or sid or something else. As author do not give any description of it.
  4. Similarly, S is in session key formation skc= H4(C,S,m,$\mu$,$\sigma$,$\gamma$') in Fig.1. Is S is server id or sid or something else?

Please Guide.

  • $\begingroup$ I have started a chat related to cryptanalysis of key exchange given by Ding et al. based RLWE. Please see it here chat.stackexchange.com/rooms/62701/pake-based-on-rlwe $\endgroup$
    – vivek
    Commented Jul 24, 2017 at 5:20

1 Answer 1


A password authenticated key exchange (PAKE) scheme assumes that the two parties have some shared secret (the password) with too little entropy. They now want to agree on a key and authenticate each other using this password.

The trick is to do this in such a way that an attacker cannot brute force the password with recorded data. This ensures the password remaining secure in spite of the low entropy because you always have to talk to one of the parties to try a guess.

So 1. and 2. are out of scope for PAKE schemes. The password is just assumed to be pre-shared. 3. and 4.: Yes, $\mathcal{C}, \mathcal{S}$ identify the client and the server. These must usually be included in authentication protocols to avoid tricky relay attacks. I recommend Boyd's book for details.

  • $\begingroup$ Therefore, It means that the two party will exchange their password using other means like telephone, email or other. Also, can you please tell that 'q' parameter used in Fig. 1 ($ R_q$) is public or not . Thanks $\endgroup$
    – vivek
    Commented Jun 24, 2017 at 10:30
  • $\begingroup$ They will probably still have some sort of registration process as you suggested in (1.) but this is out of scope of the PAKE scheme. And yes $R_q$ is a public parameter. $\endgroup$
    – Elias
    Commented Jun 24, 2017 at 17:15
  • $\begingroup$ I want to design secure key exchange protocol . Can you please tell which books or research papers i should study, so that i can design secure key exchange protocol (specifically PAKE). Thanks $\endgroup$
    – vivek
    Commented Jun 25, 2017 at 5:44

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.