CS 290T Computational Algebra
Winter Term 2016 - EnrlCd: 57968
Department of Computer Science
University of California Santa Barbara
- Instructor: Professor Çetin Kaya Koç
→ Koç is pronounced as "Coach"
- Schedule and Classroom:
Monday and Wednesdays 5:00-6:50pm; Phelps 2510
- Office Hours: Tuesdays 3:00-6:00pm
→ Office: HFH 1119
- Check the class website, the
Piazza page for cs290t,
and/or your email once a day
- The grades: Winter16.htm →
The "Code" is equal to the perm number mod 9973 for regular students
and the last 3 digits of the registration number for extension students
The participating students are expected to write a short (3-5 pages)
paper on certain fundamental or algorithmic aspects, or applications
of computational algebra. The paper is to be written in LaTeX2e.
The project paper is graded as: 50% on the difficulty of the subject
and 50% on the clarity of the presentation. The deadline for the paper
is the Sunday of the Final's Week (March 20).
- Sample Project Paper Files:
There will be 4-6 homework assignments.
Either, email me an electronic copy or bring a paper copy to the class.
Electronic copy of your homework can be in Text or PDF.
You could also scan/pdf your handwritten work;
however, do not send (low-resolution or small) phone-camera images
under any circumstances!
Put your name inside the file and also make the
file name as your last name, followed by homework number,
for example: green-hw01.pdf
- Homework Assignment 01:
hw01.pdf - Due 5pm Wednesday January 20
- Homework Assignment 02:
hw02.pdf - Due 5pm Wednesday February 10
- Homework Assignment 03:
hw03.pdf - Due 5pm Wednesday March 9
Weekly Course Plan
All course related papers, presentations and weekly slides
are (will be) here: docx
- Week 01 (Jan 4 and 6): Solving Equations over Finite Fields
- Week 02 (Jan 11 and 13): DFT over Finite Fields and its Applications
- Jan 15 is a school holiday.
- Weeks 03 and 04 (Jan 20 and 25): Boolean Functions for Cryptography
- Weeks 04 and 05 (Jan 27, Feb 1 and 3):
Random Number Generators (w04)
- Week 06 (Feb 8): Physical Unclonable Functions
- Week 06 (Feb 10): LLL Algorithm
- Feb 15 is a school holiday.
- Week 07 (Feb 17): Fault-Tolerant Computation
- Week 08 (Feb 22): Cryptographic Algorithms on FPGAs
- Week 08 (Feb 24): Proactive Secret Sharing and MPC Protocols
Karim El Defrawy
- Week 09 (Feb 29): Primality Testing Algorithms
- Week 09 and 10 (Mar 2, 7, 9): Project meetings in
Trailer 935 Room 101c
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 and Details
- Solving Equations over Finite Fields and Rings:
Solving of Linear Equations over Z_n or GF(p). Chinese Remaindering for
Composite Modulus. Dixon's Algorithm for GF(p^k).
Gaussian Elimination over GF(2). Applications. [2 lectures]
- DFT over Finite Fields and its Applications:
Definition and Fundamentals. Multiplication and Convolution.
- Boolean Functions for Cryptography:
Finite Fields. Representations. Cryptographic Properties. Nonlinearity.
Resilience. Generalizations to Vectorial Functions. Highly
Nonlinear Vectorial Boolean Functions. APN Functions. [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.
- Primality Testing and Prime Generation:
Fermat's Method. Discrete Squareroots. Miller-Rabin Method.
Solovay-Strassen Method. AKS Method.
- Physical Unclonable Functions (PUFs):
PUF Class Construction and Properties. PUF Response
Distances. PUF Experiment. Helper Data Algorithm. Fuzzy
Extractor. Information Reconciliation. Intrinsic PUF Examples.
PUF for Identification and Authentication. [1 lecture]
- 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. [1 lecture]
- Fault-Tolerant Computation:
Definition. Error-Correcting Codes. State-of-the-Art Methods.
Application Areas. Fault-Tolerant Galois Field Multiplication.
- 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]
- Post-Quantum Cryptography:
Lattice-based, Multivariate, Hash-based, and Code-based Cryptography.
Supersingular Elliptic Curve Isogeny Cryptography.
Security Reductions. Key Sizes. [4 lectures]
Çetin Kaya Koç. Open Problems in Mathematics and
Computational Science. Springer, 2014.
Martin Dietzfelbinger. Primality Testing
in Polynomial Time. Springer, 2004.
Victor Shoup. A Computational Introduction to Number Theory
and Algebra. Version 2, 2008.
John Scherk. Algebra: A Computational Introduction. 2009.
Integrity at UCSB ←
Dr. Çetin Kaya Koç