Rishab Goyal: Mixed Functional Encryption: A new stepping stone towards efficient tracing

Friday, November 8, 2019 - 10:30am to 12:00pm
Hewlett, G882
Rishab Goyal, University of Texas


In a broadcast encryption (BE) system for N users, as introduced by Fiat and Naor, a sender can encrypt a message m to an arbitrary subset S ⊆ [N] of users such that i-th user can decrypt, using its own private decryption key, iff i ∈ S. Although BE solves the problem of secure broadcast, it introduces the problem of accountability thereby enabling piracy attacks. To that end, Chor, Fiat, and Naor in the early 90s introduced the concept of traitor tracing (TT) capturing such piracy attacks when the sender can only broadcast to all N users. Informally, a TT system guarantees that if some of the N users collude to construct a pirate decoding box, then by running a special "Tracing" algorithm one can identify at least one of the secret keys used to construct the pirate device. The primary goal while designing such systems is to achieve short ciphertext size, ideally independent of N. Recently, in a joint work with Venkata Koppula and Brent Waters, we built the first fully collusion resistant compact TT scheme provably secure under the learning with errors (LWE) assumption. A vital component in our system was a new form of functional encryption (FE) that we called Mixed FE.
Whilst this solves the piracy problem in broadcast systems when sender only broadcasts to all users, it does not allow for general broadcast along with providing tracing capability. Since we already have essentially optimal solutions to BE under bilinear maps, a natural question is whether the recent developments in TT could be combined with optimal BE systems to construct more general broadcast and trace systems. In this talk, I'll show that by a careful combination of LWE and bilinear maps we can improve the prior best construction of broadcast and trace (under standard assumptions) by Boneh and Waters. Central to this result is an augmented variant of Mixed FE, that we call Broadcast Mixed FE.
Finally, I also describe an extension of regular TT systems in which the user keys are embedded with polynomial length identities that can be extracted by the tracing algorithm. This also builds upon the framework of Mixed FE, thereby showcasing the applicability of Mixed FE in broader tracing scenarios.
Based on joint works with Venkata Koppula, Willy Quach, Brent Waters, and Daniel Wichs.