Number Theory And Cryptography Assignment Sheet


Current Courses: Spring 2017

  • Mathematics 6180. Algebraic Number Theory.

            Introduces number fields and completions, norms, discriminants and differents, finiteness of the ideal class group, Dirichlet's unit theorem, decomposition of prime ideals in extension fields, decomposition, and ramification groups. Prereqs., MATH 6110 and 6140. Undergraduates must have approval of the instructor.

Past Courses at CU Boulder

  • Mathematics 4440/5440. Cryptography and Coding Theory. Fall 2016.

            Gives an introduction, with proofs, to the algebra and number theory used in coding and cryptography. Basic problems of coding and cryptography are discussed; prepares students for the more advanced ECEN 5032 and 5682. Prereq., MATH 3130. Recommended prereqs., MATH 3110 and 3140.

    • Monday, Wednesday and Friday, 1:00 - 1:50 pm, ECCR 139.
  • Mathematics 2001. Introduction to Discrete Mathematics. Fall 2016.

            Introduces the ideas of rigor and proof through an examination of basic set theory, quantification theory, elementary counting, discrete probability, and additional topics. Prereq., MATH 1300 or APPM 1350.

    • Monday, Wednesday and Friday, 2:00 - 2:50 pm, ECCR 139.
  • Mathematics 8114. Topics in Number Theory: The Arithmetic of Kleinian Groups. Spring 2016.

            Please see the Course Announcement.

  • Mathematics 3170. Introduction to Combinatorics, Fall 2015.

            Covers basic methods and results in combinatorial theory. Includes numeration methods, elementary properties of functions and relations, and graph theory. Emphasizes applications. Prerequisites: Requires prerequisite course of MATH 2001 (minimum grade C-).

    • Monday, Wednesday and Friday, 11:00 - 11:50 am, ECCR 118.
  • Mathematics 2001. Introduction to Discrete Mathematics, Fall 2015.

            Introduces the ideas of rigor and proof through an examination of basic set theory, quantification theory, elementary counting, discrete probability, and additional topics. Prereq., MATH 1300 or APPM 1350.

    • Monday, Wednesday and Friday, 1:00 - 1:50 pm, ECCR 108.
  • Mathematics 2001. Introduction to Discrete Mathematics, Spring 2015.

            Introduces the ideas of rigor and proof through an examination of basic set theory, quantification theory, elementary counting, discrete probability, and additional topics. Prereq., MATH 1300 or APPM 1350.

  • Mathematics 6130. Algebra 1, Fall 2014.

            Studies group theory and ring theory. Prerequisite, Math 3140. Undergraduates need instructor consent. Prerequisites: Restricted to graduate students only.

  • Monday, Wednesday and Friday, 9:00 - 9:50 am, KOBL 330.
  • Course website
  • FCQ Results
  • Mathematics 4440/5440. Coding and Cryptography, Spring 2014.

            Gives an introduction, with proofs, to the algebra and number theory used in coding and cryptography. Basic problems of coding and cryptography are discussed; prepares students for the more advanced ECEN 5032 and 5682. Prereq., MATH 3130. Recommended prereqs., MATH 3110 and 3140.

    • Monday, Wednesday and Friday, 2:00 - 2:50 pm, FLMG 156 (changed to ECCR 118).
    • Mathematics 3130. Linear Algebra, Fall 2013.

              Examines basic properties of systems of linear equations, vector spaces, linear independence, dimension, linear transformations, matrices, determinants, eigenvalues, and eigenvectors. Prereq., MATH 2300 or APPM 1360. Credit not granted for this course and APPM 3310.

    • Mathematics 6110. Introduction to Number Theory, Fall 2013

              Examines divisibility properties of integers, congruencies [sic], diophantine equations, arithmetic functions, quadratic residues, distribution of primes, and algebraic number fields. Prereq., MATH 3140. Undergraduates must have approval of the instructor.

    • Mathematics 2300. Calculus 2, Honours Section, Fall 2012

              Continuation of MATH 1300. Topics include transcendental functions, methods of integration, polar coordinates, conic sections, improper integrals, and infinite series. Prereq., MATH 1300. Credit not granted for this course and MATH 1320 or APPM 1360.

    • Mathematics 6110. Introduction to Number Theory, Fall 2012

              Examines divisibility properties of integers, congruencies, diophantine equations, arithmetic functions, quadratic residues, distribution of primes, and algebraic number fields. Prereq., MATH 3140. Undergraduates must have approval of the instructor.



    Courses Taught at the University of British Columbia



    Courses Taught at Harvard University

    • Mathematics 129. Number Fields, Spring 2009

             Algebraic number theory: number fields, unique factorization of ideals, finiteness of class group, structure of unit group, Frobenius elements, local fields, ramification, weak approximation, adeles, and ideles.

    • Mathematics 152. Discrete Mathematics, Fall 2008

              An introduction to finite groups, finite fields, finite geometry, discrete probability, and graph theory. A unifying theme of the course is the symmetry group of the regular icosahedron, whose elements can be realized as permutations, as linear transformations of vector spaces over finite fields, as collineations of a finite plane, or as vertices of a graph. Taught in a seminar format, and students will gain experience in presenting proofs at the blackboard.



    Courses Taught at Brown University

    • Mathematics 52. Linear Algebra, Spring 2006

             Vector spaces, linear transformations, matrices, systems of linear equations, bases, projections, rotations, determinants, and inner products. Applications may include differential equations, difference equations, least squares approximations, and models in economics and in biological and physical sciences.

    • Mathematics 18. Multivariable Calculus, Fall 2004

             Three-dimensional analytic geometry. Differential and integral calculus of functions of two or three variables: partial derivatives, multiple integrals, Green's Theorem.

    • Mathematics 9. Introductory Calculus, Fall 2003

             An intensive course in the calculus of one variable including limits; differentiation; maxima and minima, and the chain rule for polynomials, rational functions, trigonometric functions, and exponential functions. Introduction of integration with applications to area and volumes of revolution.

    • Teaching Assistant, Mathematics 9 (Introductory Calculus) in Fall 2002, Spring 2003

             An intensive course in the calculus of one variable including limits; differentiation; maxima and minima, and the chain rule for polynomials, rational functions, trigonometric functions, and exponential functions. Introduction of integration with applications to area and volumes of revolution.



    Other Teaching

     

    Resources for Teachers

    If you use or adapt any of my resources, I would appreciate you letting me know. It makes me feel useful.


    Course Evaluations

    • The University of Colorado conducts the Faculty Course Questionnaire.
                  Numerical Summary accessible via CU's FCQ website: [ web ]
                  See individual courses above for full comments
    • The University of British Columbia Mathematics Department conducts departmental evaluations by email questionnaire.
                  Report for Math 317 - Fall 2010 [ pdf ]
    • The Harvard University Mathematics Department conducts departmental evaluations by email questionnaire. Math 129 had too few students to qualify for evaluation.
                  Numerical Breakdown for Math 152 - Fall 2008 [ pdf ]
                  Complete Record of Reviews for Math 152 - Fall 2008 [ pdf ]
    • The Harvard Q is a student organisation that conducts evaluations by email questionnaire.
                  Harvard Q Review for Math 152 - Fall 2008 [ numerical | comments ]
    • The Brown University Mathematics Department conducts reviews by paper questionnaire. Although I have a record of the whole stack of reviews, I've only entered the breakdown and a selection of comments into the computer. Full reviews are available upon request.
                  Selected Quotes and Student Reviews (Math 52) [ html ]
                  Numerical Breakdown of Departmental Evaluations (Math 9, 18, 52) [ html ]
    • The Brown University Critical Review is a student-run publication which independently evaluates courses and instructors.  Evaluations include a numerical breakdown and a summary of student comments.
                  Critical Review for Math 9 - Introductory Calculus - Fall 2003 [ pdf ]
                  Critical Review for Math 18 - Multivariable Calculus - Fall 2004 [ pending ]
                  Critical Review for Math 52 - Linear Algebra - Spring 2006 [ pdf ]

    Awards and Certificates

       

     



    In Semester 1, 2015-2016, I will be teaching CSL 759: Cryptography and Network Security.

    Administrative Information.

    When and Where.

    Classes are held on Monday and Thursday between 3:30 pm - 5 pm. Location: Bharti building, Room 201.

    Office Hours and Teaching Assistants.

    The teaching assistants for the course are listed below. Please email them for setting up meeting times. I do not hold fixed office hours but will be happy to meet you anytime, just drop me an email!
    • Ishaan Preet Singh. Email:cs5110280@cse.iitd.ac.in
    • Sai Praneeth Reddy. Email:cs5110294@cse.iitd.ac.in
    • Divyanshu Bagga. Email:csz138107@cse.iitd.ac.in

    Pre-requisites.

    This course requires mathematical maturity, you should be comfortable with the language of proofs. Knowledge of algorithms, theory of computing (i.e. familiarity with reductions), some algebra and probability theory is required. The course will be self contained for the most part but you should be familiar with the tools and techniques used in theoretical computer science.

    Requirements.

    • Homeworks: 20%. There will be a homework assignment every two weeks.
    • Midterm: 25%
    • Major Exam: 35%
    • Project: 20%

    Policies and Grades.

    Collaboration is encouraged but you must write up solutions on your own. You must also write the names of all the people you discussed the problem with. In case you find material that will help you in solving some problems, you should mention the source in your writeup. Class participation will also be taken into account when assigning grades.
    I expect all students to behave according to the highest ethical standards. Any cheating or dishonesty of any nature will result in failing the class.

    Lecture Notes and Handouts.

    Lecture Summaries.

    1. Lec 1 (23rd July) : Introduction to Cryptography. Motivation, hardness assumptions, discussion on provable security. This blog by Ryan O'Donnell and this follow-up discussion contains a nice discussion of average case hardness, in particular Impagliazzo's worlds. Here is a discussion on basing cryptography on NP-hard problems by Scott Aaronson. This Wikipedia entry is also good to read. Here is a formal discussion of Shannon's lower bound for perfect security, section 1.3 of this contains another.
    2. Lec 2 (27th July): Principles of Cryptographic design : formulating security model, distilling mathematical assumption, reducing hardness of cryptosystem to mathematical assumption. Case study of secure encryption. Slides were used and are available here. The material was from Katz-Lindell's book (see Reading material below).
    3. Lec 3 (30th July): Formalizing easy and hard: Definition of probabilistic polynomial time (PPT) algorithms, negligible functions. Definition of One way Functions, One way Permutations. Examples based on integer factoring and discrete log. Basic number theory review: groups, definition of Z_n^*, Fermat's little theorem.
    4. Lec 4 (3rd Aug): Proof of Fermat's little theorem, efficient algorithm for modular exponentiation. Definition of Euler's phi function and Euler's theorem. Definition of trapdoor permutation and the example of RSA. Discussion of how to use OWFs for storing passwords and the many real world problems with this approach. Lectures 3 and 4 are based on this lecture by Yevgeniy Dodis.
    5. Lec 5 (6th Aug): Quadratic residues, Legendre symbols, ease of computing LSB of discrete log. Here is one good reference, here is another.
    6. Lec 6 (10th Aug): Jacobi symbol, QR assumption, Rabin's OWF based on factoring. References listed for Lec 5 are applicable.
    7. Lec 7 (13th Aug): Goldreich Levin hardcore bit. References : Barak's notes , Yevgeniy's notes and Theorem 9.12 in Barak-Arora's book chapter .
    8. Lec 8 (17th Aug) and Lec 9 (20th Aug): Using hardcore bit for coin tossing on the telephone and for symmetric key encryption. Definition of computational indistinguishability and pseudorandom generator. Construction of PRG with single bit stretch from hardcore bit. Barak's notes are a good reference for single bit stretch PRG and Arora's notes are a good reference for poker playing and a general introduction.
    9. Lec 10 (24th Aug) and Lec 11 (27th Aug): Stretching the output length of PRG. Construction using OWP and hardcore bits. Definition of next bit unpredictability and its connection with PRG. Proof that construction satisfies NBU. References: Barak's Notes and Yevgeniy's notes . Discussion on whether there can exist a one way function in which no bit is hardcore. A good reference (thanks to Raghuvansh!) is this homework assignment by Jon Katz.
    10. No lectures on 31st Aug and 3rd Sept due to Minor Test 1.
    11. Lec 12 (7th Sept): Proof that NBU implies PRG. Explicit examples of PRG: Blum-Micali and Blum-Blum-Shub. Definition of PRF. Barak's Notes, Yevgeniy's notes , Leo's notes are a good reference.
    12. Lec 13 (10th Sept): Symmetric Key encryption from PRG and limitations. Definition and discussion of CPA security for symmetric key encryption. Motivation for PRFs. Yevgeniy's notes are a good reference.
    13. Lec 14 and 15 (14th and 16th Sept): Construction of Symmetric key encryption from PRFs. Proof that it satisfies CPA security. Started construction of PRFs from PRGs. Here are some references.
    14. Lec 16 (21st Sept): Construction of PRF from PRG (GGM). Discussion about hybrid argument. Good references are here and here.
    15. Lec 17 24th Sept): Problem solving in preparation of midterm.
    16. (28th Sept): No class due to midterm exam. .
    17. Lec 18 (1st Oct): Definition of Public Key encryption, constuction from TDPs and DDH (El Gamal Encryption). Good notes are here and here.
    18. Lec 19 (5th Oct) and 20 (8th Oct): Introduction to the problem of message authentication. Difference between authentication and encryption, a.k.a trust versus privacy. Definition of MAC and construction from PRFs. Good notes are here and here.
    19. Lec 21 (12th Oct): Discussed solutions for Mid Term Exam.
    20. Lec 22 (15th Oct): Lecture about Bitcoins. Slides are here.
    21. 19th and 22nd Oct: No class due to Mid Semester Break.
    22. Lec 23 (26th Oct): Digital Signatures. Definition. One time signatures from One Way Functions. Construction from TDPs in ROM. Discussion of Random Oracle Model. Good references are Chris's notes and Yevgeniy's notes .
    23. Lec 24 (29th Oct): One time to many time signatures using CRHFs and chaining. Proof of TDP based signatures (full domain hash) in Random Oracle Model. References from previous lecture apply, in addition to this.
    24. Lec 25 (2nd Nov) and Lec 26 (4th Nov, rescheduled from 5th Nov): Introduction to Zero Knowledge. Slides by Yevgeniy Dodis are available here. Good notes by Rafael Pass are 1,2 and 3.Here is the SUDOKO demonstration I showed in class.
    25. Lec 27 (16th Nov): Introduction to lattice based cryptography. Discussion on fully homomorphic encryption.

    Reading Material and References.

    While we will not follow any particular text, the following are useful references.

    Handouts.

    Some useful handouts for probability, number theory and algebra are given below. Please refer to them on an "as needed" basis.
    1. Handout for basic probability by Luca Trevisan and another one by Boaz Barak.
    2. Handout for Algebra by Luca Trevisan.
    3. More technical introduction to number theory by D. Angluin.
    4. Very Basic and Basic number theory fact sheet by Dan Boneh.
    5. Computational Number Theory notes by Mihir Bellare.

    Homeworks.

    1. Homework 1 is out! Here are the solutions (on IIT privateweb).
    2. Homework 2 is out! Here are the solutions (on IIT privateweb).
    3. Homework 3 is out. Here are the solutions (on IIT privateweb).
    4. Homework 4 is out! Here are the solutions (on IIT privateweb).

    Policy: You are encouraged to discuss problems but you are expected to fully understand and write down solutions on your own. Once the HW is returned, we will discuss solutions in class where I will randomly call upon students who got a homework problem correct to solve the problem on the board so that we all can understand and discuss the solution. So make sure you really know the solutions you write! The TAs will be watching for copied answers. If any copying is detected then you will earn a zero in ALL homework assignments. I will not discuss or bend this rule. No late submissions will be accepted unless in extreme situations.


    0 Replies to “Number Theory And Cryptography Assignment Sheet”

    Lascia un Commento

    L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *