Markov Modelling of Fingerprinting Systems for Collision Analysis. (12th March 2008)

• Record Type: Journal Article
• Authors: Hurley, Neil J.; Balado, Félix; Silvestre, Guénolé C. M.
• Other Names: Voloshynovskiy S. Academic Editor.
• Is Part Of: EURASIP journal on information security. Volume 2008(2008)
• Publication Date: 2008-03-12
• Subjects: Computer security -- Periodicals; Computer networks -- Security measures -- Periodicals; Data encryption (Computer science) -- Periodicals; Cryptography -- Periodicals; 005.8
• DOI: 10.1155/2008/195238
• Languages: English
• ISSNs: 1687-417X

Abstract

Abstract : Multimedia fingerprinting, also known as robust or perceptual hashing, aims at representing multimedia signals through compact and perceptually significant descriptors (hash values). In this paper, we examine the probability of collision of a certain general class of robust hashing systems that, in its binary alphabet version, encompasses a number of existing robust audio hashing algorithms. Our analysis relies on modelling the fingerprint (hash) symbols by means of Markov chains, which is generally realistic due to the hash synchronization properties usually required in multimedia identification. We provide theoretical expressions of performance, and show that the use ofM -ary alphabets is advantageous with respect to binary alphabets. We show how these general expressions explain the performance of Philips fingerprinting, whose probability of collision had only been previously estimated through heuristics.