Data validation

A method of authenticating digital data such as measurements made for medical, environmental purposes, or forensic purpose, and destined for archival storage or transmission through communications channels in which corruption or modification in part is possible. Authenticated digital data contain data-metric quantities that can be constructed from the digital data by authorized persons having a digital key. To verify retrieved or received digital data, the data-metrics constructed from the retrieved or received data are compared with similar data-metrics calculated for the retrieved or received digital data. The comparison determines the location and measures the amount of modification or corruption in the retrieved or received digital data.

FIELD OF THE INVENTION 
The present invention generally relates to digital manipulation of 
numerical data for the intended purpose of providing a means for an 
authorized person to verify the accuracy and integrity of the information 
at any time in the future. This invention was made with Government support 
under Contract No. W-7405-ENG-36 awarded by the U.S. Department of Energy. 
The Government has certain rights in the invention. 
BACKGROUND OF THE INVENTION 
The use of data in digital form for all purposes is common throughout the 
world. Much of this digital data requires a guarantee of the data 
fidelity. This guarantee means that it would be difficult, or impossible 
for an unauthorized person to modify the information without detection. 
Thus, the many kinds of data collected with digital sensors often require 
validation. Validation provides a secure means for assuring that the data 
have not been corrupted or modified since their creation. 
Commonly used validation methods that leave the data intact are a checksum, 
a digital signature, or encryption. Discussion of these methods can be 
found in the book by B. Schneier, Applied Cryptography Protocols, 
Algorithms, and Source Code in C, J. Wiley & Sons, New York, N.Y., 1994. 
This reference is incorporated herein by reference. 
A checksum guarantees the validity of the data insecurely, because an 
unauthorized person can modify the data, calculate, and append a new 
checksum value. The checksum value can be encrypted for greater security. 
Digital signatures ensure that the data are valid, but the signature is 
unable to provide an indication of the location and extent of any 
modifications in the original data. Further, any corruption of the 
checksum or digital signature value itself gives a false indication of 
data modification. 
One encryption method for authenticating data is based on a message 
authentication code (MAC), a key shared between the parties. M. Bellare, 
R. Canetti, and H. Krawczyk presented this method in "The HMAC 
Construction," RSA Laboratories' CryptoBytes, 2, no. 1, 12 (1996). 
However, encryption renders data unusable to all persons except the 
authorized users. Encrypted data are unrecognizable as meaningful 
information and the data are of no use if the validation (decryption) 
cannot be performed. Encrypted data suffering corruption or modification 
in the process of storage and retrieval, or in transmission through a 
communication channel is therefore rendered generally unusable even for an 
authorized person. Moreover, in certain situations, encryption methods are 
unacceptable for use because they conceal the data content. 
Methods that hide validation information within the data being 
authenticated offer an alternative means to validate digital data. Digital 
watermarks can be added to data by methods falling generally into the 
field of steganography. Steganographic methods are reviewed by W. Bender, 
D. Gruhl, and N. Morimoto in "Techniques for Data Hiding," Proc. SPIE, 
Storage and Retrieval for Image and Video Databases III, 9-10 Feb., 1995, 
San Jose, Calif. This reference also is incorporated herein by reference. 
One method of impressing a digital watermark is given by G. Caronni, in 
"Assuring Ownership Rights for Digital Images," Proc. Reliable IT Systems, 
VIS '95, 1995, edited by H. H. Bruggemann and W. Gerhardt-Hackl (Vieweg 
Publ. Co.: Germany). Another method is given by I. J. Cox, J. Kilian, T. 
Leighton, and T. Shamoon in "Secure Spread Spectrum Watermarking for 
Multimedia," NEC Research Inst. Tech. Report 95-10, 1995. These references 
also are incorporated herein by reference. 
Unlike the checksum or digital signature that calculate a measure of the 
original data, digital watermarking techniques modify the data in order to 
encode a known signature that can be recovered. The presence of the hidden 
signature in received data verifies that the data are unchanged, or its 
absence reveals that the data were modified from the watermarked form. The 
method of Cox et al (1995) supra is designed specifically for digital 
images, and it is sufficiently robust to survive even transformations of 
the digital data to analog form. However, all the above methods proposed 
for digital watermarking generally detect modifications by means of an 
external signature, i.e., no metric that measures the fidelity of the 
original digital data is used. Consequently, there exists no ability to 
measure in any detail the extent of the changes made or to estimate the 
precision of the received data. The steganographic watermarking methods 
differ from the digital signature and checksum methods primarily by being 
invisible, and by using the digital data to convey the watermark, thus 
eliminating the need for an appended value. 
A robust, new method for validating digital data is taught by the present 
invention. Information needed to verify digital data is conveyed in the 
nearly adiabatic modifications to the digital data. The modifications 
consist of manipulation the digital data in a manner similar to the 
disclosures in copending U.S. patent application Ser. No. 08/392,642, 
filed Feb. 23, 1995, for DATA EMBEDDING. 
Data validation as disclosed in the present invention hides data-metric 
quantities in the host digital data that measure the fidelity of the 
digital data. The data-metric values are incorporated into the data set by 
means of the data embedding method as disclosed in the above described 
copending application. 
It is therefore an object of the present invention to provide apparatus and 
method for validating the data in a digital information stream without 
significantly changing the digital information. 
It is another object of the present invention to provide apparatus and 
method for thwarting unauthorized access to the validation information 
that is embedded in normal digital data. 
It is another object of the present invention to provide apparatus and 
method for constructing data-metrics from the digital data and a digital 
key, the data-metrics being constructed to convey the information 
necessary to verify the authentication of the digital data either 
completely, or in part. 
Additional objects, advantages and novel features of the invention will be 
set forth in part in the description which follows, and in part will 
become apparent to those skilled in the art upon examination of the 
following or may be learned by practice of the invention. The objects and 
advantages of the invention may be realized and attained by means of the 
instrumentalities and combinations particularly pointed out in the 
appended claims. 
SUMMARY OF THE INVENTION 
To achieve the foregoing and other objects, and in accordance with the 
purposes of the present invention, as embodied and broadly described 
herein, there is provided a method of validating digital data values 
comprising the steps of calculating first data-metrics that measure the 
digital data values completely, or in parts; authenticating the digital 
data in the form of revisions made by data embedding methods to represent 
the digital data-metrics by means of modifications to the digital data 
values; calculating second data-metrics for the digital data values after 
the digital data values are transmitted, archived, or opened to 
unauthorized modification; constructing an independent version of the 
first data-metrics for the digital data values after the digital data 
values are transmitted, archived, or opened to unauthorized modification 
by means of constructing the first data-metrics using the data embedding 
methods; comparing the calculated second data-metric with the constructed 
independent version of the first data-metric to determine locations and 
amount of modifications or changes to the digital data values; and 
outputting the locations and amount of modifications to the digital data 
values as verification quantities to a data port or file. 
In another aspect of the present invention, and in accordance with its 
objects and purposes there is provided apparatus for authenticating 
digital data values that can be serialized to a sequence of individual 
digital-data element values comprising data authentication means receiving 
the individual digital-data element values in an ordered sequence for 
calculating data-metrics and embedding pair candidate values and for 
outputting the data-metrics and the embedding pair candidate values. Data 
embedding means receive the data metrics, the embedding pair candidate 
values and the individual digital-data element values in an ordered 
sequence for embedding the data metrics and the embedding pair candidate 
values into the individual digital-data element values in an ordered 
sequence and outputting authenticated digital-data values. 
In yet another aspect of the present invention, and in accordance with its 
objects and purposes, there is provided apparatus for constructing 
data-metrics from a key-pair table embedded into individual frames of 
digital-data values presented in sequence comprising data metric 
construction means receiving the key-pair table and the individual frames 
of digital-data values and outputting a bitstream corresponding to a first 
data-metric embedded into the individual frames of digital-data values. 
Data-metric means receive the individual frames of digital-data values for 
calculating a second data-metric and outputting the second data-metric. 
Data verification means receive the bitstream corresponding to the first 
data-metric and the second data metric for comparing the first data metric 
with the second data-metric and presenting the results of the comparison 
to an output port.

DETAILED DESCRIPTION 
The present invention allows data-metrics to be embedded into digital data 
without naturally discernible alteration of the content and meaning of the 
digital data. This is made possible through the use of the data embedding 
technique in the present invention, in which data embedding, as taught in 
the aforementioned copending "Data Embedding" application, is performed in 
a sequence that permits constructing a data-metric by parts. 
Data to be transmitted or archived are authenticated by the invention as 
illustrated in FIG. 1. The invention processes the digital data 10 to 
calculate data-metric values 12. The invention analyzes digital data 10 to 
determine key-pairs and key-tables 11 for use with the aforementioned 
"Data Embedding" application, which is used by the present invention to 
embed data-metric values 12 into digital data 10 in step l3. The digital 
data are thereby authenticated in step 14, and they can be verified at a 
future time, by a person authorized with the data embedding key-pair and 
key-table values. 
The digital data example given herein is a sequence of floating point 
decimal values 20 in FIG. 2. The histogram data-metric is calculated 21 to 
produce a graph of the frequency of occurrence versus the floating-point 
value, in bins 22. The histogram data-metric is analyzed in step 24 to 
determine embedding key-air and key-table values, and the histogram 
data-metric is formed into auxiliary data packets 25 that can be embedded 
into the original digital data. In one embodiment of the present 
invention, the digital data-metrics are calculated and formed into 
auxiliary data packets separately from the histogram in step 23. The 
embedding method distributes the packets into tiles or sequences of the 
digital data in step 26. The resulting authenticated digital data 27 
contains an embedded data-metric characterizing the original data, without 
the data-metric presence being readily discernible. 
The process for verifying digital data 30 that are received from 
transmission, retrieved from an archive, or opened to any unauthorized 
modification is shown in FIG. 3. A person authorized to verify the data 
has in possession the key-pair and key-table values 31 used for data 
embedding. Auxiliary data packets containing portions of the data-metrics 
are constructed using the embedding key-values. The packets that fail to 
construct properly in step 32 indicate directly the regions of data 
modification or corruption. The constructed auxiliary-packet data permit 
reconstruction of the data-metric 33, except for the portions that were 
modified or corrupted (34). The data-metric is calculated directly in step 
35 from the received data 30. The calculated data-metric 36 is compared 
with the data-metric that is constructed from the embedding key-values 34 
and the amount of error is estimated in step 37. 
In the example, for authentication with the histogram data-metric, the 
histogram of the digital data is embedded into the digital data values. 
Other suitable data-metric quantities are validation sums for blocks of 
the data, or the deviation from the average of data values within a block 
or sequence of values. The invention requires that data-metric quantities 
are embedded adiabatically into the data, in order to provide the means to 
verify that the data are unchanged to within the known error introduced by 
the data embedding process. 
Conventional steganography modifies the original data more than does the 
data embedding technique. For examples of conventional steganography, see 
the aforementioned article by W. Bender, D. Gruhl, and N. Morimoto 1995, 
"Techniques for Data Hiding." The significant, often large change in the 
digital data made by conventional steganography obscures the digital 
data-metric of the transmitted or archived information, thereby preventing 
verification of the host data. 
In the present example, the data values are floating point numbers that 
represent a cosine function containing both white and spike noise. FIG. 4 
shows a graph of the test data. FIG. 5 shows a listing of the C++language 
computer program that generates the test data. The histogram of the 
digital data shown in FIG. 6 graphs the fiequency of occurrence of any 
value versus its value. For the example, the original-data histogram is 
used as a single data-metric. 
The histogram abscissa in FIG. 6 is the digital-data value coordinate, and 
the ordinate is the frequency of occurrence of the values. An abscissa 
value corresponds with the digital data values falling within a specified, 
decimal histogram interval. The histogram ordinate value is the total 
number of data values found in the abscissa interval. Thus, the histogram, 
when normalized to unit area is the probability density for selecting a 
randomly drawn value from the data. 
The histogram-metric validates digital data by comparing the constructed 
histogram with the histogram calculated for the received or retrieved 
data. Data embedding modifies the digital data values at most by one 
abscissa interval, for pair embedding, and by several intervals, for table 
embedding. Therefore, data embedding as taught in the aforementioned 
copending "Data Embedding" application guarantees that the histogram 
ordinate values change by less than a specified percentage. 
After the embedding process, the histogram ordinate value corresponding to 
key-pair or key-table digital-data values differs from the original 
histogram-ordinate value by less than a known amount. Any differences in 
the digital-data values larger than the known amount indicate that 
modification or corruption of the digital data has occurred. 
Moreover, the histogram difference owing to data embedding modification of 
the digital data is statistically consistent with the original histogram. 
The statistical constraint on the fiequency of occurrence of the key-pair 
and key-table values that is inherent in the data embedding method permits 
using statistical comparisons of the histogram-metric to verify the 
received digital data. 
Consider floating point digital data having numerical values in the 
interval 0.0 to 1.0. Assume the histogram abscissa interval is 0.01, or 
one percentage of the data range. If the original data value 0.53256 
changes to 0.53166, the amount of change (0.0090) is less than the 
histogram interval. Thus, the data value change is insignificant for 
verification with the histogram metric, because it does not modify the 
histogram frequency of occurrence. Consequently, for this example, the 
data for a key-pair embedding method are verifiable to within about 1% of 
the maximum value. 
If the digital data value in the example changes to 0.52000, the amount of 
change (0.01256) is larger than the abscissa interval. The change causes 
the frequency of occurrence for one abscissa value to decrease, and the 
frequency to increase for an adjacent histogram interval. If the histogram 
abscissa values are members of the embedding key-table, then the change 
could occur as a result of applying the data embedding algorithm. In this 
case, for the data to be verified to within 1%, the total histogram 
ordinate values corresponding to embedding-key abscissa values must agree 
to within the embedding constraint. 
If the histogram abscissa value is not a key-pair or key-table value, or 
the histogram ordinate difference exceeds the embedding constraint, then 
the received or retrieved digital data value is different from the 
original value. Hence, the amount and number of changes can be estimated. 
Histogram metric verification for embedding with key-pair values detects 
in detail the changes in digital data values that are not embedding-key 
members. Digital data values used as key-pair values guarantee changes 
within twice the histogram interval. Statistically, the digital data are 
verifiable to within one histogram interval, or 1% in this example. 
Comparison of the computed and constructed histogram leads to a 
statistical estimate of the likely number and magnitude of changes made to 
the original data. 
The digital-data values authenticated by use as elements in an embedding 
key-table suffer greater changes than for digital-data values used as 
key-pairs. For a cluster of four digital data values used in an embedding 
key-table, the histogram-ordinate values, i.e., the frequency of 
occurrence, corresponding with the table entries are approximately equal. 
Thus, the invalidation of digital data values equal to the key-table 
values is certain, when the calculated histogram ordinate values differ 
from the constructed ordinate values by more than the embedding 
constraint. For histogram ordinate, i.e., frequency of occurrence values 
falling within the constraint, the digital data validate to within the 
size of the table in units of the histogram interval, or 4% for the 
example. 
In one embodiment of the present invention, the digital data-metric can be 
the average for a set of consecutive data values. For floating point data, 
compute the average for a number M, of consecutive digital data values. 
The number M of values contributing to the average is the number of data 
values required to contain the embedded data-metric, for example 32-bits, 
the size of a value having the float data type. 
For verification in the embodiment, each constructed data-metric quantity 
is compared with the corresponding value calculated from the digital data 
under examination. If the sum of the received M digital data values agrees 
with the embedded sum to within the error introduced by the embedding 
algorithm, then the data are verified. For random bits embedded, data 
embedding changes the digital data values uniformly, and the M-average 
calculated metric value agrees closely with the metric average calculated 
from the original digital data. 
The data-metric values can be embedded with the key-table method described 
by M. T. Sandford, T. G. Handel, and J. M. Ettinger in "Data Embedding in 
Degenerate Hosts," Los Alamos National Laboratory Report LA-95-4446UR, 
December 1995 (incorporated herein by reference). For a key-table 
containing four values, two bits per digital data value are embedded. 
Thus, at least M=16 host values are needed to embed the 32-bit float-type 
average. 
FIG. 7 shows a portion of floating point data authenticated with an 
embedded average-value data-metric. The embedded data-metric is the 
average of a consecutive sequence of host data values. One embodiment of 
the present invention processes the digital data sequentially, and 
determines the number of data values that are required to embed the 
combination of a "magic number," an arbitrarily chosen binary number used 
to identify start of a data-metric, and a single 32-bit float-type data 
average. Assuming a 4-bit magic number, and 32-bits of a floating-point 
average value, 36 bits of auxiliary data must be embedded. 
The run of twenty-five data values shown in FIG. 7 provides 36 bits of 
embedding space. In the left column of raw digital data values in FIG. 7, 
seventeen are identified as members of 4-element embedding key-tables that 
embed two bits for each value. Two data values are members of an embedding 
key-pair that embeds one bit each. 
The data-metric, i.e., the average calculated for the twenty-five values in 
FIG. 7 is 1.32532. The embedded data-metric value, i.e., the average of 
the original twenty-five values before embedding is 1.33456. The 
difference is 0.6 percentage of the average, and the comparison therefore 
verifies the example data to within one percent. 
Different data-metrics are possible as well, in other embodiments of the 
invention. For example, the variance from the average can be calculated, 
embedded, and compared with the variance calculated for the received data. 
The variance gives greater sensitivity to changes in the data ordering 
than does the average value. 
A potential disadvantage of the embodiment of the present invention that 
uses the average-value data-metric, in comparison with the histogram 
data-metric, is the inability to detect reordering of the data. However, 
the data embedding construction process detects reordering of the digital 
data. Exchanging elements within the data, or modifying their values 
corrupts the embedded quantity. Even the magic number that identifies the 
data-metric could be corrupted by manipulations of the data. Significant 
changes to the digital data values invalidate the construction processing 
of the entire block. Therefore, data reordering is detected easily by the 
present invention. 
Like encryption, the data validation method automatically verifies 
digital-data by means of a successful construction of the hidden metrics. 
Digital data corrupted in transmission, or modified by an unauthorized 
person cannot be processed to construct the data-metric values, because 
the bit sequence of the auxiliary data depends upon sequencing of the 
digital data values. Even a single digital-data value changed from a 
key-pair value to any value not in use as a member of the key-pair stops 
the packet construction process. Likewise, changing a data value from a 
key-pair value to a key-table value desynchronizes the packet construction 
algorithm. 
However, any digital-data values that are not part of the embedding-key 
sequence can be modified, removed, or added without affecting the 
data-metric construction process. Modifications of non-key digital-data 
values are detected by comparing the constructed data-metric with the 
metric calculated from the digital data. 
Verifying digital-data by means of data embedding applied to the present 
invention therefore requires embedding the data-metric values with an 
algorithm that is robust against corruption of the digital-data. Consider 
an embedding algorithm that processes the digital-data sequentially, 
starting at the beginning of the data and working towards the end. In the 
simplest form, the data-metric forms a single-unit constructed by 
processing the digital data, with the embedding key, from its beginning to 
the end. However, any data-metric constructed following a corrupted 
element of the host data are incorrect. Hence, a single-unit scheme is not 
useful for validating the content of the digital-data. 
The data embedding process, as described in the aforementioned copending 
"Data Embedding" application, is modified by the present invention to 
partition embedding into the digital-data, and to divide the data-metric 
that measures the data fidelity into independent blocks. 
The aforementioned copending "Data Embedding" application applied to fax 
embedding divides the auxiliary data into packets, each containing a 
sequence number and a checksum. If the extraction of a particular packet 
fails, because of fax digital-data corruption, the data for other packets 
are unaffected. Hence, the presence of corrupted pixels in the fax 
digital-data, i.e., the black and white fax image, affects only part of 
the data. The concept of embedding data according to blocks, or packets, 
extends to a more general case in this invention. 
In a fax image, transmission errors typically cause data-dropouts that 
degrade part, or all, of a pixel row. The fax transmission protocol 
synchronizes the start of pixel rows to preserve the readability of the 
fax document. In the aforementioned pending application, the fax-data 
embedding process synchronizes to the start of the rows of pixels in the 
image, in order to provide a means for the extraction process to recover 
from corrupted host data. Synchronized embedding ensures that the start of 
a data packet signals when it decodes from the image. A process similar to 
that used by the well-known XMODEM data transmission protocol is used. 
For fax bitmaps, a start of a packet is identified by a pixel line 
containing the first black pixel in an even-numbered column. Lines with 
pixels starting in odd-numbered columns are `continuation` lines. 
Continuation lines contain data contributing to the construction of the 
packet that began earlier, on a starting line of pixels. If a 
packet-starting line appears when a continuation line is expected, then 
the packet is corrupted and its data are not constructed. 
After constructing packet data, the checksum validates its content. 
Auxiliary data decoded from the packet move to the auxiliary data stream. 
If a checksum test fails, the packet is corrupted, in either its sequence 
number, data, or checksum portion, and the packet content is suspect. 
Data embedding employed for purposes of conveying data-metrics within the 
digital data employs a similar, packet embedding scheme. Moreover, the 
embedding algorithm must consider the nature of the likely corruption of 
the host data. If the host data change extensively, for example by 
inverting the data or by a non-linear transformation, then the corruption 
is so large that verification probably is not possible. 
However, if the corruption is partial, for example a few random changes or 
the loss of a segment of the digital data, then an embedding algorithm 
using packets can recover some data. A few data-metric values may be 
sufficient to identify and verify the unchanged parts of the digital data, 
and to characterize the corruption. 
FIG. 8 illustrates one way to process digital-data into packets. The 
digital-data-metric bit stream separates into parts, shown as 16-bit 
segments in the illustration. For the example, the auxiliary data-metric 
bit stream consists of the digital-data histogram values, and any 
additional values that might be required for validation purposes. Each 
part of the data-metric is processed according to the flow shown in FIG. 
8. Compressed digital data cannot be decompressed if any portion is 
incorrect, so it is preferable to divide the data-metric into parts, 
compress each data-metric part, encode the portion into packet format, and 
embed each packet separately. 
A packet sequence number concatenates with the digital-data, and the result 
is compressed, using a loss-less algorithm, to 10 bits in this example. In 
practice, a larger packet size is needed for compression to work 
efficiently. A data packet is created by calculating a checksum value for 
the compressed digital-data and combining it into a single bit sequence 
(16 bits, in this example). The sequence number is present only to 
facilitate the correct identification and placement of the packets into 
the extracted bit stream. 
The embedding algorithm constructing the largest amount of correct 
auxiliary data depends on the kind of host data corruption that is likely 
to occur. For fax images, noise in the transmission is usually a data 
dropout that corrupts perhaps a few lines of pixels. One or more packets 
of the auxiliary data are lost, because several lines of pixels define the 
packet size. 
The embedding algorithm used in the present invention should synchronize 
the packets with the digital data in a fashion that minimizes the number 
of lost packets. For the fax application, embedding with an algorithm that 
disperses the packet data randomly across the host data-space would be a 
poor choice, because a sequence of corrupted host-data values would affect 
several embedded data packets. A scheme embedding packets sequentially is 
robust against corruption that occurs in sequence, for example dropouts 
that occur during transmission of the digital data. 
An alternative embedding method distributes the data-metric into 
two-dimensional `tiles.` Images and data that have meaning in more than 
one dimension are more robust when the embedded data-metric packets 
distribute into an area. A digital image for example is manipulated with 
tools that operate on specified portions of the image. Hence, corruption 
in the image tends to be spatial rather than sequential. 
FIG. 9 illustrates embedding packet data in sequence for linear 
digital-data, and according to tiles for spatial data. In the image shown 
schematically in FIG. 9, sequential embedding moves across the rows of 
pixels, moving from the first pixel line upward. Heavy line segments 
indicate where runs of host data values are used to embed packet 
information. In practice, the number of pixels needed to embed a packet 
varies, because the frequency of occurrence of pixels within the 
key-values varies within the host data. 
The heavy rectangles in FIG. 9 show the host pixels used by a tiled 
embedding algorithm. Each two-dimensional tile of host data holds one 
data-metric packet. The irregular shaded region is the type of spatially 
correlated corruption that is the most likely for image data. 
In the two-dimensional pixel space, a tiled embedding algorithm reduces the 
effect of image corruption, in comparison with a sequential embedding 
algorithm. A tiled-packet method is more robust than a random or 
sequential embedding method, for randomly changed host data values, 
because a number of random changed values falling within a tile affects 
only one packet. However, for many random changes, neither sequential nor 
tiled embedding is likely to be very robust against corruption of the 
embedded data. 
The present invention applies the aforementioned copending "Data Embedding" 
application to embedding auxiliary information into floating-point host 
data, for example the data shown in FIG. 4. The data in FIG. 4 show one 
cycle of the cosine function, degraded with white and spike noise. White 
noise is added to each point, with amplitude .+-.0.05. Spike noise is 
present with 5% frequency, with .+-.0.30 amplitude. Thus, the sample data 
in FIG. 4 contain random, or white, and spike noise components, simulating 
data typical of sensor values recorded as floating-point numbers. The 
number of sample data values is M=16,383. 
The histogram of the floating point values f.sub.i, (i=1,2,3, . . . M) 
defines a unique embedding key. FIG. 6 shows the histogram of the sample 
floating point data shown in FIG. 4. The arbitrary histogram size is 10% 
of the number of floating point values. Therefore, for the sample data in 
FIG. 4, the histogram in FIG. 6 contains N=1638 entries. 
The size of an interval in the histogram shown in FIG. 6 is 
.epsilon.=.DELTA./N, where .DELTA.=f.sub.max -f.sub.min is the range of 
the floating-point data values. In FIG. 6, the histogram is sparse for the 
lowest and highest intervals, because only the largest and smallest data 
spikes contribute to those samples. The histogram is symmetric, and it 
contains two peaks. The peaks represent the most frequent values in the 
sample data, that occur at values where the data approach the limits 
.+-.1. Between the peaks of maximum frequency in FIG. 6, the frequency of 
occurrence of the data values is noisy, and approximately uniform owing to 
the white noise in the digital data. 
In the embedding method taught in the aforementioned "Data Embedding" 
application, one embeds auxiliary data using pairs and clusters of sample 
values chosen by applying constraints to the histogram. Reasonable 
selection constraints are 10% for the frequency of occurrence, and a data 
value range of eight histogram intervals. The constraints force the host 
data pairs and members of the embedding tables to fall within a range of 
8.epsilon., but the values are not necessarily consecutive, or adjacent to 
one another. Table 1 gives the parameters for the data in FIGS. 4 and 6. 
TABLE 1 
______________________________________ 
Sample Data Parameters 
______________________________________ 
F.sub.min , min. data value 
-1.22421 
F.sub.max , max. data value 
1.32080 
.epsilon., histogram interval 
0.00155373 
8.epsilon., embedding histogram range 
0.0124298 
______________________________________ 
In order to create the embedding key, the present invention processes the 
sample data values sequentially, from their beginning to end. For each 
data value, the integer histogram interval index is calculated, and tested 
against other values falling within the constraints on interval range 
(8.epsilon.), and frequency of occurrence (equal to within 10%). In 
addition, a maximum cluster size of four values, corresponding to two 
embedding bits, is permitted. For the sample data in FIG. 4, the 
embedding-key selection algorithm finds 154 pairs and 129 tables. The 
C++language computer code that selects the pairs and tables is shown in 
FIG. 10. 
Embedding auxiliary data-metrics into the floating-point values is 
identical in principle with the method taught in the aforementioned "Data 
Embedding" application. The details for embedding differ because the 
floating-point values falling within the histogram interval generally 
differ from one another, whereas the integer values used for digital 
images define the histogram abscissa coordinate. An example serves to 
illustrate the difference. 
In FIG. 7, consider the two data values identified as members of an 
embedding-key pair. The values in FIG. 7 are examples for illustration 
purposes, and they do not correspond to data in FIGS. 4 and 6. Two values 
are 1.95623 and 2.11213. If one assumes the histogram interval is 
.epsilon.=0.01 for this example, and that the data begin with a minimum 
value of 0.00000, then the histogram interval indices for the two values 
are i=195 and j=211, respectively. For embedding purposes, any host value 
falling within the interval 1.95000-1.95999 represents an embedded 0-bit, 
and any value falling within the interval 2.11000-2.11999 represents an 
embedded 1-bit. 
As the embedding code processes the host data, suppose it is necessary to 
embed a 0-bit, and assume further the digital-data value 1.95763 is 
encountered. Because this value falls within the histogram interval 
corresponding with a 0-bit, no change is necessary, and the embedding 
process moves to the next auxiliary bit. Suppose this bit is also a 0-bit. 
If the next digital-data value encountered is 2.11565, a value within the 
range representing a 1-bit, then it must be changed to a value falling 
within the range representing a 0-bit. Changing the digital-data value 
creates a new data value within the proper histogram interval. The 
original data value is h=2.11565, then the new value is 
EQU h'=s(i+.gamma.), 1) 
where .gamma. is a random number uniform in the unit interval. Therefore, 
data embedding for floating point values differs from the integer 
implementation, because new data values are created. However, the values 
created are constrained by the embedding-key values, in order to guarantee 
that the new values follow the original digital-data histogram. 
The first requirement of a verification algorithm is the construction of 
the embedded data-metric. The embedding key must be available. It is 
assumed that the correct, uncorrupted key is known, and that the data 
containing the embedded information are obtained through channels 
admitting the possibility of data corruption. 
Assume the histogram-metric is constructed correctly. The verification 
process consists of comparing the histogram of the data received with the 
original histogram. The two differ; owing to the embedding process that 
modified the host data values. To illustrate the magnitude of the 
difference, compare the sample data after embedding the histogram-metric 
shown in FIG. 6 with the original data shown in FIG. 4. The 
histogram-metric in FIG. 6 was compressed with the PKZIP.RTM. algorithm 
before embedding into the digital data shown in FIG. 4. FIG. 11 shows the 
digital data containing the embedded histogram metric. FIG. 12 shows the 
histogram for the data in FIG. 11. 
As expected, FIGS. 4 and 11 appear similar. Comparing the respective 
histograms in FIGS. 6 and 12 reveals differences due entirely to the 
embedding invention. In particular, the noise in FIG. 12, in the interval 
between histogram index 273 and 1365, is greater owing to the 
randomization in equation (1) above. Details of the peaks at the left and 
right sides of the histograms differ as well. The extreme left and right 
parts, i.e. the histogram of the noise spike components, are unchanged 
because the embedding algorithm constraint avoids these values. 
In this example, verifying the received data consists of applying an 
algorithm to compare the two histograms. Statistical methods measure the 
correlation between the extracted, original histogram and the histogram of 
the data received. The correlation length is the value interval 
represented by the histogram constraints that select the embedding-key 
values, 8.epsilon. for the sample data. Data received without any 
modifications verify easily with a statistical comparison. 
Verifying embedded information from a corrupted host presents a significant 
challenge, because the corruption affects the construction of the embedded 
data-metric information. Most likely, part of the data-metric information 
is lost, and cannot be constructed. The effect of corruption in the 
received data e.g. changes in the data as illustrated in FIG. 3, leads to 
missing portions of the extracted histogram. Thus at the time of 
verification, the original histogram will be known piecewise, rather than 
complete, as shown in FIG. 6. 
The locations of packets corrupted by data changes in the sequence of host 
data values, or by data changes within tiles reveal directly the locations 
of the data corruption. The received data (see step 30, FIG. 3) can be 
divided into sections to identify the parts known to contain corrupt 
information. The failure of an embedded packet to construct correctly does 
not necessarily mean that all the information contributing to its 
extraction process is invalid. Only one changed value can invalidate the 
sequence number or checksum of an embedded packet. 
For the example data, a test for validity is still possible if the 
extracted histogram is largely intact. The histogram of the received data 
are calculated and compared with the histogram fragments that are 
extracted, in order to set a measure to the validity of the received data. 
Embedding the histogram metric into floating-point digital data is 
supported by a C++language data validation class. FIG. 13 contains the 
C++object definition listing. The Cvalidate:: class is designed to 
facilitate embedding the histogram into a file containing floating point 
numbers. The class is derived from the CDataFile:: class, which is part of 
the data embedding class architecture defined and implemented by M. T. 
Sandford in "A Data Embedding Class Architecture," Los Alamos National 
Laboratory report LA-CP-96-151, Mar. 29, 1996 (incorporated herein by 
reference). The public members of the data validation object are methods 
for individual use to calculate and embed the histogram. 
The constructor function Cvalidate(short Data.sub.-- Type, short 
Data.sub.-- Mode, LPSTR lpFname), accepts three arguments. The Data.sub.-- 
Type specifies the kind of data to be validated. For the present example, 
only floating point data are supported and the Data.sub.-- Type variable 
is DATA.sub.-- TYPE.sub.-- FLOAT. The Data.sub.-- Mode variable specifies 
the operation requested of the class. Two possible modes are VALIDATE and 
XVERIFY, to calculate and embed the histogram, and to extract and verify 
it, respectively. The third argument is a string identifying the path and 
file name for the host data. 
The class processes the digital data file with the virtual routine named 
MakeFloatTable(). The routine provided in the class implementation reads 
32-bit floating-point numbers from a binary data file. The routine is 
virtual, in order for the user of the class to provide customized code to 
read and process data in a different format. The MakeFloatTable() routine 
is capable of processing 16,382 values in the 16-bit Windows.RTM. Ver. 3.1 
implementation. Larger files can be processed by building the class for 
the 32-bit architecture Windows.RTM. 95 and Windows.RTM. NT systems. 
The output of the class constructor is a data file named output.bin. The 
file is written in the same format as the original, input file of host 
data. The output.bin file contains the host data authenticated with the 
embedded, compressed histogram. 
For the Data.sub.-- Mode parameter equal to XVERIFY, the file named in the 
third argument is processed to extract and decompress the embedded 
histogram and to call a virtual routine CompareHistograms(). The other 
public function members of the class are summarized in Table 2. 
TABLE 2 
______________________________________ 
Validation Class Member Functions 
Member Routine Description 
______________________________________ 
MakeHistogram(void) 
Calculates the histogram of the 
floating point data 
MakeHistTables(void) 
Analyzes the histogram to 
identify pair and table values for 
the embedding key 
EmbedFloatValues Embeds the data file into the 
(lpDataFile, lpOutFile) 
floating point values, and 
creates the ouput file 
EmbedFloatPairs Embeds one bit into the a 
(*fvalue,k,*maxval) 
floating pt. Value 
EmbedFloatTables Embeds multiple bits into a 
(*fvalue,cndx,*maxval) 
floating pt. Value 
MakeIndexTable(void) 
Constructs a look-up table for 
data extraction 
ExtractFloatValues(lpKeyFile) 
Extracts data from fl. pt. Values 
using a key 
ExtractFloatPairs Extracts a bit from a floating 
(*fvalue,k,*maxval) 
point value 
ExtractFloatTables 
Extracts multiple bits from a fl. 
(*fvalue,cndx,*maxval) 
pt. Value 
CompareHistograms(void) 
Compares data histograms to 
verify data 
______________________________________ 
The invention is implemented in hardware by processing pixel data as is 
shown in FIGS. 14 and 15. In FIG. 14, digital data 140a enter data 
authentication chipset 140 through an input port 140b. Digital-data 140a 
also pass to a data embedding chipset 141 for processing to determine 
key-pair and key-table values. Data authorization chipset 140 calculates 
data-metric quantities 143 and makes them available at output port 140c 
that is connected to data embedding chipset 141. Authenticated data 
containing embedded metrics pass from output port 141a of data embedding 
chipset 141 to archival storage, or to a communication line for 
transmission 142. 
In FIG. 15, digital data 150a received from communications or retrieved 
from archival storage are presented to data-metric chipset 150 at input 
port 150b. Embedding-key values 151 are provided separately to data 
construction chipset 152 and permit the authorized user to implement the 
data construction algorithm with data construction chipset 152. Calculated 
data-metric values 153 are calculated from digital-data values 150a on 
input port 150b. The calculated data-metrics 153 are compared with the 
constructed data-metrics 154 in data verification chipset 155, and the 
result of the comparison is made available at data verification chipset 
output port 155a. Digital-data appearing at input port 150b are thereby 
verified, and the result made available for further processing. 
The present invention is broadly applicable to many fields which employ 
digital methods for the transfer of records. Among these applications are 
in the transfer of physiological, biological and health records, of data 
generated from sensors, of diagnostic records relating to disease, aging 
or injury, of records relating to environmental monitoring or measurement, 
of measurements relating to forensic analysis, including records relating 
to evidence and litigation, and of digital multimedia information. 
The foregoing description of the preferred embodiments of the invention has 
been presented for purposes of illustration and description. It is not 
intended to be exhaustive or to limit the invention to the precise form 
disclosed, and obviously many modifications and variations are possible in 
light of the above teaching. The embodiments were chosen and described in 
order to best explain the principles of the invention and its practical 
application to thereby enable others skilled in the art to best utilize 
the invention in various embodiments and with various modifications as are 
suited to the particular use contemplated. It is intended that the scope 
of the invention be defined by the claims appended hereto.