Show simple item record

dc.contributor.advisorSundaresan, Rajesh
dc.contributor.authorHanawal, Manjesh Kumar
dc.date.accessioned2011-04-01T05:28:07Z
dc.date.accessioned2018-07-31T04:50:12Z
dc.date.available2011-04-01T05:28:07Z
dc.date.available2018-07-31T04:50:12Z
dc.date.issued2011-04-01
dc.date.submitted2009-02
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/1106
dc.description.abstractThe problem of guessing a random string is studied. It arises in the analysis of the strength of secret-key cryptosystems against guessing attacks. Expected number of guesses, or more generally moments of the number of guesses needed to break the cryptosystem grow exponentially with the length of the string. This thesis studies the rate of exponential growth of these moments using the theory of large deviations. A closer elation between guessing and compression is first established. For systems with large key rates, it is shown that if the source’s sequence of so-called information spectrum random variables satisfies the large deviation property with a certain rate function, then the limiting guessing exponent exists and is a scalar multiple of the Legendre-Fenchel dual of the rate function. This is then used to rederive several prior results. The large deviations approach brings to light the relevance of information spectrum in determining guessing exponents. For systems with key-rate constraints, bounds are derived on the limiting guessing exponents for general sources. The obtained bounds are shown to be tight for stationary memoryless, Markov, and unifilar sources, thus recovering some known results. The bounds are obtained by establishing a close relationship between error exponents and correct decoding exponents for fixed rate source compression on the one hand and exponents for guessing moments on the other.en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG23070en_US
dc.subjectCryptographyen_US
dc.subjectAccess Controlen_US
dc.subjectRandom Stringen_US
dc.subjectCompression Of Informationen_US
dc.subjectInformation Theoryen_US
dc.subjectCoding Theoryen_US
dc.subjectLarge Deviations Theoryen_US
dc.subjectGuessing and Compressionen_US
dc.subject.classificationComputer Scienceen_US
dc.titleGuessing And Compression : A Large Deviations Approachen_US
dc.typeThesisen_US
dc.degree.nameMSc Enggen_US
dc.degree.levelMastersen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record