Composability in Watermarking Schemes


Software watermarking allows for embedding a mark into a piece of code, such that any
attempt to remove the mark will render the code useless. Provably secure watermarking
schemes currently seems limited to programs computing various cryptographic
operations, such as evaluating pseudorandom functions (PRFs), signing messages, or
decrypting ciphertexts (the latter often going by the name "traitor tracing").
Moreover, each of these watermarking schemes has an adhoc construction of its own.
We observe, however, that many cryptographic objects are used as building blocks in larger protocols. We ask: just as we can compose building blocks to obtain larger protocols, can we compose watermarking schemes for the building blocks to obtain watermarking schemes for the larger protocols? We give an affirmative answer to this question, by precisely formulating a set of requirements that allow for composing watermarking schemes. We use our formulation to derive a number of applications.
@misc{TCC:LiuZha24,
author = {Jiahui Liu and Mark Zhandry}, booktitle = {TCC 2024}, title = {Composability in Watermarking Schemes}, year = {2024} }  
Optimal Traitor Tracing from Pairings


We use pairings over elliptic curves to give a collusionresistant traitor tracing
scheme where the sizes of public keys, secret keys, and ciphertexts are independent
of the number of users. Prior constructions from pairings had size
Ω(N^{1/3}). Our construction is nonblack box.
@misc{EPRINT:Zhandry24,
author = {Mark Zhandry}, title = {Optimal Traitor Tracing from Pairings}, howpublished = {Cryptology ePrint Archive, Paper 2024/867}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/867}}, url = {https://eprint.iacr.org/2024/867} }  
Tracing Quantum State Distinguishers via Backtracking


We show the following results:
• The postquantum 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. • Collusionresistant traitor tracing with constantsize 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 tradeoffs. Traitor tracing and differing inputs obfuscation with quantum decoders / auxiliary input arises naturally when considering the postquantum 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}, booktitle = {CRYPTO~2023, Part~V}, editor = {Helena Handschuh and Anna Lysyanskaya}, month = aug, pages = {336}, publisher = {Springer, Cham}, series = {{LNCS}}, title = {Tracing Quantum State Distinguishers via Backtracking}, volume = {14085}, year = {2023} }  
White Box Traitor Tracing


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 tradeoffs. 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 = {303333}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {White Box Traitor Tracing}, volume = {12828}, year = {2021} }  
Schrödinger's Pirate: How To Trace a Quantum Decoder


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 = {6191}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {{Schr{\"o}dinger}'s Pirate: How to Trace a Quantum Decoder}, volume = {12552}, year = {2020} }  
New Techniques for Traitor Tracing: Size N^{⅓} and More from Pairings


The best existing pairingbased 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 degree2 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 tradeoffs, including a scheme with constantsize ciphertexts and public keys (but linearsized secret keys). All of our schemes make blackbox use of the pairings. We obtain our schemes by developing a number of new traitor tracing techniques, giving the first significant parameter improvements in pairingsbased 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 = {652682}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {New Techniques for Traitor Tracing: Size {$N^{1/3}$} and More from Pairings}, volume = {12170}, year = {2020} }  
Strong Hardness of Privacy from Weak Traitor Tracing


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^{n} 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 oneway functions and indistinguishability obfuscation exist, then: • For every n, there is a family Q of O(n^{7}) 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^{n} 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^{7}) such that no poly(n,d) time differentially private algorithm takes a dataset D∈X^{n} 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^{2}) queries on an exponential size data universe, and one that answers exponentially many queries on a data universe of size Ω(n^{2}). Our proofs build on the connection between hardness results in differential privacy and traitortracing 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 traitortracing 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~2016B, Part~I}, editor = {Martin Hirt and Adam D. Smith}, month = oct # {~/~} # nov, pages = {659689}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Strong Hardness of Privacy from Weak Traitor Tracing}, volume = {9985}, year = {2016} }  
Anonymous Traitor Tracing: How to Embed Arbitrary Information in a Key


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 blackbox
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 "broadcasttraceandrevoke" 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 publickey 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 JeanS{\'{e}}bastien Coron}, month = may, pages = {388419}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Anonymous Traitor Tracing: How to Embed Arbitrary Information in a Key}, volume = {9666}, year = {2016} }  
Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation


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 noninteractive 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 = {480499}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation}, volume = {8616}, year = {2014} } 