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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Mar 19, 2017 at 23:44
-
4$\begingroup$ So the verifier needs to know $x$, $hk$, $hp$ and $L$. Where does the zero knowledge come in? $\endgroup$– EliasMar 20, 2017 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$ Mar 20, 2017 at 12:51
-
$\begingroup$ So $w$ is necessary to compute the hash with $hp$? $\endgroup$– EliasMar 20, 2017 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$ Mar 20, 2017 at 13:08