16

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?

typos
  • 809
  • 6
  • 11

1 Answers1

18

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.

Geoffroy Couteau
  • 19,919
  • 2
  • 46
  • 68
  • 4
    So the verifier needs to know $x$, $hk$, $hp$ and $L$. Where does the zero knowledge come in? – Elias Mar 20 '17 at 10:16
  • 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$. – Geoffroy Couteau Mar 20 '17 at 12:51
  • So $w$ is necessary to compute the hash with $hp$? – Elias Mar 20 '17 at 13:02
  • 1
    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}$. – Geoffroy Couteau Mar 20 '17 at 13:08