Chris Pollett > Students >
Molina

    ( Print View)

    [Bio]

    [Blog]

    [CS 297 Proposal]

    [Deliverable 1]

    [Deliverable 2]

    [Deliverable 3]

    [Deliverable 4]

    [McEliece System]

    [Regev System]

    [RSA System]

    [CS 297 Report-PDF]

    [CS 298 Proposal]

    [CS298 Slides-PDF]

    [CS298 Report-PDF]

CS298 Proposal

Investigating Lattice-Based Cryptography

Michaela Molina (michaela.molina@sjsu.edu)

Advisor: Dr. Chris Pollett

Committee Members: Dr. Thomas Austin, Dr. Robert Chun

Abstract:

Implement lattice-based cryptosystems in Rust: the first by Miklos Ajtai which is based off a cryptographic hash and has a worst-to-average case reduction, the second by Hoffstein, Piper, and Silverman called NTRU which is public key and does not have a worse-to-average case reduction, and the third by Regev which is public key and has a worse-to-average case reduction. Also read and implement components from Yanyi Liu and Shuichi HiraHara. Run benchmarking of the different systems. Implement some worse to average case reduction algorithm.

CS297 Results

  • Demonstrated understanding of Rust by showing a small program that used Rust packages.
  • Implemented md5 in Rust and showed examples of the hash function compared with the Rust library md5 hash function to confirm correctness of the algorithm.
  • Implemented Impagliazzo-Naor hash-function, ran hash function on every combination of input of specified lengths to show randomness of output.
  • Implemented modular polynomial ring multiplication, division, and inverse which were used in key generation and encryption in NTRU, a ring-based public key system.

Proposed Schedule

Week 1: Feb 1 - Feb 7 Get caught up to last Fall
Week 2: Feb 8 - Feb 14 Read [McEliece1978]
Week 3: Feb 15 - Sep 21 Implement 3 matrices from [McEliece1978]
Week 4: Feb 22 - Feb 28 Implement decoding from [McEliece1978]
Week 5: March 1 - March 7 Run tests on public key system from [McEliece1978]
Week 6: March 8 - March 14 Read [Regev2009] pages 1-20
Week 7: March 15 - March 21 Read [Regev2009] pages 21 - 40
Week 8: March 22 - March 28 Implement encryption system from [Regev2009]
Week 9: March 29 - April 4 Implement decryption from [Regev2009]
Week 10: April 5 - April 11 Run tests on public key system from [Regev2009] to show that it works
Week 11: April 12 - April 18 Create experiments to show complexity of lattice-based systems in comparison to non lattice-based systems
Week 12: April 19 - April 15 Run experiments to show complexity of lattice-based systems in comparison to non lattice-based systems
Week 13: April 26 - May 2 Run experiments to show complexity of lattice-based systems in comparison to non lattice-based systems
Week 14: May 3 - May 9 Start CS298 Report and Presentation
Week 15: May 10 - May 16 Finish CS298 Report and Presentation

Key Deliverables:

  • Software
    • Implement public key system from from [McEliece1978]. Implement the algorithm under "Algorithm E" which is encryption achieved by matrix multiplication and addition, and implement the algorithm under "Algorithm D" which is decryption achieved by finding the inverse of a matrix
    • Implement public key system from [Regev2009] under "Section 5. Public Key Cryptosystem" which is a public key system where encryption is achieved by choosing a random set of numbers and doing arithmetic on them. Decryption is done by finding if a dot product is closer to zero than some threshold.
    • Run experiments to show complexity of large key size of lattice-based systems in comparison to non lattice-based systems
  • Report
    • CS 298 Report
    • CS 298 Presentation

Innovations and Challenges

  • It is challenging to implement cutting-edge lattice-based cryptography which is quantum resistant.
  • Showing the effect of key-size difference between lattice-based and other systems requires a thorough understanding. There have been few comparisons between the McEliece and Regev systems and non lattice-based systems.
  • Rust has not been commonly used for experiments comparing lattice-based and other systems.

References:

[Regev2009] "On lattices, learning with errors, random linear codes, and cryptography." Oded Regev. Journal of the ACM (JACM) 56.6. Association for Computing Machinery, New York, NY, United States. 2009.

[McEliece1978] "A public-key cryptosystem based on algebraic coding theory." Coding Thv 4244 1978.