Broadcast and Trace with N_e Ciphertext Size from Standard Assumptions

摘要

We construct a broadcast and trace scheme (also known as trace and revoke or broadcast, trace and revoke) with N users, where the ciphertext size can be made as low as 0(N~ε), for any arbitrarily small constant e > 0. This improves on the prior best construction of broadcast and trace under standard assumptions by Boneh and Waters (CCS '06), which had ciphertext size O(N~(1/2)). While that construction relied on bilinear maps, ours uses a combination of the learning with errors (LWE) assumption and bilinear maps. Recall that, in both broadcast encryption and traitor-tracing schemes, there is a collection of N users, each of which gets a different secret key skj. In broadcast encryption, it is possible to create ciphertexts targeted to a subset S C [A] of the users such that only those users can decrypt it correctly. In a traitor tracing scheme, if a subset of users gets together and creates a decoder box D that is capable of decrypting ciphertexts, then it is possible to trace at least one of the users responsible for creating D. A broadcast and trace scheme intertwines the two properties, in a way that results in more than just their union. In particular, it ensures that if a decoder D is able to decrypt ciphertexts targeted toward a set S of users, then it should be possible to trace one of the users in the set S responsible for creating D, even if other users outside of S also participated. As of recently, we have essentially optimal broadcast encryption (Boneh, Gentry, Waters CRYPTO '05) under bilinear maps and traitor tracing (Goyal, Koppula, Waters STOC T8) under LWE, where the ciphertext size is at most poly-logarithmic in N. The main contribution of our paper is to carefully combine LWE and bilinear-map based components, and get them to interact with each other, to achieve broadcast and trace.