Welcome to the resource topic for 2022/1347
Title:
Trace and Revoke with Optimal Parameters from Polynomial Hardness
Authors: Shweta Agrawal, Simran Kumari, Anshu Yadav, Shota Yamada
Abstract:A trace and revoke (\sf{TR}) scheme is an N user traitor tracing scheme which additionally enables the encryptor to specify a list L \subseteq of revoked users so that these users can no longer decrypt ciphertexts. The ``holy grail’’ of this line of work is a construction which resists unbounded collusions, achieves ciphertext, public and secret key sizes independent (ignoring logarithmic dependencies) of |L| and |N|, and is based on polynomial hardness assumptions. In this work we make the following contributions:
-
Public Trace Setting: We provide a construction which (i) achieves optimal parameters, (ii) supports embedding identities (from an exponential space) in user secret keys, (iii) relies on polynomial hardness assumptions, namely compact functional encryption ({\sf FE}) and a key-policy attribute based encryption ({\sf ABE}) with special efficiency properties constructed by Boneh et al. (Eurocrypt 2014) from Learning With Errors ({\sf LWE}), and (iv) enjoys adaptive security with respect to the revocation list. The previous best known construction by Nishimaki, Wichs and Zhandry (Eurocrypt 2016) which achieved optimal parameters and embedded identities, relied on indistinguishability obfuscation, which is considered an inherently subexponential assumption and achieved only selective security with respect to the revocation list.
-
Secret Trace Setting: We provide the first construction with optimal ciphertext, public and secret key sizes and embedded identities from any assumption outside Obfustopia. In detail, our construction relies on Lockable Obfuscation which can be constructed using {\sf LWE} (Goyal, Koppula, Waters and Wichs, Zirdelis, Focs 2017) and two {\sf ABE} schemes: (i) the key-policy scheme with special efficiency properties by Boneh et al. (Eurocrypt 2014) and (ii) a ciphertext-policy {\sf ABE} for {\sf P} which was recently constructed by Wee (Eurocrypt 2022) using a new assumption called evasive and tensor {\sf LWE}. This assumption, introduced to build an {\sf ABE}, is believed to be much weaker than lattice based assumptions underlying {\sf FE} or {\sf iO} – in particular it is required even for lattice based broadcast, without trace.
Moreover, by relying on subexponential security of {\sf LWE}, both our constructions can also support a super-polynomial sized revocation list, so long as it allows efficient representation and membership testing. Ours is the first work to achieve this, to the best of our knowledge.
ePrint: https://eprint.iacr.org/2022/1347
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .