Codes with the identifiable parent property (IPP codes) are used in traitor tracing schemes that protect data broadcast by the publisher from unauthorized access or distribution. An n-word y over a finite alphabet is called a descendant of a set of t words x1, ..., xtif yiϵ {x1i, ..., xti} for all i = 1, ... n. A code C = {x1, ..., xM} is said to have the i-IPP property if for any n-word y that is a descendant of at most t parents belonging to the code it is possible to identify at least one of them. The existence of good i-IPP codes is known from earlier works. We introduce a robust version of IPP codes which allows unconditional identification of parents even if some of the coordinates in y can break away from the descent rule, i.e., can take arbitrary values from the alphabet, or become completely unreadable. By linking this problem to perfect hash functions and, more generally, to hash distances of a code, we prove initial results on the proportion of such coordinates that can be tolerated under the unconditional recovery requirement.

This paper considers the fingerprinting problem for the particular case when coalitions of pirates consist of no more than two users. It proves that random binary fingerprinting codes are secure against size-2 coalitions with probability of error tending to zero and code rate R=1-1/21og/sub 2/3=0.2075. This is an improvement by a factor of eight over the best known schemes that provide the error probability tending to zero.

We consider a general fingerprinting problem of digital data under which coalitions of users can alter or erase some bits in their copies in order to create an illegal copy. Each user is assigned a fingerprint which is a word in a fingerprinting code of size M (the total number of users) and length n. We present binary fingerprinting codes secure against size-t coalitions which enable the distributor (decoder) to recover at least one of the users from the coalition with probability of error exp(-/spl Omega/(n)) for M=exp(/spl Omega/(n)). This is an improvement over the best known schemes that provide the error probability no better than exp(-/spl Omega/(n/sup 1/2/)) and for this probability support at most exp(O(n/sup 1/2/)) users. The construction complexity of codes is polynomial in n. We also present versions of these constructions that afford identification algorithms of complexity poly(n)=polylog(M), improving over the best previously known complexity of /spl Omega/(M). For the case t=2, we construct codes of exponential size with even stronger performance, namely, for which the distributor can either recover both users from the coalition with probability 1-exp(/spl Omega/(n)), or identify one traitor with probability 1.

The paper concentrates on the real world problems created in the last two decades (1973-99) by cryptographers who publish in the open literature, and also mentions what gave rise to these problems-the solutions we gave to various theoretical problems, often of our own posing. For the last twenty years (1980-99), the annual IEEE Symposia on Security and Privacy have provided us with a stimulating and encouraging environment within which to expand cryptography's structure and visibility, while exposing us to criticism from workers in other security-related areas. Cryptography has been an important component of S&P, but seldom a major one. Much work presented is from conferences other than S&P. But S&P's influence has been ubiquitous and formative for the worldwide community of open literature cryptographers. To set the problems stage, the author presents six propositions for consideration, not necessarily for acceptance.

Davida, Wells and Kam used the Chinese Remainder Theorem to construct an encryption system allowing access to individual data fields of a record in a relational database. Their system is public-key in the sense that the read and write keys of a given data field are different. In this paper we present a database encryption system based on ideas similar to theirs. It is not public key, but has some other useful features. It makes possible the computation of averages and other statistics pertinent to unencrypted data, but it uses only encrypted data in the computation.

It is possible to find the smallest nonnegative integer R congruent modulo M to the product AB of two nonnegative integers without dividing by M. In multiple precision arithmetic, doing away with the division cuts the calculation time by varying amounts, depending on machine architecture. It also cuts storage space.

This paper solves an analog of the problem which gave rise to the theory of error control codes by methods, of miniscule computational complexity, taken from the theory of TIPS (also called key safeguarding schemes, threshold schemes, secret sharing, key sharing, and IPS). The problem solved herein is the following. Information is flowing through several parallel channels from a sending node S to a receiving node R. The possibility exists that one or more channels will be rendered inoperative, but it is deemed essential that all the information get through. Suppose that the organization responsible for the information flow wants to protect Itself against ths breakdown of some of the total number d of available channels. It thus wants to be able to use "coding" and "decoding" processes, which are quick to implement on cheap microprocessors, for blending all the information H due to leave S into a slurry which can be poured into the d channels in such a way that whatever comes out of any b channels at R is enough to reconstruct H completely. It wants more than a high speed implementation of this process on cheap hardware. It wants to send as few bits as possible. Suppose, for example, that it has 100 bits to send and that it requires assurance that they will all get through even if 3 channels fail. It cannot predict which 3 channels might fail and it knows, of course, that it cannot reconstruct the 100 bits to be sent from S unless 100 bits get through the channels which continue to function (total bit cost: 100 plus the number of bits sent on channels which fail). Each of the following solutions to its problem is therefore optimal from an information theoretic viewpoint: 1. A way to reconstruct H from l-bit transmissionson any 100 of 103 channels (involves 3 wasted bits); 2. A way to reconstruct H from 10-bit transmissions on any 10 of 13 channels (involves 30 wasted bits); 3. A way to reconstruct H from 25-bit transmissions on any 4 of 7 channels (involves 75 wasted bits); 4. A way to reconstruct H from 100-bit transmissions on any 1 of 4 (involves 300 wasted bits). Common sense is inclined to reject at least the first (too many channels used) and last (too many bits sent) of the "optimal" solutions above. This paper shows how to produce cheap high speed processes which come within a hair of being optimal (in the sense just described) solutions to the problem in question. It describes parameter settings in which the problem cannot be solved satisfactorilyby at leastsome approaches. It discusses ways to decide on which "optimal" solution to the problem is preferable. The idea behind the theory presented here was originally to provide insurance against lose of information due to long-term outage of several channels of communication. The insurance turned out to be cheap (involving only general-purpose processor and memory chips) and compatible with communications in the megabit per second range. But the process involved conferred an unlooked-for additional benefit. It provided a novel way to multiplex digital communications and, in so doing, led to the invention of a variety of mathematically natural "stepup information transformers" (devices for taking several streams of data being produced at various low bit per second rates and merging them to yield transmitted data streams at higher bit rates on a number of channels which can, in some circumstances, be smaller than the number of source streams of data) and "stepdown information transformers" (devices which take the output of several high bit per second rate data sources and transmit them, on a number of channels exceeding the number of sources, at lower bit per second transmission rates in such a way that the high rate streams reemerge separately at the receiver). Thus devices which provide reliability can sometimes also confer economies on communications systems. It became evident that there is a natural way to cascade the processes described below. This cascading operation makes possible the use of two or three microprocessors to overcome an inherent limitation of a single microprocessor. A single 32-bit micro cannot cope with two bit streams when one has more than 30 times the bit rate of the other. But a two chip cascade can deal with bit streams whose bit rates differ by a factor of hundreds. Three chip cascades can process still more disparate bit streams. Finally, it appeared that the same theory can be ueed to provide low cost reliability in packet-switching networks where packeta can be destroyed in collisions, and can be employed in chip design to provide fault tolerance.

Recently discovered procedures use a random input, rather than a cryptographic key, to turn a piece s of information into n + 1 pieces of information in such a way that s can be recovered from any b + 1 of them but that it is hard, or perhaps impossible in a sense which must be precisely defined, to recover s from any b of them. Thus, for example, one might have 15 pieces of information such that any 9 of them suffice to reconstitute s, but euch that no 8 of them give any hint as to what s is. The various authors of euch procedures have called them key safeguarding schemes, threshold schemes, secret sharing, and key sharing. None of these names captures the idea, which we will denote by information protection system (IPS). Our purpose is to put a rigorous foundation under the intuitive security arguments these papers adduce. In the proceed we will produce a distinctive style of proof of security, a rigorous argument involving product measures as a conceptual basis for justifying intuitively plausible probabilistic statement of the sort C. E. Shannon used to describe the security of the one-time pad.

Common sense, David Kahn [KA67] and Gilles Brassard [BR79] all argue that there are no unbreakable cryptosystems. What, then, is to be made of the -- provably [D179a, pp. 399-400] unbreakable -- Vernam one-time pad? The somewhat surprising answer is that it is not a cryptosystem at all, but rather a key safeguarding scheme [BL79] used, as all such schemes can be, in the courier mode. This suggests that proofs of invulnerability of key safeguarding schemes, what A. Shamir [SH79] calls threshold schemes, are as natural as proofs of difficulty of breaking cryptosystems are un-natural (perhaps impossible). Indeed, such an approach sets the Vernam one-time pad securely into context. Both the projective geometric threshold scheme [BL79] and the Lagrange interpolation threshold scheme [SH79] profit from being generalized from the field of integers modulo some prime p to arbitrary Galois fields. In particular, their computer implementations are particularly felicitous in some fields with 2n elements.