## A generalized linear complexity

dc.creator | Stamp, Mark Steven | |

dc.date.available | 2011-02-19T00:41:28Z | |

dc.date.issued | 1992-05 | |

dc.degree.department | Mathematics | en_US |

dc.description.abstract | Certain cryptographic applications require pseudo-random sequences which are "unpredictable," in the sense that recovering the sequence from a short captured segment is computationally infeasible. Such sequences are said to be cryptographically strong. Due to the Berlekamp-Massey algorithm, a cryptographically strong sequence must have a high linear complexity, where the linear complexity of a sequence s is the minimum number of stages in a linear feedback shift register capable of generating s. However, trivial examples exist which show that a high linear complexity does not insure that a sequence is cryptographically strong. In this thesis a generalized linear complexity—the k-complexity—is proposed and analyzed. The k-complexity of s is defined to be the smallest linear complexity that can be obtained by altering any k or fewer elements of s. The k-complexity can be interpreted as a "strong" measure of the complexity of a sequence, or as a worst-case measure of the linear complexity when k or fewer errors occur. It is shown that the k-complexity gives more information on the cryptographic strength of a sequence than other previously suggested methods. An efficient algorithm for finding the k-complexity in the special case where 5 is a periodic binary sequence with period length 2" is given. This algorithm generalizes a linear complexity algorithm of Games and Chan. The computational complexity of the general case is also considered. The k-complexities of a particular class of binary sequences—the de Bruijn sequences—are analyzed and several computational results are given. In addition, a new class of binary sequences which appear to have good k-complexity properties is presented. | |

dc.format.mimetype | application/pdf | |

dc.identifier.uri | http://hdl.handle.net/2346/21994 | en_US |

dc.language.iso | eng | |

dc.publisher | Texas Tech University | en_US |

dc.rights.availability | Unrestricted. | |

dc.subject | Cryptography | en_US |

dc.subject | Sequences (Mathematics) | en_US |

dc.subject | Linear orderings | en_US |

dc.subject | Complexes | en_US |

dc.title | A generalized linear complexity | |

dc.type | Dissertation | |

thesis.degree.department | Mathematics | |

thesis.degree.department | Mathematics and Statistics | |

thesis.degree.discipline | Mathematics | |

thesis.degree.grantor | Texas Tech University | |

thesis.degree.level | Doctoral | |

thesis.degree.name | Ph.D. |

##### Files

##### Original bundle

1 - 1 of 1