Cryptography – Key management – Key distribution
Reexamination Certificate
2000-05-10
2004-07-06
Jung, David (Department: 2134)
Cryptography
Key management
Key distribution
C713S171000, C380S277000
Reexamination Certificate
active
06760445
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method for identifying betrayers of proprietary data, i.e., authorized users who without authorization pass on proprietary data, the proprietary data being encrypted.
RELATED TECHNOLOGY
In modern information technology, it is becoming increasingly important to be able to distribute proprietary data as secure data to an authorized group of customers. Examples of this are digital pay-TV, data broadcasting, data distribution using CD-ROM, and fee-based online databases.
In all the aforementioned media, the information is distributed in encrypted form. It is customary that several authorized persons are able to decrypt this information. In practice, it is frequently the case that such proprietary data is passed on, or retransmitted without authorization to third parties. In the systems used today, it is not possible to detect the source of this type of unauthorized passing-on, or redistribution.
A first approach to solving this problem is discussed in the article “Tracing Traitors” by Chor, Fiat and Naor, published in the Proceedings on CRYPTO 194 (Springer Heidelberg, Lecture Notes in Computer Science 839). This article is hereby incorporated by reference herein. The article presents a probabilistic method for developing a so-called “traitor tracing” strategy, which can be used to find “traitor”, even if he is in collusion with up to k−1 other traitors (the article refers to this property as k-resilient).
Here, “probabilistic” means that virtually all the values in such a strategy are randomly selected. This is a disadvantage when the results of such a strategy are used in court proceedings against a person who has passed on proprietary information, without authorization. A technical report prepared by an expert that is based on probabilities has little prospect of being accepted as evidence.
One of the core aspects of the strategy described in the aforementioned article is the fact that communication session key S, which is used to encrypt the data, is divided into t subkeys s
1
, . . . ,s
t
. The session key S can only be reconstructed with knowledge of all t parts. Each of these subkeys s
1
, . . . ,s
t
is then encrypted using each encryption key from a set of encryption keys PK, and the entirety of these cryptograms is placed in front of, or upstream of the data as a so-called “access block”. Each authorized user, or subscriber U receives a subset of encryption keys PK(U)
⊂
PK, which enables him to calculate all the subkeys s
1
, . . . ,s
t
.
A property of these subsets PK(U) of encryption keys is that no combination of up to k of these subsets contains another subset in its entirety. This is a necessary precondition of the property of k-resilience.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a method for identifying betrayers, or traitors of proprietary data, making it possible to identify unequivocally at least one betrayer {overscore (U)} (i.e., an authorized user U who has, without authorization, passed on one of his subkeys to a third person), the identification method thus being acceptable as unequivocal evidence in court proceedings.
The present invention provides a method for identifying at least one betrayer of proprietary data, the method including encrypting the proprietary data using a session key; dividing the session key into a plurality of subkeys, all of the plurality of subkeys being required to reconstruct the session key; encrypting each of the plurality of subkeys using each encryption key of a plurality of encryption keys so as to form a plurality of cryptograms; placing the plurality of cryptograms in front of the proprietary data as an access block; and assigning a respective subset of the plurality of encryption keys to each of a plurality of authorized users in accordance with at least one finite geometry structure and at least one finite geometry method so as to enable each user to reconstruct the plurality of subkeys and so as to ensure a k-resilience property for unequivocally identifying the at least one betrayer using a betrayer-search algorithm, k being a maximum number of betrayers in the at least one betrayer. As in the known method described above in a method according to the present invention, data to be encrypted are encrypted using a session key S. The session key S is subdivided into t subkeys s
1
, . . . ,s
t
, all of which are required to reconstruct the session key S. Each subkey s
1
, . . . ,s
t
is encrypted using each encryption key PK from the set of encryption keys PK. The entirety of such cryptograms is placed as an access block in front of the data to be encrypted.
A method according to the present invention includes a search strategy which differs in its deterministic construction from the search strategy of the previously described method.
According to the present invention, encryption keys PK are assigned to authorized users U in accordance with geometrical structures and methods of finite geometry. Each authorized user U is allocated a subset of encryption keys PK(U) which enables him to reconstruct in each case one of subkeys s
i
for i=1, . . . t and, thus, also the session key S. Assigning the encryption keys according to geometrical structures and finite geometry methods ensures that every k authorized users have a total of no more than
&LeftBracketingBar;
PK
(
U
)
&RightBracketingBar;
k
-
1
encrypti
on
keys
in
common
with
each
other
authorized
user
.
Consequently, the k-resilience property, required for identifying a betrayer {overscore (U)}, is ensured. At least one betrayer {overscore (U)} can then be identified with certainty using a betrayer-search algorithm.
According to an embodiment of the present invention, the session key may be divided into t subkeys s
1
, . . . ,s
t
using a threshold method so that the session key is reconstructable using one of the subkeys. The threshold method may be, for example, an r, t threshold method. The method according to the present invention is described in greater detail in the following on the basis of an exemplary embodiment, the finite geometry structure used being conceived as a finite affine space AG. Such geometrical concepts are described in A. Beutelspacher, U. Rosenbaum, Projektive Geometrie [Projective Geometry], Vieweg Publishers, Wiesbaden 1992, which is hereby incorporated by reference herein.
REFERENCES:
patent: 6549638 (2003-04-01), Davis et al.
patent: 6557103 (2003-04-01), Boncelet et al.
patent: 6640305 (2003-10-01), Kocher et al.
Dittman, Combining digital watermarks and collusion secure fingerprints for customer copy monitoring, Secure Images and Image Authentication (Ref. No. 2000/239), IEE Seminar on, Apr. 10, 2000, pp. 6/1-6/6.*
Kou et al., Low density parity check codes: construction based on finite geometries, Global Telecommunications Conference, 2000, GLOBECOM '00. IEEE, vol. 2, 27, Nov.-Dec. 2000, pp. 825-829, vol. 2.*
Kou et al., Low-density parity check codes based on finite geometries: a rediscovery and new results, Information Theory, IEEE Transactions on, vol. 47, Issue 7, Nov. 2001, pp. 2711-2736.*
Chor B. et al., “Tracing Traitors”, Aug. 1994, pp. 257-270, Advances in Cryptology.
Schwenk Joerg
Ueberberg Johannes
Deutsche Telekom AG
Jung David
LandOfFree
Method for identifying betrayers of proprietary data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for identifying betrayers of proprietary data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for identifying betrayers of proprietary data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3259230