[inria-00261827, v1] Formal Approaches to Information-Hiding (Tutorial )

Author manuscript, published in "Trustworthy Global Computing 4912 (2007) 347-362" DOI : 10.1007/978-3-540-78663-4_23FormalapproachestoInformation Hiding?–Atutorial –RomainBeauxis KonstantinosChatzikokolakis CatusciaPalamidessi´INRIAandLIX,EcolePolytechnique,Palaiseau,France{beauxis,kostas,catuscia}@lix.polytechnique.frPrakashPanangadenMcGillUniversity,Montreal,Canada prakash@cs.mcgill.caAbstract. Inthissurveypaperweconsidertheclassofprotocolsforinformation hiding which use randomization to obfuscate the link between the observablesand the information to be protected. We focus on the problem of formalizing thenotionofhiding,andverifyingthatagivenprotocolachievesthein tendeddegreeofprotection.Withoutthepretenseofbeingomni comprehensive,wereviewthemainapproachesthathavebeenexploredinliterature:possibilistic,probabilistic,information theoretic,andstatistical.1 IntroductionDuring the last decade, internet activities have become an important part of many peo ple’s lives. As the number of these activities increases, there is a growing amount ofpersonal information about the users that is stored in electronic form and that is usu ally transferred using public electronic means. This makes it feasible and often easy tocollect,transferandprocessahugeamountofinformationaboutaperson.Asaconse quence,theneedformechanismstoprotectsuchiscompelling.Arecentexampleofsuchprivacyconcernsaretheso called“biometric”passports.Thesepassports ...