When information security is important, message authentication is often used. In this dissertation, extended research on Noise Tolerant Message Authentication Codes (NTMAC) for noisy message and image authentication is presented. The reasons for proposing these NTMACs lie in avoiding the oversensitivity to channel errors, achieving much better collision rates and obtaining information on error numbers and locations, which cannot be achieved by the conventional MACS. Some future research directions are also proposed.

Firstly, the recently proposed Noise Tolerant Message Authentication Code (NTMAC) is introduced. The NTMAC can tolerate a small number of errors, such as might be caused by a noisy communications channel. It uses a repetition structure and the conventional MAC in its construction. It inherits the conventional MAC's resistance to forgeries. Furthermore, the NTMAC gives some indication of the number and locations of errors. It is obvious that the error localizations rely on the partitions of the NTMACs. Therefore, the partitioning schemes and the impacts they impose on the NTMAC error toleration are explicitly elaborated.

Secondly, the Parity NTMAC (PNTMAC) is proposed by replacing the truncated conventional MAC in NTMAC by a parity MAC, which has better odd numbered error detecting rates than the truncated conventional MAC. The parity MAC can localize the errors in a smaller range than the conventional MAC does. Through this modification, the PNTMAC gives a better indication of the number and location of the errors than the NTMAC does.

Thirdly, inspired by the low error missing rate of the CRC, the CRC-NTMAC is proposed. The CRC-NTMAC has a much lower collision rate than the NTMAC does. In the CRC-NTMAC, the partitions are selected pseudo-randomly, thus they are unknown and unpredictable to attackers. Just as its name implies, the sub-MACs of the CRC-NTMAC are replaced by the Cyclic Redundancy Checks (CRCs). In the CRC-NTMAC, the concatenated sub-MACs are encrypted by a secure block cipher with a shared key. The encryption stage and random partition make the CRC-NTMAC secure.

Fourthly, a modified CRC-NTMAC, called image CRC-NTMAC, is presented to ensure the credibility of multimedia, such as images. The image CRC-NTMAC can accurately identify the specific regions of the image that have been modified and visibly display the authentication result. Moreover, tolerance to low rate random errors, often allowed with multimedia objects, and sensitivity to the high noise (as in a forgery) enable the CRC-NTMAC to distinguish between malicious forgeries and minor communication errors.

Fifthly, the BCH-NTMAC is proposed by improving on the recently developed CRC-NTMAC and NTMAC. Similar to the CRC-NTMAC and the NTMAC, the BCH-NTMAC can tolerate a modest number of errors and keep quite a low collision rate as does the CRC-NTMAC. Most importantly, it provides a much better error number estimate than either the CRC-NTMAC or the NTMAC. Similar to the CRC-NTMAC, the BCH-NTMAC is not based on cryptographic hash functions. The security is ensured by random partitions and block cipher encryption.

Finally, based on these accomplishments, we propose some problems for future research, including probability analysis of error estimates, some new methods for helping the NTMAC family correct errors, applications other than image authentication.