National Technical University of Athens (NTUA)
Συνδυαστική θεωρία σχεδιασμών, κωδίκων και κρυπτογραφίας
Abstract
dc:descriptionMy Ph.D. Thesis involves the study of combinatorial constructions for several classes of combinatorial designs and the development of relevant algorithms that are applicable to the fields of Coding Theory and Cryptography. In the first part of the Thesis, entitled ``Combinatorial Design Theory'', different classes of sequences with constant autocorrelation and combinatorial designs are studied, new families of these combinatorial structures are introduced, theorems related to the necessary and sufficient conditions are proved, and a software for searching the later combinatorial objects is implemented. In addition, a series of competent evolutionary algorithms is developed for finding new sequences and designs. In particular, a new method for verifying the autocorrelation property of compatible sequences is presented. A worst-case complexity analysis shows that the new criterion is efficient for sequences of small weight. This method in addition allows the formulation of a series of combinatorial optimization algorithms (mGA, FmGA, OmeGA) for finding new weighing matrices, whereas the sequences are used as intermediate steps in the construction of the designs. Furthermore, new inequivalent Hadamard matrices are constructed from complementary sequences using a software developed specifically for this purpose. Moreover, new infinite families of orthogonal designs and weighing matrices are constructed from complementary sequences, which update the second edition of the CRC Handbook of Combinatorial Designs in several cases. Finally, a new measure for ternary complementary pairs, called ζ-efficiency is introduced and its consequences in Design Theory are thoroughly studied. In the second part, entitled ``Coding Theory'', some special families of codes are studied, namely the self-dual and quasi-cyclic codes, construction methods of the later codes are proposed using designs and genetic algorithms are utilized in the case of the quasi-cyclic codes for determining their parameters. In particular, new construction methods of self-dual codes over GF(p) using skew-Hadamard matrices are proposed, and a complete study over small finite fields is given. Moreover, new large self-dual codes over GF(5) are found for the first time, while over GF(7) a new [56,28,17] self-dual code is presented having the highest minimum distance among the class of self-dual codes. Furthermore, a systematic construction of MDS self-dual codes over large finite fields that arose from solutions of Diophantine equations is given. Last but not least, binary quasi-cyclic codes are studied from statistical designs and a fundamental relation between an optimal class of the later designs and complementary dual quasi-cyclic codes is illustrated. In the third and final part, entitled ``Cryptography'', private-key cryptosystems that arose from classes of combinatorial designs are proposed, and families of secret-sharing schemes are constructed with the aid of Hadamard designs. In particular, the new symmetric block ciphers are constructed from Hadamard matrices and Plotkin arrays. The mathematical structure of the later designs allows the design of cryptographic algorithms suitable for the encryption and decryption of a message. An extended cryptanalysis of these ciphers, shows that the ciphers are robust under certain types of attacks. Moreover, two-part secret sharing schemes are developed from Hadamard designs, which under certain conditions provide perfect secrecy.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2011
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Simos, Dimitrios
- Σίμος, Δημήτριος
Subjects
dc:subject × 20- Συνδυαστικοί σχεδιασμοί
- Ακολουθίες
- Αυτοσυσχέτιση
- Συνδυαστικοί αλγόριθμοι βελτιστοποίησης
- Αυτοδυϊκοί κώδικες
- Πολυκυκλικοί κώδικες
- Κρυπτογραφικά σχήματα
- Κρυπτανάλυση
- Combinatorial designs
- Sequences
- Autocorrelation
- Combinatorial optimization algorithms
- Self-dual codes
- Quasi-cyclic codes
- Encryption schemes
- Cryptoanalysis
- Φυσικές Επιστήμες
- Μαθηματικά
- Natural Sciences
- Mathematics
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/25540