Abstract
Integrity is the property of information concerning protection against its unauthorized modifications and forgeries. This chapter discusses bulletin board (BB), hash functions, MACs (Message Authentication Codes) and digital signatures, as schemes for maintaining integrity of data. BBs protect data by simply disclosing them to the public, i.e. an entity cannot modify them without being watched by others. Hash functions, Macs, and digital signatures protect data by detecting illegitimate modifications while attaching values to the data. Namely, when an entity illegitimately modifies the data, the modified results become inconsistent with the attached values. When hash functions, MACs and digital signatures are compared regarding the ability to convince entities that the data are authorized ones, hash functions cannot enable entities to convince others, and by MACs, entities can convince others only when relevant secrets are properly protected. On the other hand, digital signatures enable anyone to convince others without constraints.
TopHashes, Macs And Digital Signatures
Although various mechanisms exist for maintaining integrity of bit strings, many of them share the common idea. That is to add redundant information to the bit strings to be protected so that their modifications can be detected by examining the relations between the bit strings and the added redundant information. A Hamming code for error detection shown in Figure1 is an example (Hamming, 1980). In the figure, a redundant bit P is added to bit string M so that the total number of 1s in bit string M and P becomes even. Therefore, when erroneous behaviours of hardware or software disrupt M, changes in M can be detected by counting the number of 1s in M and P, provided that the errors change values only in a single bit position of the given bit string, i.e. when erroneous behaviours of hardware or software change M, the number of 1s in M and P becomes odd. Many exiting mechanisms that maintain data integrity behave in the same way. However, the redundant information must be constructed in more sophisticated ways, because different from Hamming codes that detect modifications made by hardware or software failures, mechanisms for maintaining data integrity must detect data modifications and disruptions also made intentionally by malicious entities.