290T - Computational Algebra

This course cover a collection of research topics in computational algebra and number theory, as related to cryptography, cryptanalysis, security, and error-correcting codes. The students are expected to follow the course presentations, and return homework assignments. Additionally, each student is required to pick a particular area and write a short paper or presentation, covering the fundamentals of the area and describing possible open problems.

Topics

• Boolean Functions and Vectorial Boolean Functions for Cryptography: Finite Fields. Representations. Cryptographic Properties. Nonlinearity. Resilience. Generalizations to Vectorial Functions. Highly Nonlinear Vectorial Boolean Functions. APN Functions. [2 lectures]
• Primality Testing and Prime Generation: Fermat's Method. Discrete Squareroots. Miller-Rabin Method. Solovay-Strassen Method. AKS Method. [2 lectures]
• Physical Unclonable Functions (PUFs): PUF Classn Construction and Properties. PUF Response Distances. PUF Experiment. Helper Data Algorithm. Fuzzy Extractor. Information Reconciliation. Intrinsic PUF Examples. PUF for Identification and Authentication. [2 lectures]
• Random Number Generators: Introduction to Randomness. Ideal Random Numbers. Random Number Generators. True Random Number Generators. Pseudorandomness. Pseudorandom (Deterministically Random) Number Generators. Entropy. Statistical Tests. NIST Certification. AIS31 Certification. [4 lectures]
• Modeling Computation: Modeling Computers. Finite Automata. Finite State Machines with and without Outputs. Language Recognition. Regular Expressions. VLSI Models of Computation. Design of a Simple CPU. Application Specific Instruction Set Processors. Area-Time Tradeoffs. [2 lectures]
• Cryptographic Algorithms on FPGAs: Digital Design. Reconfigurable Hardware. FPGAs. Digital IC Power. Finite Field Arithmetic Realizations. Modular Multiplication. Elliptic curve algorithms. Power Analysis. [2 lectures]