CS 290T Computational Algebra

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: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: Mustafa Parlak

  • 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

    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ç