Paper 2016/562

Deniable Attribute Based Encryption for Branching Programs from LWE

Daniel Apon, Xiong Fan, and Feng-Hao Liu


Deniable encryption (Canetti et al. CRYPTO '97) is an intriguing primitive that provides a security guarantee against not only eavesdropping attacks as required by semantic security, but also stronger coercion attacks performed after the fact. The concept of deniability has later demonstrated useful and powerful in many other contexts, such as leakage resilience, adaptive security of protocols, and security against selective opening attacks. Despite its conceptual usefulness, our understanding of how to construct deniable primitives under standard assumptions is restricted. In particular from standard lattice assumptions, i.e. Learning with Errors (LWE), we have only flexibly and non-negligible advantage deniable public-key encryption schemes, whereas with the much stronger assumption of indistinguishable obfuscation, we can obtain at least fully sender-deniable PKE and computation. How to achieve deniability for other more advanced encryption schemes under standard assumptions remains an interesting open question. In this work, we construct a flexibly bi-deniable Attribute-Based Encryption (ABE) scheme for all polynomial-size Branching Programs from LWE. Our techniques involve new ways of manipulating Gaussian noise that may be of independent interest, and lead to a significantly sharper analysis of noise growth in Dual Regev type encryption schemes. We hope these ideas give insight into achieving deniability and related properties for further, advanced cryptographic systems from lattice assumptions.

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
attribute based encryptionLWE
Contact author(s)
xfan @ cs cornell edu
2016-06-05: revised
2016-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Apon and Xiong Fan and Feng-Hao Liu},
      title = {Deniable Attribute Based Encryption for Branching Programs from LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2016/562},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.