# Special-purpose witness encryption without multilinear maps

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?

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

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).

• Thanks! This was very helpful -- I'm accepting Mehdi's answer because it gave more examples, but I wish I could accept yours too. – Andrew Poelstra Jun 1 '17 at 17:01