4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.