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?
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 &lt; y &lt; 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).