The SureSign Method

1. The SureSign Method

SureSign fingerprinting embeds a binary code into a digital datastream in a complex manner, the embedding being determined by a key.

The fingerprinting of digital data has three stages. Firstly, the conversion of any embedded code into a binary stream. Secondly, the calculation of sets of permutations, each set corresponding to a particular key. Thirdly, the addition of the permuted code to the original digital data.

The third stage may be further subdivided into two processes. The first is that of dividing the data into suitable subsets - in the case of images those subsets comprise tessellable shapes and in the case of audio or other linear data, the subsets comprise repetitively defined chunks of data. The second process is that of adjudicating at each part of the data how large a change in the original data will be acceptable to any user.

The strengths of the permutation method lie in its universality and flexibility. It may be applied to different types of data and, for any one data type, it may be applied in many different ways. An outline of the scheme as currently applied to images is given below.

i) Code Conversion to Binary
SureSign, at present, uses two codes, one to identify the image originator and one to identify the image or document. The originator identifier has two letters and four numbers (format 00-AA-00) and the image identifier has two letters and five numbers (format AA00000.)

There are many ways in which these may be converted into binary strings and the Signum method results in a binary code which, in present implementations, will normally have between 20 and 40 bits.

ii) Conversion of a Key into a Permutation
The lynchpin of the method is the use of permutations to conceal the embedded code. Even with 20 bits the number of possible permutations is 2.4 x 10¹⁸, clearly enough to prevent any systematic trial and error search.

Each originator has a unique key, and each key is required to generate a unique permutation with which to conceal the data. The most secure method for producing permutations is one in which there are initially chosen arbitrary permutations from which all others are generated, and this is the method used by Signum. The choice of the arbitrary originating permutations is roughly equivalent to the key, computed from two arbitrarily chosen prime numbers, which is used for RSA coding.

The permutations can be made to have selected properties to facilitate the subsequent code detection. Signum permutations in the first product release are commutative and have known order (the order being the number of times the permutation must be applied before elements return to their original position). The crucial point is that an arbitrarily chosen permutation is the basis for the generation of a set of permutations.

iii) Addition of Code To Original Data
This involves taking the binary message as in i) and scrambling it with a permutation as described in ii).

(a) Generation of Scrambled Code Blocks
Suppose that the binary code to be embedded consists of n bits of data. Then a permutation of n elements has to be generated from the key. The first process is to apply repeatedly this permutation to the binary code so that the code becomes unrecognisably scrambled. After r applications of the permutation, where r is the order of the permutation, the code returns to its original state. It is this set of r sets of n bits of scrambled data which is applied to the data in the manner described below.

Each set of n bits is arranged into a rectangle, p x q = n. This ensures that all parts of the binary code are fairly close together and reduces false data from image features. The rectangles themselves are then arranged in such a way that the permutation from any given rectangle to the neighbouring rectangle is always the same. This results in a large rectangle of data which consists of 1's and 0's which need to be applied to the image. The use of rectangles is for simplicity at this stage but any tessellable shape will be sufficient.

(b) Application to the Image
The above scrambled rectangle is applied repeatedly to the image. In its simplest form a '1' might indicate the addition of 1 to the original data and a '0' might indicate subtraction. However, any application to a data stream should tend to add information more strongly to areas that carry more information, and this is true of the Signum method. Areas that are smooth and slowly varying can carry less information than noisy areas without that information becoming easily detectable.

2. Rationale Behind the Choice of SureSign Method

There are several different techniques, using methods well known to mathematicians, for concealing data in a digital stream. Alternative methods and the reason for the choice of the SureSign method are discussed briefly below.

Method 1 - Frequency Domain Modification
This type of method relies on adding to the data frequencies which will be distinguishable from unfingerprinted data. Frequency methods come first to mind in the field of signal processing. They are particularly current because of the recent development of compression methods such as JPEG and Wavelets which operate in the frequency domain. The problem with this method is that frequencies have to be defined over a finite domain, and in discrete data there are often problems where a frequency extends beyond the particular feature of an image that it is required to describe. Another problem is that the frequencies used cannot be high frequencies because these are often removed in compression, and low frequencies have to be defined over larger areas.

Method 2 - Feature Recognition and Modification
These methods search for particular features in images and seek to modify them in a known way. The main drawback of this is that images that are particularly smooth, for instance, may not contain many of the recognisable features. A good fingerprinting method has the essential feature that no part of the image is exempt from the fingerprint.

Method 3 - Direct Data Addition
In this method a code is applied directly to an image. This is the SureSign method. The data is, of course, carefully concealed to prevent visibility or easy removal. The advantage with this method is that it is particularly easy for each pixel to be assessed and therefore, to determine how much information can be added. This control allows fingerprinting of the highest quality images with negligible degradation.

Method 4 - Direct Addition of Coded Data
In this method, each element of the code to be added is represented by an array of previously generated data, e.g. a plane of pseudo-noise. This method is generally regarded as being relatively insecure because all users must have knowledge of whatever arrays are used and it is then relatively easy to modify any image. It is also difficult to ensure that the generated data does not have an adverse noise-to-information ratio at particularly sensitive parts of the image.