Special-purpose witness encryption without multilinear maps

Question

In Witness Encryption and its Applications Garg et al describe "witness encryption" which allows one to encrypt some specified data to a NP problem, such that another party can decrypt iff they present some witness to the NP problem.

They give general construction using multilinear maps based on a reduction of NP from CNF predicates to subset-sum problems.

Are there any examples of witness encryption on a smaller class of problems (say, inner products, or preimages of point functions, or discrete logarithms) that are provably secure without multilinear maps?

Answer 1

Witness encryption is essentially the same thing as hash proof systems (what some people call “smooth projective hash functions”), so we know quite a few examples.

The best-known one is probably the Cramer-Shoup SPHF, which can be seen as a witness encryption scheme with respect to the NP language of Diffie-Hellman pairs. Precisely, we have a cyclic group $G$ and consider the language $L\subset G\times G$ of pairs $(g^w, h^w)$, where $g,h$ are two given generators of $G$. One can then define an encryption of $m\in G$ with respect to an arbitrary pair $(u,v)\in G^2$ as $(c_0,c_1)=(g^rh^s,m\cdot u^rv^s)$ for random exponents $r,s$. If $(u,v)\notin L$ and the DDH assumption holds in $G$, it is easy to verify that $(g^rh^s, u^rv^s)$ is uniformly random in $G^2$, so $m$ is statistically hidden. On the other hand, if $(u,v)\in L$ and someone knows a witness to that fact, namely $(u,v)=(g^w,h^w)$ and one knows $w$, then it is easy to decrypt: one can simply recover $m$ as $c_1/c_0^w$. So we have a witness encryption scheme as required.

There are many more examples: SPHFs for the language of valid commitments in some suitable commitment scheme, etc.

Here is a very nice talk by Victor Shoup himself on the subject: https://www.youtube.com/watch?v=2aX-0E07Fpg

Answer 2

One obvious example would be the factorization problem, with the Rabin encryption system.

One way of stating the factorization decision problem is: given $x, M$, does there exist integers $y, z$ such that $1 < y < x$ and $yz = M$? The witness would be the values $y, z$.

If we constrain the values of $M$ to be Rabin modulii (product of two prime factors, with both factors $3 \bmod 4$), then Rabin is provably equivalent to the factorization problem. Hence, if you can decrypt, then you can produce a witness (as you can factor), and if you can produce a witness, then you can decrypt (as you can factor).