CryptoDB
Candidate Witness Encryption from Lattice Techniques
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2022 |
| Abstract: | 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 ``simple'' 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 from A to B, is as hard as LWE with respect to the public matrix [A|B] and no auxiliary information. In order to formally state the assumption and use it in the security proof we define a notion of LWE challenges with general 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. Independently of lattice techniques, our WE candidate relies on branching programs that behave in a predicted manner when they are executed with inconsistent input sequences. This part of the work is information-theoretic in nature and can possibly be used in other environments as well. |
BibTeX
@inproceedings{crypto-2022-32256,
title={Candidate Witness Encryption from Lattice Techniques},
publisher={Springer-Verlag},
author={Rotem Tsabary},
year=2022
}