I am working on Password Authenticated Key Exchange (PAKE). I noted some PAKE schemes were built upon the smooth projective hash function (SPHF). I am confused why SPHF can be used to design PAKE?

I can understand the definition of SPHF and I know it is a special case of designated-verifier ZK. But what are the main advantages of SPHF for PAKE?


SPHF are a very versatile tool, and they have a large number of applications. Their application to PAKE stems from three main properties:

  • first, they allow for low-interactivity PAKE. Note that this is very desirable, since latency is one of the main source of inefficiency when communicating with a server on the web. To see it, consider a construction with a designated-verifier proof: intuitively, each player could just prove to the other that, say, some commitment contains the right password. The parties could then perform a standard key exchange after verifying the proofs. However, making this formal requires in particular several rounds of interactions. SPHFs improve that because for PAKE, it is not needed at all that each party proves to the other that he knows the right password: we only want to ensure that if both parties know the same password, they get the same strong key. Intuitively, this fits perfectly the SPHF definition: an SPHF gives you some specific kind of designated-verifier proof where the prover and the verifier end up having the same random key in the statement is true, and independent keys otherwise. To make that a real proof, the prover then sends his key to the verifier, who checks that this is the same as the one she got. But in the PAKE application, this last check is not needed: the hash values can directly be used as the strong key, without any further verification step. Hence, this allows for single round PAKE (for more details, see this paper).
  • Second, they can be built from well-studied standard assumptions, namely, DDH (and it's variant, such as DLIN). In contrast, the natural alternative approach to obtaining a low-interactivity PAKE (which, as I already argued, is very desirable for efficiency reasons) would rely on non-interactive zero-knowledge proofs, which are not known from such well-studied assumptions (existing efficient NIZKs require pairing-based cryptography, or the random oracle model).
  • Third, they are very algebraic, which is a strong bonus both for optimizing efficiency (since all kinds of tricks, such as batching, become available) and analyzing security. Hence, SPHFs lead to the most efficient PAKEs in the standard model (with only 6 group elements sent by each party, in a single round) with the highest security notion (UC security, which means security even in an arbitrary concurrent setting, as well as full adaptive security for some more recent constructions).
  • $\begingroup$ Thanks, Geoffroy! There are a lot of PAKE protocols which are based on number-theoretic assumptions, such as J-PAKE. And I guess, in the industrial community, most guys would like to use the basic hash function (eg, SHA-1) to achieve the PAKE. So I am confusing what are the main advantages of SPHF-based PAKE compared with PKAE based on a hash function like SHA-1? Is it possible to use SPHF-based PAKE to replace the hash function based PAKE in the real world? $\endgroup$ – Z.P. Apr 13 at 15:25
  • 1
    $\begingroup$ What are the "PAKE based on a hash function like SHA-1" that you have in mind? I'm not aware of a PAKE based solely on such structureless hash functions. Show me one if you know of any, then I can try to compare it to SPHF-based PAKEs. And if they simply do not exist, well, existing is a clear advantage of SPHFs-based PAKEs :) (SPHFs are not just hash functions, they have a lot of additional structure, and cannot be build from structurless hash such as SHA-1 as far as we know) $\endgroup$ – Geoffroy Couteau Apr 13 at 15:28
  • $\begingroup$ Thanks, Geoffroy! Regarding PAKE based on hash functions, I mean PAKE protocols like Fig1 to Fig 4 in VTBPEKE (di.ens.fr/david.pointcheval/Documents/Papers/2017_asiaccsB.pdf ) and Protocol EKE2, Figure 9 of eprint.iacr.org/2017/1111.pdf. These protocols just used simple hash functions to obtain the PAKE. So my question is that why these protocols are widely accepted, in particular, J-PAKE (tools.ietf.org/html/rfc8236), rather than SPHF-based PAKEs. So what're the main advantages of SPHF-based PAKE compared with PAKEs I mentioned above? $\endgroup$ – Z.P. Apr 14 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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