Skip to main content

Efficient Public Trace and Revoke from Standard Assumptions

Agrawal, Shweta, Bhattacherjee, Sanjay, Phan, Duong Hieu, Stehlé, Damien, Yamada, Shota (2017) Efficient Public Trace and Revoke from Standard Assumptions. In: Proceedings of the ACM Conference on Computer and Communications Security. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. . pp. 2277-2293. Association for Computing Machinery, New York- United States ISBN 978-1-4503-4946-8. (doi:10.1145/3133956.3134041) (KAR id:83284)

PDF Author's Accepted Manuscript
Language: English
Download (624kB) Preview
[thumbnail of 3.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL


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 Composite Residuosity.

Item Type: Conference or workshop item (Paper)
DOI/Identification number: 10.1145/3133956.3134041
Uncontrolled keywords: Inner-product functional encryption; Trace-and-revoke; Public traceability
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
University-wide institutes > Institute of Cyber Security for Society
Depositing User: Sanjay Bhattacherjee
Date Deposited: 06 Oct 2020 10:45 UTC
Last Modified: 07 Apr 2022 09:50 UTC
Resource URI: (The current URI for this page, for reference purposes)
Bhattacherjee, Sanjay:
  • Depositors only (login required):


Downloads per month over past year