Error-Correcting Codes and Lattices

Lattices and Error-Correcting Codes

Prof. Muli Safra

1. SYLLABUS: 0368-3084

1. ECC

- Linear codes - Distance and dimension.

- Encoding and decoding.

- The generator matrix.

- The parity-check matrix.

- Hamming codes (distance, dimension, encoding, decoding, perfect)

- Hadamard codes (distance, dimension, encoding, decoding)

- Reed Solomon and Reed Muller codes

2. Lattices

The Mathematical basic behind Lattices

- Covolume of a lattice

- Minkowski: first and second theorems

- Application to shortest vector problem

- Covering radius.

Computational Complexity

- Classical computational problems on lattices

- The LLL algorithm

- Worst-case to average-case reductions

Cryptographic Applications

- Hashing and Encryption

- The Learning with Errors Problem

- Computing over Encrypted Data