GL-SPHF and witness encryption

Question

I recently came across this fascinating paper, and was wondering about whether the GL-SPHF that the paper constructs can be used to create a witness encryption scheme for algebraic branching programs. That is, if Alice could derive the appropriate parameters $\Gamma$ and $\theta$ for the GL-SPHF for a given algebraic branching program, then she could derive a symmetric key from the hash $H$ computed from the private hashing key $hk$, encrypt some data, then send the encrypted data along with the public hashing key $hp$ and public parameters to Bob. Now, Bob will only be able to derive the symmetric key if he knows an appropriate witness.

Applied to algebraic branching programs, this seems to be a useful technique, but an application to witness encryption is not mentioned in the paper. What am I missing? Is the above scheme insecure for some reason? Or are ABPs not as powerful as I am understanding? Or something else?

Thanks, and apologies if the answer is obvious.

Answer 1

Yes, you can derive a witness encryption for a language related to ABPs from this result - generally, it is easy to construct witness encryption for a language $\mathcal{L}$ given an SPHF for the same language.

However, one has to be careful with the kind of languages we are talking about. The paper specifically targets commit-and-prove languages. In the ABP context, this means that we can get a witness encryption for languages of the form

$\mathcal{L}_F = \{(c_1, \cdots, c_n) \;:\; c_1 = \mathsf{Com}(x_1) \wedge \cdots \wedge c_n = \mathsf{Com}(x_n) \wedge F(x_1, \cdots, x_n) = 1\},$

where $\mathsf{Com}$ is a commitment scheme, and $F$ is an arithmetic branching program (the choice of the constant $1$ in the equality is arbitrary). This is a relatively useful and general family of languages, but it is nevertheless a restricted family.