I recently came across the term "smooth projective hash function", and I see that there are many constructions nowadays that rely on them, especially some PAKE constructions. But, I didn't exactly understand them. What are they? And why are they so useful?


Smooth projective hash functions have been introduced by Cramer and Shoup under the name hash proof systems. An SPHF for a language $L$ allows to hash a word $x$, in two different ways: either with some secret key (the hashing key, usually denoted $\mathsf{hk}$) or with the associated public key (the projection key, usually denoted $\mathsf{hp}$). It must satisfies two properties:

  • If the word $x$ is in the language, both ways of hashing will return the same hash value
  • If the word $x$ is outside the language, the hash obtained with the secret key is statistically indistinguishable from random, even given the public key

Intuitively, this can be used as a kind of designated-verifier zero-knowledge proof (although it does not satisfy the classical zero-knowledge property): to prove the $x \in L$, the prover receives the projection key $\mathsf{hp}$ from the verifier, and hashes the word with respect to $L$, using $\mathsf{hp}$, and sends back the result. The verifier compares it to the hash obtained with the secret key and accepts the proof if both hashes are the same.

  • 4
    $\begingroup$ So the verifier needs to know $x$, $hk$, $hp$ and $L$. Where does the zero knowledge come in? $\endgroup$ – Elias Mar 20 '17 at 10:16
  • $\begingroup$ A language $L$ in $NP$ is associated to a polytime relation $R$ as follows: $L = \{x : \exists w, R(x,w) = 1\}$. The prover knows a witness $w$ which allows to verify that $x$ belongs to $L$ in polynomial time - this is the information that should remain secret (think for example about knowing the random coins of a ciphertext). However, the protocol I mentioned is zero-knowledge only when the verifier plays honestly (hence my sentence "it does not satisfy the classical zero-knowledge property"); a cheating verifier could learn information on $w$. $\endgroup$ – Geoffroy Couteau Mar 20 '17 at 12:51
  • $\begingroup$ So $w$ is necessary to compute the hash with $hp$? $\endgroup$ – Elias Mar 20 '17 at 13:02
  • 1
    $\begingroup$ Yes, and this is somewhat implicit given the definitions: if deciding whether $x \in L$ is computationally infeasible, then the situation $x \in L$ and $x \notin L$ are computationally indistinguishable, hence the hash with $\mathsf{hk}$ is computationally indistinguishable from random even given $\mathsf{hp}$. Knowing $w$ is necessary to compute the hash value with $\mathsf{hp}$. $\endgroup$ – Geoffroy Couteau Mar 20 '17 at 13:08

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.