Back to search

National and Kapodistrian University of Athens

Τεχνικές επεξεργασίας σήματος στην κρυπτογραφία

Abstract

dc:description

Cryptography is the study of mathematical techniques concerning telecommunication security stream ciphers comprise an important class of cryptographic algorithms. Shift registers with linear (LFSR) or nonlinear (FSR) feedback are the basic building blocks in stream ciphers. The security of these systems is mainly attributed to pseudorandom characteristics of the keystreams. Amongst the cryptographic measures of a sequence is its complexity defined as the length of the shortest FSR that generates the sequence. Especially the linear complexity is important for assessing resistance to cryptanalytic attacks like the Berlekamp-Massey algorithm (BMA). Hence high linear complexity is prerequisite for keystreams. Such sequences are generated by applying nonlinear Boolean functions either as filters or combiners. However resistance of cryptosystems to various attacks is also associated with properties of the functions used. Determining the connections between several cryptographic criteria of sequences remains an open problem. In this thesis, pseudorandom properties of sequences are studied, by using system theoretic concepts. A new unified approach for analyzing the linear complexity is developed via controllability and observability conditions applied to sequence generators. A new generalized Fourier transform is introduced allowing the generation of sequences with prescribed linear complexity. Moreover new classes of nonlinear filters are constructed which guarantee high values of the linear complexity. Furthermore the nonlinear complexity of binary sequences and its connections to other cryptographic criteria is studied. A new efficient recursive algorithm is presented, which produces the minimal FSR of a given sequence, thus generalizing the BMA to the nonlinear case. Connections between nonlinear complexity and Lempel-Ziv complexity are also established. Moreover a lower bound for the Lempel-Ziv compression ratio of a sequence is proved which depends on its nonlinear complexity. Finally the problem of computing best quadratic approximations of Boolean functions is studied. Efficient formulas for computing such approximations for a class of functions with degree 3 and 4 are proved. The methodology is independent from the number of variables and reveals new design principles for cryptographic functions. An analysis of recently proposed cryptographic functions indicates potential weaknesses if construction parameters are not properly chosen.

Degree

thesis:*
Grantor dc:publisher
National and Kapodistrian University of Athens
Year dc:date
2007

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Limniotis, Konstantinos
  • Λιμνιώτης, Κωνσταντίνος

Subjects

dc:subject × 20

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/23012

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Limniotis, Konstantinos; Λιμνιώτης, Κωνσταντίνος. Τεχνικές επεξεργασίας σήματος στην κρυπτογραφία. National and Kapodistrian University of Athens, 2007. http://hdl.handle.net/10442/hedi/23012