Candidate Witness Encryption from Lattice Techniques

Witness encryption (WE), first introduced by Garg, Gentry, Sahai and Waters in [GGSW13], is an encryption scheme where messages are encrypted with respect to instances of an NP relation, such that in order to decrypt one needs to know a valid witness for the instance that is associated with the ciphertext.

Despite of significant efforts in the past decade to construct WE from standard assumptions, to the best of our knowledge all of the existing WE candidates either rely directly on iO or use techniques that also seem to imply iO in the same way that they seem to imply WE.

In this work we propose a new hardness assumption with regard to lattice trapdoors and show a witness encryption candidate which is secure under it. Contrary to previous WE candidates, our technique is trivially broken when one tries to convert it to iO, which suggests that the security relies on a different mechanism. We view the gap between WE and iO as an analogue to the gap between ABE and FE and thus potentially significant.

Intuitively, the assumption says that "the best an attacker can do with a trapdoor sample is to use it semi-honestly" -i.e. that LWE with respect to a public matrix A, given as auxiliary information a trapdoor sample K ← A TD (B), is as hard as LWE with respect to the public matrix [A|B] and no auxiliary information.

In order to formally utilize the assumption we define a notion of LWE oracles with generic distributions of public matrices and auxiliary information. This model allows to bound the hardness of LWE with respect to one distribution as a function of the hardness of LWE with respect to another distribution. Repeated arguments of this flavor can be used as a sequence of hybrids in order to gradually change the challenge that an adversary is facing while keeping track on the security loss in each step of the proof. Typically security proofs of LWE-based systems implicitly make arguments of this flavor for distributions that are indistinguishable, while our model allows to make relaxed arguments that in some cases suffice for the proof requirements.