We show the following results:

• The post-quantum equivalence of indisitnguishability obfuscation and differing inputs obfuscation in the restricted setting where the outputs differ on at most a polynomial number of points. Our result handles the case where the auxiliary input may contain a quantum state; previous results could only handle classical auxiliary input.

• Bounded collusion traitor tracing from general public key encryption, where the decoder is allowed to contain a quantum state. The parameters of the scheme grow polynomially in the collusion bound.

• Collusion-resistant traitor tracing with constant-size ciphertexts from general public key encryption, again for quantum state decoders. The public key and secret keys grow polynomially in the number of users.

• Traitor tracing with embedded identities in the keys, again for quantum state decoders, under a variety of different assumptions with different parameter size trade-offs.

Traitor tracing and differing inputs obfuscation with quantum decoders / auxiliary input arises naturally when considering the post-quantum security of these primitives. We obtain our results by abstracting out a core algorithmic model, which we call the Back One Step (BOS) model. We prove a general theorem, reducing many quantum results including ours to designing \emph{classical} algorithms in the BOS model. We then provide simple algorithms for the particular instances studied in this work.

@inproceedings{C:Zhandry23,
  author = {Mark Zhandry},
  title = {Tracing Quantum State Distinguishers via Backtracking},
  booktitle =  {CRYPTO 2023},
  year = {2023}
}

Traitor tracing aims to identify the source of leaked decryption keys. Since the "traitor" can try to hide their key within obfuscated code in order to evade tracing, the tracing algorithm should work for general, potentially obfuscated, decoder programs. In the setting of such general decoder programs, prior work uses black box tracing: the tracing algorithm ignores the implementation of the decoder, and instead traces just by making queries to the decoder and observing the outputs.

We observe that, in some settings, such black box tracing leads to consistency and user privacy issues. On the other hand, these issues do not appear inherent to white box tracing, where the tracing algorithm actually inspects the decoder implementation. We therefore develop new white box traitor tracing schemes providing consistency and/or privacy. Our schemes can be instantiated under various assumptions ranging from public key encryption and NIZKs to indistinguishability obfuscation, with different trade-offs. To the best of our knowledge, ours is the first work to consider white box tracing in the general decoder setting.

@inproceedings{C:Zhandry21,
    author =        {Mark Zhandry},
    booktitle =     {CRYPTO~2021, Part~IV},
    editor =        {Tal Malkin and Chris Peikert},
    month =         aug,
    pages =         {303--333},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {White Box Traitor Tracing},
    volume =        {12828},
    year =          {2021}
}

We explore the problem of traitor tracing where the pirate decoder can contain a quantum state. Our main results include:

• We show how to overcome numerous definitional challenges to give a meaningful notion of tracing for quantum decoders

• We give negative results, demonstrating barriers to adapting classical tracing algorithms to the quantum decoder setting.

• On the other hand, we show how to trace quantum decoders in the setting of (public key) private linear broadcast encryption, capturing a common approach to traitor tracing.

@inproceedings{TCC:Zhandry20,
    author =        {Mark Zhandry},
    booktitle =     {TCC~2020, Part~III},
    editor =        {Rafael Pass and Krzysztof Pietrzak},
    month =         nov,
    pages =         {61--91},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {{Schr{\"o}dinger}'s Pirate: How to Trace a Quantum
                     Decoder},
    volume =        {12552},
    year =          {2020}
}

The best existing pairing-based traitor tracing schemes have O(√N)-sized parameters, which has stood since 2006. This intuitively seems to be consistent with the fact that pairings allow for degree-2 computations, yielding a quadratic compression.

In this work, we show that this intuition is false by building a tracing scheme from pairings with O(∛N)-sized parameters. We additionally give schemes with a variety of parameter size trade-offs, including a scheme with constant-size ciphertexts and public keys (but linear-sized secret keys). All of our schemes make black-box use of the pairings. We obtain our schemes by developing a number of new traitor tracing techniques, giving the first significant parameter improvements in pairings-based traitor tracing in over a decade.

@inproceedings{C:Zhandry20,
    author =        {Mark Zhandry},
    booktitle =     {CRYPTO~2020, Part~I},
    editor =        {Daniele Micciancio and Thomas Ristenpart},
    month =         aug,
    pages =         {652--682},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {New Techniques for Traitor Tracing: Size {$N^{1/3}$}
                     and More from Pairings},
    volume =        {12170},
    year =          {2020}
}

Despite much study, the computational complexity of differential privacy remains poorly understood. In this paper we consider the computational complexity of accurately answering a family Q of statistical queries over a data universe X under differential privacy. A statistical query on a dataset D∈Xⁿ asks "what fraction of the elements of D satisfy a given predicate p on X?" Dwork et al. (STOC'09) and Boneh and Zhandry (CRYPTO'14) showed that if both Q and X are of polynomial size, then there is an efficient differentially private algorithm that accurately answers all the queries, and if both Q and X are exponential size, then under a plausible assumption, no efficient algorithm exists.

We show that, under the same assumption, if either the number of queries or the data universe is of exponential size, then there is no differentially private algorithm that answers all the queries. Specifically, we prove that if one-way functions and indistinguishability obfuscation exist, then:

• For every n, there is a family Q of O(n⁷) queries on a data universe X of size 2^d such that no poly(n,d) time differentially private algorithm takes a dataset D∈Xⁿ and outputs accurate answers to every query in Q.

•For every n, there is a family Q of 2^d queries on a data universe X of size O(n⁷) such that no poly(n,d) time differentially private algorithm takes a dataset D∈Xⁿ and outputs accurate answers to every query in Q.

In both cases, the result is nearly quantitatively tight, since there is an efficient differentially private algorithm that answers Ω(n²) queries on an exponential size data universe, and one that answers exponentially many queries on a data universe of size Ω(n²).

Our proofs build on the connection between hardness results in differential privacy and traitor-tracing schemes (Dwork et al., STOC'09; Ullman, STOC'13). We prove our hardness result for a polynomial size query set (resp., data universe) by showing that they follow from the existence of a special type of traitor-tracing scheme with very short ciphertexts (resp., secret keys), but very weak security guarantees, and then constructing such a scheme.

@inproceedings{TCC:KMUZ16,
    author =        {Lucas Kowalczyk and Tal Malkin and Jonathan Ullman and
                     Mark Zhandry},
    booktitle =     {TCC~2016-B, Part~I},
    editor =        {Martin Hirt and Adam D. Smith},
    month =         oct # {~/~} # nov,
    pages =         {659--689},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Strong Hardness of Privacy from Weak Traitor Tracing},
    volume =        {9985},
    year =          {2016}
}

In a traitor tracing scheme, each user is given a different decryption key. A content distributor can encrypt digital content using a public encryption key and each user in the system can decrypt it using her decryption key. Even if a coalition of users combines their decryption keys and constructs some "pirate decoder" that is capable of decrypting the content, there is a public tracing algorithm that is guaranteed to recover the identity of at least one of the users in the coalition given black-box access to such decoder.

In prior solutions, the users are indexed by numbers 1,…,N and the tracing algorithm recovers the index i of a user in a coalition. Such solutions implicitly require the content distributor to keep a record that associates each index i with the actual identifying information for the corresponding user (e.g., name, address, etc.) in order to ensure accountability. In this work, we construct traitor tracing schemes where all of the identifying information about the user can be embedded directly into the user's key and recovered by the tracing algorithm. In particular, the content distributor does not need to separately store any records about the users of the system, and honest users can even remain anonymous to the content distributor.

The main technical difficulty comes in designing tracing algorithms that can handle an exponentially large universe of possible identities, rather than just a polynomial set of indices i∈[N]. We solve this by abstracting out an interesting algorithmic problem that has surprising connections with seemingly unrelated areas in cryptography. We also extend our solution to a full "broadcast-trace-and-revoke" scheme in which the traced users can subsequently be revoked from the system. Depending on parameters, some of our schemes can be based only on the existence of public-key encryption while others rely on indistinguishability obfuscation.

@inproceedings{EC:NisWicZha16,
  author =        {Ryo Nishimaki and Daniel Wichs and Mark Zhandry},
  booktitle =     {EUROCRYPT~2016, Part~II},
  editor =        {Marc Fischlin and Jean-S{\'{e}}bastien Coron},
  month =         may,
  pages =         {388--419},
  publisher =     {Springer, Heidelberg},
  series =        {{LNCS}},
  title =         {Anonymous Traitor Tracing: How to Embed Arbitrary
                   Information in a Key},
  volume =        {9666},
  year =          {2016}
}

In this work, we show how to use indistinguishability obfuscation (iO) to build multiparty key exchange, efficient broadcast encryption, and efficient traitor tracing. Our schemes enjoy several interesting properties that have not been achievable before:

• Our multiparty non-interactive key exchange protocol does not require a trusted setup. Moreover, the size of the published value from each user is independent of the total number of users.

• Our broadcast encryption schemes support distributed setup, where users choose their own secret keys rather than be given secret keys by a trusted entity. The broadcast ciphertext size is independent of the number of users.

• Our traitor tracing system is fully collusion resistant with short ciphertexts, secret keys, and public key. Ciphertext size is logarithmic in the number of users and secret key size is independent of the number of users. Our public key size is polylogarithmic in the number of users. The recent functional encryption system of Garg, Gentry, Halevi, Raykova, Sahai, and Waters also leads to a traitor tracing scheme with similar ciphertext and secret key size, but the construction in this paper is simpler and more direct. These constructions resolve an open problem relating to differential privacy.

• Generalizing our traitor tracing system gives a private broadcast encryption scheme (where broadcast ciphertexts reveal minimal information about the recipient set) with optimal size ciphertext.

Several of our proofs of security introduce new tools for proving security using indistinguishability obfuscation.

@inproceedings{C:BonZha14,
    author =        {Dan Boneh and Mark Zhandry},
    booktitle =     {CRYPTO~2014, Part~I},
    editor =        {Juan A. Garay and Rosario Gennaro},
    month =         aug,
    pages =         {480--499},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Multiparty Key Exchange, Efficient Traitor Tracing,
                     and More from Indistinguishability Obfuscation},
    volume =        {8616},
    year =          {2014}
}