Cryptanalysis of Boyen’s Attribute-Based Encryption Scheme in TCC 2013

Shweta Agrawal; Rajarshi Biswas; Ryo Nishimaki; Keita Xagawa; Xiang Xie; Shota Yamada

Paper 2021/505

Cryptanalysis of Boyen’s Attribute-Based Encryption Scheme in TCC 2013

Shweta Agrawal, Rajarshi Biswas, Ryo Nishimaki, Keita Xagawa, Xiang Xie, and Shota Yamada

Abstract

In TCC 2013, Boyen suggested the first lattice based construction of attribute based encryption (ABE) for the circuit class $NC1$. Unfortunately, soon after, a flaw was found in the security proof of the scheme. However, it remained unclear whether the scheme is actually insecure, and if so, whether it can be repaired. Meanwhile, the construction has been heavily cited and continues to be extensively studied due to its technical novelty. In particular, this is the first lattice based ABE which uses linear secret sharing schemes (LSSS) as a crucial tool to enforce access control. In this work, we show that the scheme is in fact insecure. To do so, we provide a polynomial-time attack that completely breaks the security of the scheme. We suggest a route to fix the security of the scheme, via the notion of admissible linear secret sharing schemes (LSSS) and instantiate these for the class of DNFs. Subsequent to our work, Datta, Komargodski and Waters (Eurocrypt 2021) provided a construction of admissible LSSS for NC1 and resurrected Boyen's claimed result.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Attribute-based encryption lattices linear secret sharing scheme
Contact author(s): shweta a @ cse iitm ac in
rajarshi 369 @ outlook in
ryo nishimaki zk @ hco ntt co jp
keita xagawa zv @ hco ntt co jp
xiexiang @ matrixelements com
yamada-shota @ aist go jp
History: 2021-04-19: received
Short URL: https://ia.cr/2021/505
License: CC BY

BibTeX

@misc{cryptoeprint:2021/505,
      author = {Shweta Agrawal and Rajarshi Biswas and Ryo Nishimaki and Keita Xagawa and Xiang Xie and Shota Yamada},
      title = {Cryptanalysis of Boyen’s Attribute-Based Encryption Scheme in {TCC} 2013},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/505},
      year = {2021},
      url = {https://eprint.iacr.org/2021/505}
}