Software watermarking schemes allow a user to embed an identifier into a piece of code such that the resulting program is nearly functionallyequivalent 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 this work, we revisit the definitional foundations of watermarking, and begin by highlighting a major flaw in existing security notions. Existing security notions for watermarking only require that the identifier be successfully extracted from programs that preserve the exact input/output behavior of the original program. In the context of PRFs, this means that an adversary that constructs a program which computes a quarter of the output bits of the PRF or that is able to distinguish the outputs of the PRF from random are considered to be outside the threat model. However, in any application (e.g., watermarking a decryption device or an authentication token) that relies on PRF security, an adversary that manages to predict a quarter of the bits or distinguishes the PRF outputs from random would be considered to have defeated the scheme. Thus, existing watermarking schemes provide very little security guarantee against realistic adversaries. None of the existing constructions of watermarkable PRFs would be able to extract the identifier from a program that only outputs a quarter of the bits of the PRF or one that perfectly distinguishes.
To address the shortcomings in existing watermarkable PRF definitions, we introduce a new primitive called a traceable PRF. Our definitions are inspired by similar definitions from publickey traitor tracing, and aim to capture a very robust set of adversaries: namely, any adversary that produces a useful distinguisher (i.e., a program that can break PRF security), can be traced to a specific identifier. We provide a general framework for constructing traceable PRFs via an intermediate primitive called private linear constrained PRFs. Finally, we show how to construct traceable PRFs from a similar set of assumptions previously used to realize software watermarking. Namely, we obtain a singlekey traceable PRF from standard lattice assumptions and a fully collusionresistant traceable PRF from indistinguishability obfuscation (together with injective oneway functions).
more »
« less
Traceable PRFs: Full Collusion Resistance and Active Security
The main goal of traceable cryptography is to protect against unauthorized redistribution of cryptographic functionalities. Such schemes provide a way to embed identities (i.e., a “mark”) within cryptographic objects (e.g., decryption keys in an encryption scheme, signing keys in a signature scheme). In turn, the tracing guarantee ensures that any “pirate device” that successfully replicates the underlying functionality can be successfully traced to the set of identities used to build the device.
In this work, we study traceable pseudorandom functions (PRFs). As PRFs are the workhorses of symmetric cryptography, traceable PRFs are useful for augmenting symmetric cryptographic primitives with strong traceable security guarantees. However, existing constructions of traceable PRFs either rely on strong notions like indistinguishability obfuscation or satisfy weak security guarantees like singlekey security (i.e., tracing only works against adversaries that possess a single marked key).
In this work, we show how to use fingerprinting codes to upgrade a singlekey traceable PRF into a fully collusion resistant traceable PRF, where security holds regardless of how many keys the adversary possesses. We additionally introduce a stronger notion of security where tracing security holds even against active adversaries that have oracle access to the tracing algorithm. In conjunction with known constructions of singlekey traceable PRFs, we obtain the first fully collusion resistant traceable PRF from standard lattice assumptions. Our traceable PRFs directly imply new latticebased secretkey traitor tracing schemes that are CCAsecure and where tracing security holds against active adversaries that have access to the tracing oracle.
more »
« less
 NSFPAR ID:
 10310225
 Date Published:
 Journal Name:
 International Conference on Practice and Theory of PublicKey Cryptography (PKC)
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Bhargavan, Karthikeyan ; Oswald, Elisabeth ; Prabhakaran, Manoj (Ed.)This paper gives the first definitions and constructions for incremental pseudorandom functions (IPRFs). The syntax is nonce based. (Algorithms are deterministic but may take as input a nonrepeating quantity called a nonce.) The design approach is modular. First, given a scheme secure only in the singledocument setting (there is just one document on which incremental updates are being performed) we show how to generically build a scheme that is secure in the more realistic multidocument setting (there are many documents, and they are simultaneously being incrementally updated). Then we give a general way to build an IPRF from (1) an incremental hash function with weak collision resistance properties and (2) a symmetric encryption scheme. (This adapts the classic CarterWegman paradigm used to build message authentication schemes in the nonincremental setting.) This leads to many particular IPRFs. Our work has both practical and theoretical motivation and value: Incremental PRFs bring the benefits of incrementality to new applications (such as incremental key derivation), and the movement from randomized or stateful schemes to nonce based ones, and from UF (unforgeability) to PRF security, bring incremental symmetric cryptography up to speed with the broader field of symmetric cryptography itself.more » « less

Functional Encryption is a powerful notion of encryption in which each decryption key is associated with a function such that decryption recovers the function evaluation . Informally, security states that a user with access to function keys (and so on) can only learn (and so on) but nothing more about the message. The system is said to be bounded collusion resistant if the security holds as long as an adversary gets access to at most function keys. A major drawback of such "statically" bounded collusion systems is that the collusion bound must be declared at setup time and is fixed for the entire lifetime of the system. We initiate the study of "dynamically" bounded collusion resistant functional encryption systems which provide more flexibility in terms of selecting the collusion bound, while reaping the benefits of statically bounded collusion FE systems (such as quantum resistance, simulation security, and general assumptions). Briefly, the virtues of a dynamically bounded scheme can be summarized as: (i) [Finegrained individualized selection.] It lets each encryptor select the collusion bound by weighing the tradeoff between performance overhead and the amount of collusion resilience. (ii) [Evolving encryption strategies.] Since the system is no longer tied to a single collusion bound, thus it allows to dynamically adjust the desired collusion resilience based on any number of evolving factors such as the age of the system, or a number of active users, etc. (iii) [Ease and simplicity of updatability.] None of the system parameters have to be updated when adjusting the collusion bound. That is, the same key can be used to decrypt ciphertexts for collusion bound as well as . We construct such a dynamically bounded functional encryption scheme for the class of all polynomialsize circuits under the general assumption of IdentityBased Encryption.more » « less

In a traitor tracing (TT) system for n users, every user has his/her own secret key. Content providers can encrypt messages using a public key, and each user can decrypt the ciphertext using his/her secret key. Suppose some of the n users collude to construct a pirate decoding box. Then the tracing scheme has a special algorithm, called 𝖳𝗋𝖺𝖼𝖾 , which can identify at least one of the secret keys used to construct the pirate decoding box. Traditionally, the trace algorithm output only the ‘index’ associated with the traitors. As a result, to use such systems, either a central master authority must map the indices to actual identities, or there should be a public mapping of indices to identities. Both these options are problematic, especially if we need public tracing with anonymity of users. Nishimaki, Wichs, and Zhandry (NWZ) [Eurocrypt 2016] addressed this problem by constructing a traitor tracing scheme where the identities of users are embedded in the secret keys, and the trace algorithm, given a decoding box D, can recover the entire identities of the traitors. We call such schemes ‘Embedded Identity Traitor Tracing’ schemes. NWZ constructed such schemes based on adaptively secure functional encryption (FE). Currently, the only known constructions of FE schemes are based on nonstandard assumptions such as multilinear maps and iO. In this work, we study the problem of embedded identities TT based on standard assumptions. We provide a range of constructions based on different assumptions such as public key encryption (PKE), bilinear maps and the Learning with Errors (LWE) assumption. The different constructions have different efficiency trade offs. In our PKE based construction, the ciphertext size grows linearly with the number of users; the bilinear maps based construction has sublinear (𝑛√ ) sized ciphertexts. Both these schemes have public tracing. The LWE based scheme is a private tracing scheme with optimal ciphertexts (i.e., log(𝑛)). Finally, we also present other notions of traitor tracing, and discuss how they can be build in a generic manner from our base embedded identity TT scheme.more » « less

Handschuh, Helena ; Lysyanskaya, Anna (Ed.)In Internet security protocols including TLS 1.3, KEMTLS, MLS and Noise, HMAC is being assumed to be a dualPRF, meaning a PRF not only when keyed conventionally (through its first input), but also when "swapped'' and keyed (unconventionally) through its second (message) input. We give the first indepth analysis of the dualPRF assumption on HMAC. For the swap case, we note that security does not hold in general, but completely characterize when it does; we show that HMAC is swapPRF secure if and only if keys are restricted to sets satisfying a condition called feasibility, that we give, and that holds in applications. The sufficiency is shown by proof and the necessity by attacks. For the conventional PRF case, we fill a gap in the literature by proving PRF security of HMAC for keys of arbitrary length. Our proofs are in the standard model, make assumptions only on the compression function underlying the hash function, and give good bounds in the multi user setting. The positive results are strengthened through achieving a new notion of variable keylength PRF security that guarantees security even if different users use keys of different lengths, as happens in practice.more » « less