Software Watermarking and Traitor Tracing

A software watermarking scheme enables a user to embed a tag (e.g., a developer's name or a serial number) into a program while preserving the program's functionality. Moreover, it should be difficult to remove the watermark from the resulting program without destroying its functionality. Closely related is the notion of traitor tracing, which are cryptographic schemes that enable users or authorities to trace the source of compromised cryptographic keys and programs. Both of these primitives are useful for protecting against unauthorized use or redistribution of digital content. In this project, we study and propose new constructions of these primitives.

Watermarking PRFs from Lattices: Stronger Security via Extractable PRFs

Contributors: Sam Kim and David J. Wu

Abstract:

A software watermarking scheme enables one to embed a “mark” (i.e., a message) within a program while preserving the program's functionality. Moreover, there is an extraction algorithm that recovers an embedded message from a program. The main security goal is that it should be difficult to remove the watermark without destroying the functionality of the program. Existing constructions of watermarking focus on watermarking cryptographic functions like pseudorandom functions (PRFs); even in this setting, realizing watermarking from standard assumptions remains difficult. The first lattice-based construction of secret-key watermarking due to Kim and Wu (CRYPTO 2017) only ensures mark-unremovability against an adversary who does not have access to the mark-extraction oracle. The construction of Quach et al. (TCC 2018) achieves the stronger notion of mark-unremovability even if the adversary can make extraction queries, but has the drawback that the watermarking authority (who holds the watermarking secret key) can break pseudorandomness of all PRF keys in the family (including unmarked keys).

In this work, we construct new lattice-based secret-key watermarking schemes for PRFs that both provide unremovability against adversaries that have access to the mark-extraction oracle and offer a strong and meaningful notion of pseudorandomness even against the watermarking authority (i.e., the outputs of unmarked keys are pseudorandom almost everywhere). Moreover, security of several of our schemes can be based on the hardness of computing nearly polynomial approximations to worst-case lattice problems. This is a qualitatively weaker assumption than that needed for existing lattice-based constructions of watermarking (that support message-embedding), all of which require quasi-polynomial approximation factors. Our constructions rely on a new cryptographic primitive called an extractable PRF, which may be of independent interest.

Resources:

BibTeX:
@inproceedings{KW19,
  author     = {Sam Kim and David J. Wu},
  title      = {Watermarking {PRFs} from Lattices: Stronger Security via Extractable {PRFs}},
  booktitle  = {{CRYPTO}},
  year       = {2019}
}

Watermarking Cryptographic Functionalities from Standard Lattice Assumptions

Contributors: Sam Kim and David J. Wu

Abstract:

A software watermarking scheme allows one to embed a “mark” into a program without significantly altering the behavior of the program. Moreover, it should be difficult to remove the watermark without destroying the functionality of the program. Recently, Cohen et al. (STOC 2016) and Boneh et al. (PKC 2017) showed how to watermark cryptographic functions such as PRFs using the full power of general-purpose indistinguishability obfuscation. Notably, in their constructions, the watermark remains intact even against arbitrary removal strategies. A natural question is whether we can build watermarking schemes from standard assumptions that achieve this strong mark-unremovability property.

We give the first construction of a watermarkable family of PRFs that satisfy this strong mark-unremovability property from standard lattice assumptions (namely, the learning with errors (LWE) and the one-dimensional short integer solution (SIS) problems). As part of our construction, we introduce a new cryptographic primitive called a translucent PRF. Next, we give a concrete construction of a translucent PRF family from standard lattice assumptions. Finally, we show that using our new lattice-based translucent PRFs, we obtain the first watermarkable family of PRFs with strong unremovability against arbitrary strategies from standard assumptions.

Resources:

BibTeX:
@inproceedings{KW17,
  author     = {Sam Kim and David J. Wu},
  title      = {Watermarking Cryptographic Functionalities from Standard Lattice Assumptions},
  booktitle  = {{CRYPTO}},
  year       = {2017}
}

Watermarking Public-Key Cryptographic Primitives

Contributors: Rishab Goyal, Sam Kim, Nathan Manohar, Brent Waters, and David J. Wu

Abstract:

A software watermarking scheme enables users to embed a message or mark within a program while preserving its functionality. Moreover, it is difficult for an adversary to remove a watermark from a marked program without corrupting its behavior. Existing constructions of software watermarking from standard assumptions have focused exclusively on watermarking pseudorandom functions (PRFs).

In this work, we study watermarking public-key primitives such as the signing key of a digital signature scheme or the decryption key of a public-key (predicate) encryption scheme. While watermarking public-key primitives might seem more challenging than watermarking PRFs, we show how to construct watermarkable variants of these notions while only relying on standard, and oftentimes, minimal, assumptions. Our watermarkable signature scheme relies only on the minimal assumption that one-way functions exist and satisfies ideal properties such as public marking, public mark-extraction, and full collusion resistance. Our watermarkable public-key encryption schemes are built using techniques developed for the closely-related problem of traitor tracing. Notably, we obtain fully collusion resistant watermarkable attribute-based encryption in the private-key setting from the standard learning with errors assumption and a bounded collusion resistant watermarkable predicate encryption scheme with public mark-extraction and public marking from the minimal assumption that public-key encryption exists.

Resources:

BibTeX:
@inproceedings{GKMWW19,
  author     = {Rishab Goyal and Sam Kim and Nathan Manohar and Brent Waters and David J. Wu},
  title      = {Watermarking Public-Key Cryptographic Primitives},
  booktitle  = {{CRYPTO}},
  year       = {2019}
}

Collusion Resistant Trace-and-Revoke for Arbitrary Identities from Standard Assumptions

Contributors: Sam Kim and David J. Wu

Abstract:

A traitor tracing scheme is a multi-user public-key encryption scheme where each user in the system holds a decryption key that is associated with the user's identity. Using the public key, a content distributor can encrypt a message to all of the users in the system. At the same time, if a malicious group of users combine their respective decryption keys to build a “pirate decoder,” there is an efficient tracing algorithm that the content distributor can use to identify at least one of the keys used to construct the decoder. A trace-and-revoke scheme is an extension of a standard traitor tracing scheme where there is an additional key-revocation mechanism that the content distributor can use to disable the decryption capabilities of compromised keys.

Trace-and-revoke schemes are generally difficult to construct. Existing constructions from standard assumptions can only tolerate bounded collusions (i.e., there is an a priori bound on the number of keys an adversary obtains), have system parameters that scale exponentially in the bit-length of the identities, or satisfy weaker notions of traceability that are vulnerable to certain types of “pirate evolution” attacks. In this work, we provide the first construction of a trace-and-revoke scheme that is fully collusion resistant and capable of supporting arbitrary identities (i.e., the identities can be drawn from an exponential-size space). Our scheme supports public broadcast and secret tracing, and can be based on the sub-exponential hardness of the LWE problem (with a super-polynomial modulus-to-noise ratio). Our construction relies on a combination of both algebraic and combinatorial techniques for traitor tracing.

Resources:

BibTeX:
@inproceedings{KW19b,
  author = {Sam Kim and David J. Wu},
  title  = {Collusion Resistant Trace-and-Revoke for Arbitrary Identities from Standard Assumptions},
  misc   = {Full version available at \url{https://eprint.iacr.org/2019/984}},
  year   = {2019}
}

Constraining Pseudorandom Functions Privately

Contributors: Dan Boneh, Kevin Lewi, and David J. Wu

Abstract:

In a constrained pseudorandom function (PRF), the master secret key can be used to derive constrained keys, where each constrained key k is constrained with respect to some Boolean circuit C. A constrained key k can be used to evaluate the PRF on all inputs x for which C(x) = 1. In almost all existing constrained PRF constructions, the constrained key k reveals its constraint C.

In this paper we introduce the concept of private constrained PRFs, which are constrained PRFs with the additional property that a constrained key does not reveal its constraint. Our main notion of privacy captures the intuition that an adversary, given a constrained key k for one of two circuits C0 and C1, is unable to tell which circuit is associated with the key k. We show that constrained PRFs have natural applications to searchable symmetric encryption, cryptographic watermarking, and much more.

To construct private constrained PRFs we first demonstrate that our strongest notions of privacy and functionality can be achieved using indistinguishability obfuscation. Then, for our main constructions, we build private constrained PRFs for bit-fixing constraints and for puncturing constraints from concrete algebraic assumptions.

Resources:

BibTeX:
@inproceedings{BLW17,
  author    = {Dan Boneh and Kevin Lewi and David J. Wu},
  title     = {Constraining Pseudorandom Functions Privately},
  booktitle = {International Conference on Practice and Theory in Public-Key Cryptography ({PKC})},
  year      = {2017}
}