Information theoretic cryptanalysis and reliable communications under codebook mismatch

Abstract

In this thesis, usage of typicality in two diffrent concepts is investigated. In the first concept, a new approach on cryptanalysis is proposed where the goal is to explore the fundamental limits of a specific class of attacks against a particular cryptosystem. As a first step, the approach is applied on ABSG, which is an LFSR-based stream cipher where irregular decimation techniques are utilized. Consequently, under a set of mild assumptions, which are common in cryptanalysis, the tight lower bound on the al- gorithmic complexity of successful exhaustive search type Query-Based Key-Recovery attacks are derived where the proofs rely on the concept of typicality for single random variable. In the second concept, we define a new problem, which we called \code- book mismatch problem", which is a generalization of the traditional point-to-point to communication setup. Under independent identically distributed encoder codewords assumption, it is proven that the operational capacity of the system is equal to the information capacity of the system, defined as maxp(x) I(U; Y ).