Watermarking schemes for PRFs and public-key primitives

Abstract

Watermarking is used to confirm the ownership of a program and authenticate softwares. Watermarking a program is to embed a “mark” or a message into the program satisfying that (i) the watermarked program is almost identical to the original program (“functionality-preserving”); (ii) it is hard to remove the “mark” unless the watermarked program is damaged heavily (“unremovability”); (iii) it is infeasible to forge a watermarked scheme which behaves differently from other watermarked programs (“unforgeability”). In this thesis, four watermarking schemes for different cryptographic primitives are proposed. The first one is to watermark signatures. The constructed signature can be watermarked securely in the symmetric-key setting with constraints hidden. Moreover, the signature is not required to prove secure under a certain specific proof technique. The second one is to watermark attribute-based encryptions (ABEs). Due to the difficulties of making extraction or marking algorithms public, the watermarkable ABE in the thesis is valuable with a public extraction. The novelty is a combination of a relaxed watermarking definition and a special cryptographic component called identity-based encryptions (IBE). This leads to a watermarking scheme for ABEs which possesses resistance to fully collusion attacks, secret marking and public extraction. Another advantage is that the security proof is much concise. The third one is to watermark distributed pseudorandom functions (DPRFs). Technically, a translucent constrained DPRF (TDF) is constructed under standard lattice assumption. Following the same spirit as Kim et al., a watermarking scheme for TDFs is constructed and proven that the watermarking scheme satisfies both the properties of unremovability and unforgeability. Such a watermarking scheme for DPRFs can be applied to watermark a distributed MAC scheme, a distributed symmetric-key encryption scheme, and so on. The fourth one is a watermarking scheme for PRFs in a secret-key setting under standard assumptions. A novel property of the scheme is about supporting hierarchical watermarking which is discussed for the first time.