## Software WatermarkingA 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. In this project, we study and propose new constructions for watermarking cryptographic functionalities. ## Watermarking PRFs from Lattices: Stronger Security via Extractable PRFs
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 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
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
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.
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
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 intuitively seem more challenging than watermarking PRFs, our constructions only rely on simple assumptions. Our watermarkable signature scheme can be built from the minimal assumption of one-way functions while our watermarkable public-key encryption scheme can be built from most standard algebraic assumptions that imply public-key encryption (e.g., factoring, discrete log, or lattice assumptions). Our schemes also satisfy a number of appealing properties: public marking, public mark-extraction, and collusion resistance. Our schemes are the first to simultaneously achieve all of these properties. The key enabler of our new constructions is a relaxed notion of
functionality-preserving. While traditionally, we require that a marked
program (approximately) preserve the
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} } ## Constraining Pseudorandom Functions Privately
Abstract:
In a constrained pseudorandom function (PRF), the master secret key can be
used to derive constrained keys, where each constrained key 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 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.
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} } |