Efficient Public Trace and Revoke from Standard Assumptions

International audienceWe provide efficient constructions for trace-and-revoke systemswith public traceability in the black-box confirmationmodel. Our constructions achieve adaptive security, are basedon standard assumptions and achieve significant efficiencygains compared to previous constructions.Our constructions rely on a generic transformation frominner product functional encryption (IPFE) schemes to traceand-revoke systems. Our transformation requires the underlyingIPFE scheme to only satisfy a very weak notion of security– the attacker may only request a bounded number of randomkeys – in contrast to the standard notion of security whereshe may request an unbounded number of arbitrarily chosenkeys. We exploit the much weaker security model to providea new construction for bounded collusion and randomkey IPFE from the learning with errors assumption (LWE),which enjoys improved efficiency compared to the scheme ofAgrawal et al. [CRYPTO’16].Together with IPFE schemes from Agrawal et al., we obtaintrace and revoke from LWE, Decision Diffie Hellman andDecision Composite Residuosit