IISc Logo    Title

etd AT Indian Institute of Science >
Division of Electrical Sciences >
Electrical Communication Engineering (ece) >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2005/1106

Title: Guessing And Compression : A Large Deviations Approach
Authors: Hanawal, Manjesh Kumar
Advisors: Sundaresan, Rajesh
Keywords: Cryptography
Access Control
Random String
Compression Of Information
Information Theory
Coding Theory
Large Deviations Theory
Guessing and Compression
Submitted Date: Feb-2009
Series/Report no.: G23070
Abstract: The 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.
URI: http://etd.iisc.ernet.in/handle/2005/1106
Appears in Collections:Electrical Communication Engineering (ece)

Files in This Item:

File Description SizeFormat
G23070.pdf478.78 kBAdobe PDFView/Open

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.


etd@IISc is a joint service of SERC & IISc Library ||
|| Powered by DSpace || Compliant to OAI-PMH V 2.0 and ETD-MS V 1.01