Dept. of Information Security, Graduate School, Pukyong Nat’l Univ.

599-1 Daeyeon-dong Nam-ku Busan, Korea.

+82-51-620-6392

jae@{tcslab.csce.kyushu-u.ac.jp, mail1.pknu.ac.kr}

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.

+81-92-642-3867

Sakurai@csce.kyushu-u.ac.jp

Dept. of Information Security, Graduate School, Pukyong Nat’l Univ

599-1 Daeyeon-dong Nam-ku Busan, Korea.

+82-51-620-6392

jpark@pknu.ac.kr

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.

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.

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.

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.