CS 290T Computational Algebra
Department of Computer Science
University of California Santa Barbara
http://koclab.cs.ucsb.edu/teaching/ca
Announcements
- 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
Project Paper
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.
- Sample Project Paper Files:
paper
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).
Homework Assignments
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
(w01)
- Week 02 (Jan 11 and 13): DFT over Finite Fields and its Applications
(w02)
- Jan 15 is a school holiday.
- Weeks 03 and 04 (Jan 20 and 25): Boolean Functions for Cryptography
(w03)
Invited Speaker:
Zülfükar Saygı
- Weeks 04 and 05 (Jan 27, Feb 1 and 3):
Random Number Generators (w04)
Invited Speakers:
İhsan Çiçek
and
Sam Green
- Week 06 (Feb 8): Physical Unclonable Functions
(w06)
Invited Speaker:
İsmail San
- Week 06 (Feb 10): LLL Algorithm
Invited Speaker:
Marc Joye
- Feb 15 is a school holiday.
- Week 07 (Feb 17): Fault-Tolerant Computation
(w07)
Invited Speaker:
İsmail San
- Week 08 (Feb 22): Cryptographic Algorithms on FPGAs
(w08a)
Invited Speaker:
Karim El Defrawy
- Week 08 (Feb 24): Proactive Secret Sharing and MPC Protocols
(w08b)
Invited Speaker:
Karim El Defrawy
- Week 09 (Feb 29): Primality Testing Algorithms
(w09)
- Week 09 and 10 (Mar 2, 7, 9): Project meetings in
Trailer 935 Room 101c
Description
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.
[4 lectures]
- Primality Testing and Prime Generation:
Fermat's Method. Discrete Squareroots. Miller-Rabin Method.
Solovay-Strassen Method. AKS Method.
[1 lecture]
- 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.
[1 lecture]
- 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]
Books
Çetin Kaya Koç. Open Problems in Mathematics and
Computational Science. Springer, 2014.
URL
Martin Dietzfelbinger. Primality Testing
in Polynomial Time. Springer, 2004.
URL
Victor Shoup. A Computational Introduction to Number Theory
and Algebra. Version 2, 2008.
PDF
John Scherk. Algebra: A Computational Introduction. 2009.
PDF
Academic
Integrity at UCSB ←
Dr. Çetin Kaya Koç
|
