MATH4260
Coding theory and cryptography
Linear, cyclic, BCH and evaluation codes, coding bounds, finite fields, information theory and noisy channels, classical and public-key cryptography, key agreement and authentication.
Your progress
0/ 32 sections marked complete
Next section: Distance, linear codes and syndromes
Completion marks are saved in this browser.
This course in the web
In the MATH4260 notes
- Theorem cards
- 82
- Definitions
- 48
- Counterexamples
- 34
- Concept lenses
- 22
- Histories of ideas
- 6
- Proof X-rays
- 32
Sections with a history of an idea
- Weight enumerators and MacWilliams duality1.4
- Entropy and binary prefix codes3.1
- ElGamal encryption and a conditional secrecy proof4.2
- Schnorr identification and nonce reuse4.4
- Matrix ciphers, periodic keys and information leakage5.2
- Polynomial evaluation, interpolation and optimal distance16.1
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 32 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
In the webTheorem cards 82 · Definitions 48 · Counterexamples 34 · Concept lenses 22 · Histories of ideas 6 · Proof X-rays 32
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 32 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
Chapter 1 · 4 sections
Linear codes
Distance, error correction and syndromes over the binary field.
Theorems 14 · Definitions 8Counterexamples 4Lenses 4History 1Proof X-rays 5
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
Distance, linear codes and syndromes
Derive correction guarantees and syndrome decoding for binary linear codes.
- 1.2
Extended Hamming codes and SECDED
Derive the extended Hamming syndrome decoder, its single-error correction and double-error detection guarantee, and the limits outside that guarantee.
- 1.3
Packing, covering and the limits of code size
Prove finite and asymptotic Hamming, Gilbert–Varshamov and Plotkin bounds, separating existence, linearity and efficient construction.
- 1.4
Weight enumerators and MacWilliams duality
Derive the dual weight transform by additive-character orthogonality, obtain exact coefficient and moment constraints, and test candidate code distributions.
Chapter 2 · 2 sections
2. Cyclic codes
Consecutive roots and a finite syndrome decoder.
Theorems 4Counterexamples 2Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
Consecutive roots and a cyclic decoder
Prove a consecutive-root distance bound and decode a binary length-seven cyclic code.
- 2.2
Cyclic codes as polynomial ideals
Relate cyclic shifts to multiplication modulo x^n−1 and construct a binary cyclic code.
Chapter 3 · 4 sections
3. Information theory
Entropy and binary prefix codes for finite sources.
Theorems 13 · Definitions 11Counterexamples 6Lenses 1History 1Proof X-rays 4
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Entropy and binary prefix codes
Derive the entropy lower bound and a finite-source prefix-code construction.
- 3.2
Huffman coding and lossless block-source rates
Prove the greedy prefix-code algorithm, its exact cost certificate and entropy bounds, then explain how independent blocks approach the source entropy.
- 3.3
Noisy channels, mutual information and a decoding converse
Measure the information retained by a finite channel and prove a necessary rate bound for reliable binary communication.
- 3.4
The coding theorem for a finite memoryless channel
Prove capacity achievability by information-density threshold decoding and a weak converse for arbitrary input correlations.
Chapter 4 · 4 sections
4. Public-key arithmetic
RSA correctness and the security limits of textbook arithmetic.
Theorems 9 · Definitions 5Counterexamples 3Lenses 3History 2Proof X-rays 4
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
RSA: modular arithmetic and public-key encryption
Prove RSA correctness on all residue classes and distinguish textbook arithmetic from secure encryption.
- 4.2
ElGamal encryption and a conditional secrecy proof
Prove correctness and chosen-plaintext security under decisional Diffie–Hellman, account for bounded fair-bit sampling, and exhibit malleability.
- 4.3
RSA signatures and full-domain hashing
Define chosen-message forgery, exhibit textbook RSA attacks, and prove a conditional full-domain-hash theorem in the random-oracle model.
- 4.4
Schnorr identification and nonce reuse
Prove the correctness, extraction and honest-verifier simulation of a discrete-log identification protocol, then examine its signature transformation and nonce failure.
Chapter 5 · 2 sections
5. Classical cryptography
Affine substitutions and precise information leakage.
Theorems 6 · Definitions 4Counterexamples 2Lenses 2History 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Classical cryptography: affine ciphers and the information they preserve
Derive affine decryption, recover keys from observations, and distinguish exact leakage from statistical frequency analysis.
- 5.2
Matrix ciphers, periodic keys and information leakage
Analyze Hill and Vigenère ciphers using modular linear algebra, known plaintext and exact secrecy obstructions.
Chapter 6 · 1 section
6. Source compression
Construct optimal finite binary prefix codes.
Theorems 4 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Huffman coding and optimal prefix trees
Prove the greedy construction minimizes expected prefix-code length for a finite source.
Chapter 7 · 1 section
7. Noisy channels
Study information and error correction for a binary symmetric channel.
Theorems 2 · Definitions 2Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 7.1
A binary symmetric channel and repetition
Compute one-use mutual information and examine a finite repetition code under an explicit noise model.
Chapter 8 · 1 section
8. Secret sharing
Prove threshold reconstruction and information-theoretic privacy.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
Polynomial threshold secret sharing
Prove reconstruction and perfect privacy for a finite-field threshold scheme.
Chapter 9 · 1 section
9. Polynomial evaluation codes
Study evaluation-code distance, errors and erasures.
Theorems 2 · Definitions 2Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 9.1
Evaluation codes, errors and erasures
Derive the distance and error-erasure guarantee of a polynomial evaluation code.
Chapter 10 · 2 sections
10. Key agreement
Study modular key agreement and its security assumptions.
Theorems 4 · Definitions 3Counterexamples 3Lenses 2Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 10.1
Diffie–Hellman key agreement
Derive modular key agreement and distinguish its arithmetic from authentication and security.
- 10.2
Diffie–Hellman security experiments
Compare passive security experiments, computational assumptions, and active substitution.
Chapter 11 · 1 section
11. Message authentication
Study a one-time authentication experiment and its limits.
Theorems 1 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 11.1
A one-time authentication experiment
Prove a substitution bound for a one-time affine tag and examine key reuse.
Chapter 12 · 1 section
12. Decoding limits
Relate finite-alphabet estimation error to conditional entropy.
Theorems 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 12.1
Error probability and conditional entropy
Prove a finite-alphabet Fano bound and interpret its limitations.
Chapter 13 · 1 section
13. Coding bounds
Compare greedy existence and Hamming packing bounds.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 13.1
Greedy codes and Hamming bounds
Construct a finite code greedily and compare existence and packing bounds.
Chapter 14 · 3 sections
Finite fields
Construction, structure and discrete logarithms in finite fields.
Theorems 9 · Definitions 5Counterexamples 3Lenses 3Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 14.1
Why finite fields exist and how their subfields fit together
Construct finite fields from irreducible polynomials and prove prime-power size, cyclic units, Frobenius periods and subfield classification.
- 14.2
Compute and construct finite fields with certified tests
Implement polynomial-residue arithmetic, prove an irreducibility test, and give bounded-randomness field construction with an explicit failure probability.
- 14.3
Element orders, roots of unity and discrete logarithms
Construct roots of a specified order and prove baby-step giant-step and prime-power discrete-log algorithms with explicit cost assumptions.
Chapter 15 · 2 sections
BCH codes
Designed distance and syndrome decoding of BCH codes.
Theorems 4 · Definitions 4Counterexamples 2Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 15.1
Consecutive roots and the BCH distance guarantee
Construct cyclic codes from extension-field roots, prove the Vandermonde distance bound, and build a binary code of length fifteen.
- 15.2
Locate two bit errors from BCH syndromes
Derive a complete two-error decoder for the binary length-fifteen BCH code and distinguish guaranteed correction from behavior outside the error radius.
Chapter 16 · 2 sections
Evaluation codes
Reed-Solomon codes and Berlekamp-Welch decoding.
Theorems 5Counterexamples 2Lenses 2History 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 16.1
Polynomial evaluation, interpolation and optimal distance
Construct Reed–Solomon codes, prove their parameters and erasure recovery, and derive parity checks from interpolation.
- 16.2
Unknown errors become a linear system
Prove polynomial-time unique Reed–Solomon decoding with a monic error locator, including failure certificates and unused error budget.