Non-Trivial Witness Encryption and Null-iO from Standard Assumptions
Non-Trivial Witness Encryption and Null-iO from Standard Assumptions
复制标题
标准假设的非平凡见证加密和 Null-iO
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Daniel Wichs
中科院分区：
文献类型：
--
作者：
Zvika Brakerski;Aayush Jain;Ilan Komargodski;Alain Passelègue;Daniel Wichs
证人加密(WE)方案可以将任何({{extsf{NP})语句作为公钥，并使用它来加密消息。如果该陈述为真，则可以在给定相应证人的情况下解密该消息，但是如果该陈述为假，则该消息在计算上是隐藏的。理想情况下，加密过程应该在多项式时间内运行，但定义一个较弱的概念也是有意义的，我们称之为非平凡指数有效WE(XWE)，其中加密运行时间只需要远小于证人大小为m的({{extsf{NP})关系的平凡(2^{m})界。我们展示了如何在次指数带错误学习(LWE)假设下为所有({{extsf{NP})具有加密运行时间(2^{m/2})的所有({extsf{NP}})构造这样的XWE方案。对于可以在({{extsf{NC}}^1})(例如SAT)中验证的({{extsf{NP}})关系，我们也可以在次指数决策双线性Diffie-Hellman(DBDH)假设下构造这样的XWE格式。尽管我们发现结果令人惊讶，但它是通过一个非常简单的连接到基于属性的加密来实现的。
A witness encryption (WE) scheme can take any ({{ extsf {NP}}}) statement as a public-key and use it to encrypt a message. If the statement is true then it is possible to decrypt the message given a corresponding witness, but if the statement is false then the message is computationally hidden. Ideally, the encryption procedure should run in polynomial time, but it is also meaningful to define a weaker notion, which we call non-trivially exponentially efficient WE (XWE), where the encryption run-time is only required to be much smaller than the trivial (2^{m}) bound for ({{ extsf {NP}}}) relations with witness size m. We show how to construct such XWE schemes for all of ({{ extsf {NP}}}) with encryption run-time (2^{m/2}) under the sub-exponential learning with errors (LWE) assumption. For ({{ extsf {NP}}}) relations that can be verified in ({{ extsf {NC}}^1}) (e.g., SAT) we can also construct such XWE schemes under the sub-exponential Decisional Bilinear Diffie-Hellman (DBDH) assumption. Although we find the result surprising, it follows via a very simple connection to attribute-based encryption.