Introduced in [CG24], pseudorandom error-correcting codes (PRCs) are a new cryptographic primitive with applications in watermarking generative AI models. These are codes where a collection of polynomially many codewords is computationally indistinguishable from random, except to individuals with the decoding key. In this work, we examine the assumptions under which PRCs with robustness to a constant error rate exist. 1. We show that if both the planted hyperloop assumption...

We propose waterlogs, a new direction to detect and trace synthetic text outputs from large language models based on transparency logs. Waterlogs offer major categorical advantages over watermarking: it (1) allows for the inclusion of arbitrary metadata to facilitate tracing, (2) is publicly verifiable by third parties, and (3) operates in a distributed manner while remaining robust and efficient. Waterlogs rely on a verifiable Hamming distance index, a novel data structure that we...

Motivated by the problem of detecting AI-generated text, we consider the problem of watermarking the output of language models with provable guarantees. We aim for watermarks which satisfy: (a) undetectability, a cryptographic notion introduced by Christ, Gunn & Zamir (2024) which stipulates that it is computationally hard to distinguish watermarked language model outputs from the model's actual output distribution; and (b) robustness to channels which introduce a constant fraction of...

The rise of Generative AI (GenAI) brings about transformative potential across sectors, but its dual-use nature also amplifies risks. Governments globally are grappling with the challenge of regulating GenAI, balancing innovation against safety. China, the United States (US), and the European Union (EU) are at the forefront with initiatives like the Management of Algorithmic Recommendations, the Executive Order, and the AI Act, respectively. However, the rapid evolution of GenAI capabilities...

We study watermarking schemes for language models with provable guarantees. As we show, prior works offer no robustness guarantees against adaptive prompting: when a user queries a language model more than once, as even benign users do. And with just a single exception (Christ and Gunn, 2024), prior works are restricted to zero-bit watermarking: machine-generated text can be detected as such, but no additional information can be extracted from the watermark. Unfortunately, merely detecting...

A verifiable delay function $\texttt{VDF}(x,T)\rightarrow (y,\pi)$ maps an input $x$ and time parameter $T$ to an output $y$ together with an efficiently verifiable proof $\pi$ certifying that $y$ was correctly computed. The function runs in $T$ sequential steps, and it should not be possible to compute $y$ much faster than that. The only known practical VDFs use sequential squaring in groups of unknown order as the sequential function, i.e., $y=x^{2^T}$. There are two constructions for...

We construct pseudorandom error-correcting codes (or simply pseudorandom codes), which are error-correcting codes with the property that any polynomial number of codewords are pseudorandom to any computationally-bounded adversary. Efficient decoding of corrupted codewords is possible with the help of a decoding key. We build pseudorandom codes that are robust to substitution and deletion errors, where pseudorandomness rests on standard cryptographic assumptions. Specifically,...

Watermarking generative models consists of planting a statistical signal (watermark) in a model’s output so that it can be later verified that the output was generated by the given model. A strong watermarking scheme satisfies the property that a computationally bounded attacker cannot erase the watermark without causing significant quality degradation. In this paper, we study the (im)possibility of strong watermarking schemes. We prove that, under well-specified and natural assumptions,...

We present a highly detectable, trustless watermarking scheme for LLMs: the detection algorithm contains no secret information, and it is executable by anyone. We embed a publicly-verifiable cryptographic signature into LLM output using rejection sampling. We prove that our scheme is cryptographically correct, sound, and distortion-free. We make novel uses of error-correction techniques to overcome periods of low entropy, a barrier for all prior watermarking schemes. We implement our scheme...

Recent advances in the capabilities of large language models such as GPT-4 have spurred increasing concern about our ability to detect AI-generated text. Prior works have suggested methods of embedding watermarks in model outputs, by $\textit{noticeably}$ altering the output distribution. We ask: Is it possible to introduce a watermark without incurring $\textit{any detectable}$ change to the output distribution? To this end we introduce a cryptographically-inspired notion of undetectable...

We put forth a new paradigm for program obfuscation, where obfuscated programs are endowed with proofs of ``well-formedness.'' In addition to asserting existence of an underlying plaintext program with an attested structure and functionality, these proofs also prevent mauling attacks, whereby an adversary surreptitiously creates an obfuscated program based on secrets which are embedded in a given obfuscated program. We call this new guarantee Chosen Obfuscation Attack (COA) security....

Numerous security vulnerability assessment techniques urge precise and fast finite state machines (FSMs) extraction from the design under evaluation. Sequential logic locking, watermark insertion, fault-injection assessment of a System-ona- Chip (SoC) control flow, information leakage assessment, and reverse engineering at gate-level abstraction, to name a few, require precise FSM extraction from the synthesized netlist of the design. Unfortunately, no reliable solutions are currently...

At the early stage of the design process, many security vulnerability assessment solutions require fast and precise extraction of the finite state machines (FSMs) present in the register-transfer level (RTL) description of the design. FSMs should be accurately extracted for watermark insertion, fault injection assessment of control paths in a system-on-chip (SoC), information leakage assessment, control-flow reverse engineering in RTL abstraction, logic obfuscation, etc. However, it is quite...

Copy-protection is the task of encoding a program into a quantum state to prevent illegal duplications. A line of recent works studied copy-protection schemes under ``1 -> 2 attacks'': the adversary receiving one program copy can not produce two valid copies. However, under most circumstances, vendors need to sell more than one copy of a program and still ensure that no duplicates can be generated. In this work, we initiate the study of collusion resistant copy-protection in the plain model....

The current state of the art in watermarked public-key encryption schemes under standard cryptographic assumptions suggests that extracting the embedded message requires either linear time in the number of marked keys or the a-priori knowledge of the marked key employed in the decoder. We present the first scheme that obviates these restrictions in the secret-key marking model, i.e., the setting where extraction is performed using a private extraction key. Our construction offers constant...

A software watermarking scheme can embed a message into a program while preserving its functionality. The embedded message can be extracted later by an extraction algorithm, and no one could remove it without significantly changing the functionality of the program. A watermarking scheme is public key if neither the marking procedure nor the extraction procedure needs a watermarking secret key. Prior constructions of watermarking schemes mainly focus on watermarking pseudorandom functions...

We initiate the study of software watermarking against quantum adversaries. A quantum adversary generates a quantum state as a pirate software that potentially removes an embedded message from a classical marked software. Extracting an embedded message from quantum pirate software is difficult since measurement could irreversibly alter the quantum state. In software watermarking against classical adversaries, a message extraction algorithm crucially uses the (input-output) behavior of a...

Intellectual property (IP) cores are essential to creating modern system-on-chips (SoCs). Protecting the IPs deployed in modern SoCs has become more difficult as the IP houses have been established across the globe over the past three decades. The threat posed by IP piracy and overuse has been a topic of research for the past decade or so and has led to creation of a field called watermarking. IP watermarking aims of detecting unauthorized IP usage by embedding excess, nonfunctional...

A software watermarking scheme enables one to embed a ``mark " (i.e., a message) into a program without significantly changing the functionality. Moreover, any removal of the watermark from a marked program is futile without significantly changing the functionality of the program. At present, the construction of software watermarking mainly focuses on watermarking pseudorandom functions (PRFs), watermarking public key encryption, watermarking signature, etc. In this work, we construct new...

An information escrow (IE) service allows its users to encrypt a message such that the message is unlocked only when a user-specified condition is satisfied. Its instantiations include timed-release encryption and allegation escrows with applications ranging from e-auctions to the #metoo movement. The proposed IE systems typically employ threshold cryptography towards mitigating the single-point-of-failure problem. Here, a set of escrow agents securely realize the IE functionality as long as...

Quantum copy protection uses the unclonability of quantum states to construct quantum software that provably cannot be pirated. Copy protection would be immensely useful, but unfortunately little is known about how to achieve it in general. In this work, we make progress on this goal, by giving the following results: –We show how to copy protect any program that cannot be learned from its input/output behavior, relative to a classical oracle. This improves on Aaronson [CCC’09], which ...

Program watermarking enables users to embed an arbitrary string called a mark into a program while preserving the functionality of the program. Adversaries cannot remove the mark without destroying the functionality. Although there exist generic constructions of watermarking schemes for public-key cryptographic (PKC) primitives, those schemes are constructed from scratch and not efficient. In this work, we present a general framework to equip a broad class of PKC primitives with an...

Puncturable encryption (PE), proposed by Green and Miers at IEEE S&P 2015, is a kind of public key encryption that allows recipients to revoke individual messages by repeatedly updating decryption keys without communicating with senders. PE is an essential tool for constructing many interesting applications, such as asynchronous messaging systems, forward-secret zero round-trip time protocols, public-key watermarking schemes and forward-secret proxy re-encryptions. This paper revisits PEs...

A software watermarking scheme can embed a message into a program without significantly changing its functionality. Moreover, any attempt to remove the embedded message in a marked program will substantially change the functionality of the program. Prior constructions of watermarking schemes focus on watermarking cryptographic functions, such as pseudorandom function (PRF), public key encryption, etc. A natural security requirement for watermarking schemes is collusion resistance, where the...

We introduce a new primitive named Delay Encryption, and give an efficient instantation based on isogenies of supersingular curves and pairings. Delay Encryption is related to Time-lock Puzzles and Verifiable Delay Functions, and can be roughly described as ``time-lock identity based encryption''. It has several applications in distributed protocols, such as sealed bid Vickrey auctions and electronic voting. We give an instantiation of Delay Encryption by modifying Boneh and Frankiln's IBE...

Software watermarking schemes allow a user to embed an identifier into a piece of code such that the resulting program is nearly functionally-equivalent to the original program, and yet, it is difficult to remove the identifier without destroying the functionality of the program. Such schemes are often considered for proving software ownership or for digital rights management. Existing constructions of watermarking have focused primarily on watermarking pseudorandom functions (PRFs). In...

The internet has the main advantage of transparent and sharing, but on the other hand, it has a disadvantage that digital contents are not protected. Due to the online environment, it is not easy to achieve a well protected Digital Rights Management System. Any digital content that is freely allowed to spread online have zero value. The content provider only gets a one-time profit when they upload their work to a platform and transfer the right of the production to the platform. Now the...

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...

This work studies the problem of automatically penalizing intentional or unintentional data breach (APB) by a receiver/custodian receiving confidential data from a sender. We solve this problem for multimedia data by augmenting a blockchain on-chain smart contract between the sender and receiver with an off-chain cryptographic protocol, such that any significant data breach from the receiver is penalized through a monetary loss. Towards achieving the goal, we develop a natural extension of...

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...

A software watermarking scheme can embed some information called a mark into a program while preserving its functionality. No adversary can remove the mark without damaging the functionality of the program. Cohen et al. (STOC '16) gave the first positive results for watermarking, showing how to watermark certain pseudorandom function (PRF) families using indistinguishability obfuscation (iO). Their scheme has a secret marking procedure to embed marks in programs and a public extraction...

Deep Learning (DL) models have caused a paradigm shift in our ability to comprehend raw data in various important fields, ranging from intelligence warfare and healthcare to autonomous transportation and automated manufacturing. A practical concern, in the rush to adopt DL models as a service, is protecting the models against Intellectual Property (IP) infringement. The DL models are commonly built by allocating significant computational resources that process vast amounts of proprietary...

A cryptographic watermarking scheme embeds a message into a program while preserving its functionality. Recently, a number of watermarking schemes have been proposed, which are proven secure in the sense that given one marked program, any attempt to remove the embedded message will substantially change its functionality. In this paper, we formally initiate the study of collusion attacks for watermarking schemes, where the attacker’s goal is to remove the embedded messages given multiple...

Opaque predicates are a commonly used technique in program obfuscation, intended to add complexity to control flow and to insert dummy code or watermarks. However, there are many attacks known to detect opaque predicates and remove dummy code. We survey these attacks and argue that many types of programs cannot be securely obfuscated using opaque predicates. In particular we explain that most previous works on control flow obfuscation have introduced predicates that are easily distinguished...

A watermarking scheme for a public-key cryptographic functionality enables the embedding of a mark in the instance of the secret-key algorithm such that the functionality of the original scheme is maintained, while it is infeasible for an adversary to remove the mark (unremovability) or mark a fresh object without the marking key (unforgeability). Cohen et al. [STOC'16] has provided constructions for watermarking arbitrary cryptographic functionalities; the resulting schemes rely on...

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 indistinguishability obfuscation. Notably, in their constructions, the watermark remains intact even against arbitrary...

Constraint-hiding constrained PRFs (CHCPRFs), initially studied by Boneh, Lewi, and Wu [PKC 2017], are constrained PRFs where the constrained key hides the description of the constraint. Envisioned with powerful applications such as searchable encryption, private-detectable watermarking, and symmetric deniable encryption, the only known candidates of CHCPRFs are based on indistinguishability obfuscation or multilinear maps with strong security properties. In this paper, we construct CHCPRFs...

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...

A watermarking scheme for programs embeds some information called a mark into a program while preserving its functionality. No adversary can remove the mark without damaging the functionality of the program. In this work, we study the problem of watermarking various cryptographic programs such as pseudorandom function (PRF) evaluation, decryption, and signing. For example, given a PRF F, we create a marked program C~ that evaluates F(). An adversary that gets C~ cannot come up with any...

Software Watermarking is the process of transforming a program into a functionally equivalent ``marked'' program in such a way that it is computationally hard to remove the mark without destroying functionality. Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang (CRYPTO 2001) defined software watermarking and showed that the existence of indistinguishability obfuscation implies that software watermarking is impossible. Given the recent candidate constructions of...

A watermarking scheme for programs embeds some information called a mark into a program while preserving its functionality. No adversary can remove the mark without damaging the functionality of the program. In this work, we study the problem of watermarking various cryptographic programs such as pseudorandom function (PRF) evaluation, decryption, and signing. For example, given a PRF key $K$, we create a marked program $\widetilde{C}$ that evaluates the PRF $F(K,\cdot)$. An adversary that...

The topic of this paper is collusion resistant watermarking, a.k.a. traitor tracing, in particular bias-based traitor tracing codes as introduced by G.Tardos in 2003. The past years have seen an ongoing effort to construct efficient high-performance decoders for these codes. In this paper we construct a score system from the Neyman-Pearson hypothesis test (which is known to be the most powerful test possible) into which we feed all the evidence available to the tracer, in particular the...

We introduce a notion of watermarking for cryptographic functions and propose a concrete scheme for watermarking cryptographic functions. Informally speaking, a digital watermarking scheme for cryptographic functions embeds information, called a \textit{mark}, into functions such as one-way functions and decryption functions of public-key encryption. There are two basic requirements for watermarking schemes. (1) A mark-embedded function must be functionally equivalent to the original...

The protection of intelligent property (IP) is a challenging task, especially in secured embedded systems where program code that is supposed to be a plagiarism cannot be simply read-out for further inspection. This is even more aggravated if the original source code was modified to prevent comparisons of any kind. For instance, watermarks that are actually hidden in the code are at risk to be rendered useless if the attacker has full access to the original code and some knowledge about the...

Forensic watermarking is the application of digital watermarks for the purpose of tracing unauthorized redistribution of content. The most powerful type of attack on watermarks is the collusion attack, in which multiple users compare their differently watermarked versions of the same content. Collusion-resistant codes have been developed against these attacks. One of the most famous such codes is the Tardos code. It has the asymptotically optimal property that it can resist c attackers with...

We investigate False Positive (FP) accusation probabilities for q-ary Tardos codes in the Restricted Digit Model. We employ a computation method recently introduced by us, to which we refer as Convolution and Series Expansion (CSE). We present a comparison of several collusion attacks on q-ary codes: majority voting, minority voting, Interleaving, $\tilde\mu$-minimizing and Random Symbol (the q-ary equivalent of the Coin Flip strategy). The comparison is made by looking at the FP rate at...

The Tardos code is a much studied collusion-resistant fingerprinting code, with the special property that it has asymptotically optimal length $m\propto c_0^2$, where $c_0$ is the number of colluders. In this paper we give alternative security proofs for the Tardos code, working with the assumption that the strongest coalition strategy is position-independent. We employ the Bernstein inequality and Bennett inequality instead of the typically used Markov inequality. This proof technique...

We study the channel capacity of $q$-ary fingerprinting in the limit of large attacker coalitions. We extend known results by considering the Combined Digit Model, an attacker model that captures signal processing attacks such as averaging and noise addition. For $q=2$ we give results for various attack parameter settings. For $q\geq 3$ we present the relevant equations without providing a solution. We show how the channel capacity in the Restricted Digit Model is obtained as a limiting case...

We study the probability distribution of user accusations in the q-ary Tardos fingerprinting system under the Marking Assumption, in the restricted digit model. In particular, we look at the applicability of the so-called Gaussian approximation, which states that accusation probabilities tend to the normal distribution when the fingerprinting code is long. We introduce a novel parametrization of the attack strategy which enables a significant speedup of numerical evaluations. We set up a...

We propose a new encryption scheme that supports joint fingerprinting and decryption. The scheme is remarkably resistant to known-plaintext attack and collusion attack (e.g. average attack or other linear combination attack) on keys. Interestingly, the security of our scheme is relied on a lattice problem: Given a collection of random lattice points generated from a short basis of a lattice, find the short basis. The scheme can be used as a traitor-tracing scheme or a buyer-seller...

Codes with the \emph{Identifiable Parent Property} (IPP) have been studied in the context of traitor tracing; such codes can be used to enable a data supplier to determine the origin of pirated data. We consider an analogous property for a set of binary strings $S$: if a new string $\tau$ is formed by concatenating substrings of members of $S$, we should be able to identify at least one original string which must have been used to generate $\tau$. We prove upper and lower bounds for the size...

Traitor tracing schemes are cryptographically secure broadcast methods that allow identification of conspirators: if a pirate key is generated by $k$ traitors out of a static set of $\ell$ legitimate users, then all traitors can be identified given the pirate key. In this paper we address three practicality and security issues of the Boneh-Franklin traitor-tracing scheme. In the first place, without changing the original scheme, we modify its tracing procedure in the non-black-box model such...

In this paper a new efficient public key cryptosystem usable for both encryption and digital signatures is presented. Due to its simple structure this public key cipher can be implemented easily in every software or hardware device, making the cryptosystem available for circumstances where the implementation of an alternative like RSA, El Gamal / Diffie - Hellmann, etc. is too complicated. Furthermore the construction on the closest and shortest vector problem using a new homomorph...

In this paper, we investigate the problem of how to prove the authorship of textual documents. First we define the basic functionalities of an authorship proof scheme (APS) based on natural language watermarking, and identify two essential security requirements for an APS to be secure against various attacks. We review existing natural language watermarking schemes, and we propose two new schemes with improved security.

Fingerprinting provides a means of tracing unauthorized redistribution of digital data by individually marking each authorized copy with a personalized serial number. In order to prevent a group of users from collectively escaping identification, collusion-secure fingerprinting codes have been proposed. In this paper, we introduce a new construction of a collusion-secure fingerprinting code which is similar to a recent construction by Tardos but achieves shorter code lengths and allows for...

In 2005, Hwang et al. [17] proposed a time-stamping protocol for digit watermarking. They claimed that their scheme is secure against attacks. However, in this article, we will show that their scheme is not secure enough for that when the owner of the image sends both the encrypted session key and image to the TSS, the attacker can intercept these transmitted data. Then, he can launch an off-line attack to analyze these intercepted data. We will describe the attacker’s action in this...

The informal goal of a watermarking scheme is to ``mark'' a digital object, such as a picture or video, in such a way that it is difficult for an adversary to remove the mark without destroying the content of the object. Although there has been considerable work proposing and breaking watermarking schemes, there has been little attention given to the formal security goals of such a scheme. In this work, we provide a new complexity-theoretic definition of security for watermarking schemes. ...

Traitor tracing schemes are used to fight piracy when distributing securely some data to multiple authorized receivers: if some receivers collude and share their decryption keys to build some pirate decoder, a tracing procedure should be able to find at least one of these ``traitors'' from the pirate decoder. In this paper, we consider powerful pirate decoders, which may sometimes refuse to decrypt, or may try to detect when the tracing procedure is running. Most known traitor tracing...

Although many watermarking schemes consider the case of universal verifiability, it is undesirable in some applications. Designated verification is a possible solution for this problem. Watermarking scheme with (non-interactive) designated verification through non-invertible schemes was proposed by Lee et al in 2003, to resolve multiple watermarking problem. Yoo et al [14] proposed a very similar watermarking scheme. In this paper, we propose a cryptanalytic attack on both of these schemes...

The recent advances in multimedia technology have made the manipulation of digital images, videos or audio files easy. On the one hand the broad availability of these new capabilities enabled numerous new applications. On the other hand, for the same reasons, digital media can easily be forged by almost anyone. To counteract this risk, fragile watermarks were proposed to protect the integrity and authenticity of digital multimedia objects. Traditional watermarking schemes employ...

The paper gives an upper bound on the size of a $q$-ary code of length $n$ that has the $k$-identifiable parent property. One consequence of this bound is that the optimal rate of such a code is determined in many cases when $q\rightarrow\infty$ with $k$ and $n$ fixed.

Informally, an {\em obfuscator} $O$ is an (efficient, probabilistic) ``compiler'' that takes as input a program (or circuit) $P$ and produces a new program $O(P)$ that has the same functionality as $P$ yet is ``unintelligible'' in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice's theorem. Most of these applications are...

The moduli used in RSA (see \cite{rsa}) can be generated by many different sources. The generator of that modulus knows its factorization. They have the ability to forge signatures or break any system based on this moduli. If a moduli and the RSA parameters associated with it were generated by a reputable source, the system would have higher value than if the parameters were generated by an unknown entity. An RSA modulus is digitally marked, or digitally trade marked, if the generator and...

TaKE cryptography offers subliminal marking of a digital stream so that any tampering, induces an unacceptable distortion of the primary information. Encrypted audio and video streams are decrypted by one key to the original content (e.g. music), and through another key to the digital watermark (e.g. name of legitimate user). Unlike the prevailing methods which are based on distorting the protected contents, or locking it through a digital signature, TaKE -- Tailored Key Encryption --...