Join Log in
Score:2
avatar Crypto

GL-SPHF and witness encryption

cn flag
PatrickG88

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.

52
0 + 0
Score:1
Geoffroy Couteau avatar Crypto
cn flag
Geoffroy Couteau

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.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.