Paper 2017/650

Efficient Public Trace and Revoke from Standard Assumptions

Shweta Agrawal, Sanjay Bhattacherjee, Duong Hieu Phan, Damien Stehle, and Shota Yamada


We provide efficient constructions for trace-and-revoke systems with public traceability in the black-box confirmation model. Our constructions achieve adaptive security, are based on standard assumptions and achieve significant efficiency gains compared to previous constructions. Our constructions rely on a generic transformation from inner product functional encryption (IPFE) schemes to trace-and-revoke systems. Our transformation requires the underlying IPFE scheme to only satisfy a very weak notion of security -- the attacker may only request a bounded number of random keys -- in contrast to the standard notion of security where she may request an unbounded number of arbitrarily chosen keys. We exploit the much weaker security model to provide a new construction for bounded collusion and random key IPFE from the learning with errors assumption (LWE), which enjoys improved efficiency compared to the scheme of Agrawal et al. [CRYPTO'16]. Together with IPFE schemes from Agrawal et al., we obtain trace and revoke from LWE, Decision Diffie Hellman and Decision Quadratic Residuosity.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
damien stehle @ gmail com
2017-07-05: received
Short URL
Creative Commons Attribution


      author = {Shweta Agrawal and Sanjay Bhattacherjee and Duong Hieu Phan and Damien Stehle and Shota Yamada},
      title = {Efficient Public Trace and Revoke from Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/650},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.