Password authenticated key exchange using quadratic residues

This paper investigates the feasibility of designing password-authenticated key exchange protocols using quadratic residues. To date, most of the published protocols for password-authenticated key exchange were based on the Diffie-Hellman key exchange. It appears inappropriate to design password-authenticated key exchange protocols using other public-key cryptographic techniques. In this paper, we show that protocols for password-authenticated key exchange can be constructed using quadratic residues and we present the first protocol of this type. Under the factoring assumption and the random oracle model, we show that our protocol is provably secure against off-line dictionary attacks. We also discuss the use of cache technique to improve the efficiency of our protocol.