Unconditionally Secure Approximate Message Authentication

Authors

Dongvu Tonien, University of CalgaryFollow
Reihaneh Safavi-Naini, University of WollongongFollow
Peter Nickolas, University of WollongongFollow
Yvo Desmedt, University of LondonFollow

RIS ID

32661

Publication Details

Tonien, D., Safavi-Naini, R., Nickolas, P. & Desmedt, Y. (2009). Unconditionally Secure Approximate Message Authentication. In 2nd International Workshop on Coding and Cryptology, IWCC 2009, 1-5/06/2009, Zhangjiajie. Lecture Notes in Computer Science, 5557 233-247.

Abstract

Approximate message authentication codes (AMAC) arise naturally in biometric and multimedia applications where plaintexts are fuzzy and a tagged message (x, t) where t is the calculated tag for a message x that is close to x should pass the verification test. Fuzziness of plaintexts can be due to a variety of factors including applying acceptable transforms such as compression and decompression to data, or inaccuracy of sensors in reading biometric data. This paper develops a framework for approximate message authentication systems in unconditionally security setting. We give formal definition of AMAC and analyze two attacks, impersonation attack and substitution attack.We derive lower bounds on an opponents deception probability in these attacks under the assumption that all keys are equiprobable. Our bounds generalize known combinatorial bounds in classical authentication theory.