An Approach to Materialize Digital Fingerprinting Based on Proxy Signature Schemes

Jae-Gwi Choi
Dept. of Information Security, Graduate School, Pukyong Nat’l Univ.
599-1 Daeyeon-dong Nam-ku Busan, Korea.

Kouichi Sakurai
Dept. of Computer Science and Communication Engineering, Graduate School of Information Science and Electrical Engineering, Kyushu Univ.
6-10-1 Hakozaki Higashi-ku Fukuoka Japan.
Ji-Hwan Park
Dept. of Information Security, Graduate School, Pukyong Nat’l Univ
599-1 Daeyeon-dong Nam-ku Busan, Korea.


Protection of intellectual property in digital contents has been a subject of research for many years and led to the development of various techniques. A digital fingerprinting scheme is an important class of these techniques. The goal of fingerprinting scheme is to deter people from illegally redistributing digital data. But, the problem of known anonymous fingerprinting schemes is that, being based on computationally unspecified black boxes: secure multiparty computation or minimum disclosure proofs of knowledge or general zero-knowledge proof. Their complexity is much too high to be implementable in real application. Furthermore, buyers have a small memory and little computation capability relatively to merchants. Hence, we can conclude that fingerprinting scheme to be needed high complexity is not suited to the customer-centered commercial transaction. In this paper, we presented an anonymous fingerprinting which is efficient and feasible from a practical view. The basic primitive used is a proxy signature.


Anonymous fingerprinting scheme, proxy signatures, zero-knowledge proofs, secures multiparty computation.


Fingerprinting schemes are techniques applied to protect the copyright on digital goods. They applied to the merchants to identify the source of illegal redistribution. This is similar to digital watermarking, except that different information such as the user ID is embedded in each distributed digital contents. Thus it enables a merchant to trace the buyer of an illegally distributed digital good by providing each buyer with a slightly different version.

1.1 Problems of the previous works

An anonymous fingerprinting scheme has appeared as a technique for copyright protection that is compatible with buyer anonymity in electronic transactions. The idea is that the merchant can know neither the fingerprinted copy nor the buyer's identity. The constructions [1] applied general theorems like “every NP-language has a zero-knowledge proof system" without presenting explicit protocols. Recently, several studies on anonymous fingerprinting schemes enhance the functionally in various ways. The most of them rely either on secure multiparty computation [2] or on general zero-knowledge proofs and this protocols are embodied based on difficult problems is needed much computations such as discrete logarithm problem or graph isomorphic problem.

In general, the watermarked contents can be made in off-line, since every sold copy is the same. On the contrary, the buyer has to connect at the merchant’s server for buying digital contents in fingerprinting schemes, since every sold copy is slightly different from the original contents and unique to its buyer. Moreover, buyers’ memory and computation power are very small relatively to ones of the merchant. Thus we might conclude that fingerprinting schemes with high complexity are not suited to the real materialization. Of course, the schemes that are efficiently and completely specified from a computational point of view were proposed [3]. However, this approach also relies on an unspecified general zero-knowledge proof or has disadvantage that all buyers having bought a copy of digital contents have to participate in identification protocol to identify traitor. Besides these schemes were pointed out that they have the problems such as a weak form of anonymity and possibility of the merchant’s dishonesty. Later, a new scheme with explicit protocols based on the principles of digital coins was introduced [4] and anonymous fingerprinting scheme that uses group signatures scheme was suggested. But these schemes also could not overcome the weaknesses of high complexity.

1.2 Constributions

The purpose of this paper is to propose a fingerprinting scheme to be possible of realization in real application. In order to address this problem, we introduce a proxy-based model. In our model, the proxy agent executes buyer’s computations instead of the buyer. Thus it is practical and efficient from the viewpoint of the buyer with small computation power since our proposal reduces amount of their computations to the minimum.

2. Proposed Scheme

Any suitable proxy signature schemes that satisfied requirements such as (1) Verifiability, (2) Strong unforgeability, (3) Strong identifiability, (4) Strong undeniability, (5) Prevention of misuse, can be combined to our proposal [5]. We assume that the proxy agent cannot disclose the buyer’s information. The underlying idea is that the proxy agent in proxy signatures plays role of the buyer in digital fingerprinting schemes. In other words, the anonymous buyer delegates the power of protocol execution to the proxy agent. Then, the proxy agent performs fingerprinting protocol with high complexity on behalf of the buyer.

2.1 Key Generation

l         It is a probabilistic key setup algorithm for the registration center. Its output is the center’s secret key and its public key , which is published authentically. Consider a large prime , a prime factor of and an element  of order

2.2 Registration Protocol

l         It is a two party protocol between a buyer and the registration center. The common inputs are the buyer’s real identity and the registration center’s public key. The outputs are the buyer’s anonymous key pair of a private key and a public key  and the registration center’s records about the buyer. In here, the registration center issues the certificate on the anonymous public key of the buyer. proves that  is a discrete logarithm or an e-th root of a given  without disclosing

2.3 Delegation Protocol

It is the two party protocol between anonymous buyer and a proxy agent.

l         The anonymous buyer chooses secret random  and sends  to the proxy agent.

l         The proxy agent randomly chooses and computes , and then communicates  to the buyer.

l         The buyer computes  and forwards  to the proxy agent.

l         The proxy agent computes  and accepts  as a valid proxy signature key, if the following equation holds:

Now, the proxy agent can execute fingerprinting protocol with his secret key  and public key  instead of the buyer. The public key is opened to the public.

2.4 Fingerprinting Protocol

If we denote by  the fingerprinted copy of the original contents  being sold.

l         The proxy agent sends  to the merchant, where  is a string identifying the purchase.

l         The merchant verifies the certificate

l         The proxy agent and the merchant execute secure two party computation protocol (SMPC). SMPC offers a function that they do not know each other’s inputs, however they are convinced that the inputs are correct. Also this protocol offers another function that secretly sends each output to each party. The proxy agent secretly computes a signatures on the , . The proxy agent’s secret input is and the merchant’s secret inputs are . If and only if it turned out that all of the inputs are correct, are obtained as the output of the fingerprinting protocol. The entire values to be embedded are and it is encrypted by the anonymous buyer’s public key .

l         The anonymous buyer decrypts  using his/her secret key .

2.5 Identification Protocol

On finding a redistributed copy, the merchant extracts . The merchant with the purchase record  can combine the information . He/She sends , which proves that the owner of this pseudonym has redistributed the digital contents corresponding to , to the registration center and asks for identification.

3. Conclusions

In this paper, we first proposed proxy-based fingerprinting scheme. In previous scheme, the buyer has to carry out all protocols; on the contrary, the buyer just executes registration protocol in our scheme. Our proposal also provides (1) registration security; an honest buyer remains anonymous, even if the attacker is a collusion of the merchant, the registration center and the proxy agent and (2) buyer anonymity; an honest buyer will not be identified if computing discrete logarithms is hard even if the merchant and the proxy agent collude. Thus our approach is suited to the customer-centered commercial transaction.

Future Research: In distributed environments like the Internet, it is very difficult to assume the trustness of the buyer, proxy agent, and the proxy key issuing protocol between them. Thus we should design more secure proxy-based fingerprinting scheme such that any possibility of misuse is prevented.


This work was partially supported by the 21st Century COE Program 'Reconstruction of Social Infrastructure Related to Information Science and Electrical Engineering, Grant No.01-2002-000-00589-0 from the Basic Research Program of the Korea Science & Engineering Foundation, and Association of International Education of JAPAN.


[1] B.Pfitzmann and W.Waidner, Anonymous Fingerprinting, Eurocrypto97, LNCS 1233, 1997.

[2] D.Chaum et al., Multiparty Computation Ensuring Privacy of Each Party’s Input and Correctness of the Result, Crypto97, LNCS 293, Springer 1987.

[3] J.Domingo-Ferrer, Anonymous Fingerprinting Based on Committed Oblivious Transfer. PKC99, LNCS 1560, 1999.

[4] B.Pfitzmann and Ahmad-Reza Sadeghi. Anonymous Fingerprinting with Direct Non-Repudiation, Asiacrypt 2000, LNCS 1976, 2000.

[5] Takeshi Okamoto et al. Extended Proxy Signature or Smart Cards, ISW99, LNCS 1729, 1999.