CS 290T Computational Algebra
Winter Term 2016  EnrlCd: 57968
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:006:50pm; Phelps 2510
 Office Hours: Tuesdays 3:006: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 (35 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 46 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 (lowresolution or small) phonecamera 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: greenhw01.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): FaultTolerant 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 errorcorrecting 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. MillerRabin Method.
SolovayStrassen 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.
AreaTime Tradeoffs. [1 lecture]
 FaultTolerant Computation:
Definition. ErrorCorrecting Codes. StateoftheArt Methods.
Application Areas. FaultTolerant 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]
 PostQuantum Cryptography:
Latticebased, Multivariate, Hashbased, and Codebased 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
Relevant Journals, Conferences & Archives
Grading
 Homework Assignments: 60 %
 Project Paper: 40 %
Prerequisites
This class is open to all graduate students.
Undergraduate students should contact the instructor.
Academic
Integrity at UCSB ←
Dr. Çetin Kaya Koç
