Record Details

Guessing And Compression : A Large Deviations Approach

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Guessing And Compression : A Large Deviations Approach
 
Creator Hanawal, Manjesh Kumar
 
Subject Cryptography
Access Control
Random String
Compression Of Information
Information Theory
Coding Theory
Large Deviations Theory
Guessing and Compression
Computer Science
 
Description 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.
 
Contributor Sundaresan, Rajesh
 
Date 2011-04-01T05:28:07Z
2011-04-01T05:28:07Z
2011-04-01
2009-02
 
Type Thesis
 
Identifier http://hdl.handle.net/2005/1106
 
Language en_US
 
Relation G23070