Cyclic Codes: Low-Weight Codewords and Locators

Cycle 28th Oral Defence of the Phd Thesis
16 marzo 2016
16 marzo 2016
Contatti: 
Staff Dipartimento di Matematica

Università degli Studi Trento
38123 Povo (TN)
Tel +39 04 61/281508-1625-1701-3898-1980.
dept.math [at] unitn.it

Place: Seminar Room -  Department of Mathematics - Via Sommarive 14 - Povo - Trento
at 09.00 a.m.

  • Claudia Tinnirello - PhD in mathematics

Abstract:
Error correcting codes has become an integral part of the design of reliable data transmissions and storage systems. They are also playing an increasingly important role for other applications such as the analysis of pseudorandom sequences and the design of secure cryptosystems. Cyclic codes form a large class of widely used error correcting codes, including important codes such as the Bose-Chaudhuri-Hocquenghem (BCH) codes, quadratic residue (QR) codes and Golay codes.
In this seminar I will tackle two problems related to cyclic codes: finding low-weight codewords and decoding.
The first part of the talk is devoted to some results concerning efficient bounded distance decoding (BDD) for cyclic codes. More precisely I will introduce the Orsini-Sala decoding algorithm and the notion of general error locator polynomial, and show some results on the structure of this polynomial.
Computing efficiently low-weight codewords of a cyclic code is often a key ingredient of correlation attacks to LFSR-based stream ciphers. The best general purpose algorithm is based on the generalized birthday problem. In the second part of the talk I will describe an alternative approach based on discrete logarithms which has - in some cases relevant for applications - much lower memory complexity requirements and a comparable time complexity.

Supervisor: Massimiliano Sala