(Winter 2023) CS 485/585 - Intro to Cryptography

Course Project

Instructions

2-3 people group projects. You may choose one of the options below.

  • Research project. Take any route to gain some research experience.
    • Literature review. Pick a topic of interest, and summarize the state of art of it. The final outcome would be a survey paper including open problems.
    • Original research. Challenge yourself with some open question in the field. You are encouraged to explore interdisciplinary topics between cryptography and your own research area. Be creative and keep a critical mind. You may also choose to complete “folklores” in the field, which are results believed true but are missing details or careful scrutiny. You will study a dedicated problem and give a thorough exposition on it.

  • Programming project. Implementing cryptographic systems and applications is a risky business. Take this opportunity to learn good practices of putting cryptography into real-world use cases.

  • Societal-impact project. What is the broader implications of cryptography? Are there ethical issues concerning the technology and the workforce development?

Milestones

  • Proposal: 1-2 pages consisting of 1) the topic, background, context, and motivation; 2) a few core references; and 3) your goal and a plan. (5%)
  • Oral presentation: Each group will have about 30 minutes to present your project including Q&A. Your need to demonstrate both breath and depth. Aim for a clear introduction that would engage the audience, and then explain 1-2 technical ideas in some detail. Every group member needs to participate, and your group will be graded by fellow students. (15%)
  • Final report: ~ 10 pages (excluding references). This should resemble a research paper containing: 1) a short abstract; 2) an introduction that motivates the topic and offers an overview of the entire report; 3) details including proper preliminary materials (e.g., notations & definitions), explaining the main results; and finally 4) further discussion and open questions. (10%)
  • Report format: Submit your reports in PDF. I recommend that you typeset in LaTeX, and manage your bibliography using BibTeX.

Timeline (Tentative)

  • Week 2 - 4: discussing project ideas and forming groups.
  • Week 5: proposal due on 02/08.
  • Week 8: progress check-up meetings.
  • Week 10: in-class presentations.
  • 03/22: final report due.

Suggested topics

The list below is far from complete, and is only intended as a starting point for you to explore more options.

Societal impact

(We need scientists and engineers to advance the field of cryptography and cybersecurity at large. But what is equally important, if not more, is to have more people think broadly the implications and proper actions to take.)

  • The Moral Character of Cryptographic Work. An insightful essay by Phil Rogaway (Paper Slides at Asiacrypt 2015).

  • Cryptography For a Secure, Privacy-Respecting and Fair Society: What More Can We Do? Invited talk (Video) at Asiacrypt 2021 by Kazue Sako.

  • Crypto for the People. Invited talk by Seny Kamara at Crypto 2020. Check out Kamara’s research work.

  • Export control on cryptography (US EAR). What? Why? Impact?

  • E-Voting. Check out research by Vanessa Teague and an invited talk (Slides Video) at Crypto 2021. There was also an earlier talk (Democracy, security and evidence: let’s have all three) at Asiacrypt 2018.

Programming

(Implementing cryptographic algorithms and applications needs to be exercised with the highest standard. Even the slightest neligence can be disastrous. Individuals are usually advised against homebrewing them but to resort to standardized libraries.)

  • Password Manager (Credit: Dan Boneh). Instructions Starter code.

  • End-to-End encrypted chat client (Credit: Dan Boneh). Instructions Starter code.

  • Comparative study of NIST PQC Finalists. Read the report to get a comprehensive picture about the history and status of this standardization process. Then select a few to assess their security and performance. Each team typically maitains codes and a project website (e.g., this page contains the information of the schemes selected to be standadized in July 2022, and this page lists Round 4 submissions).

  • Build your applications with homomorphic encryption. Some libraries to consider SEAL, openFHE.

  • Playing with zeor-knowledge proofs and SNARKs. This workshop provides a lot of up-to-date pointers in the theory and practical developments of zero-knowledge proofs.

Research

  • Check out recent research results at these venues: Crypto, Eurocrypt, Asiacrypt, TCC, Qcrypt, and general TCS conferences (e.g., STOC, FOCS, SODA, ITCS, CCC).

  • Constructions
    • [ETY22] Shorter Hash-and-Sign Lattice-Based Signatures.
    • [HMR12] An Enciphering Scheme Based on a Card Shuffle.
    • [BH15] From Non-adaptive to Adaptive Pseudorandom Functions.
    • [JJ22] Indistinguishability Obfuscation (iO) via Mathematical Proofs of Equivalence.
    • [SW14] How to Use Indistinguishability Obfuscation: Deniable Encryption, and More.
    • [GSW13] Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. (Third-Gen fully homomorphic encryption.)
  • Cryptanalysis
    • [Beullens22] Breaking Rainbow (an NIST post-quantum cryptography Round-3 finalist) Takes a Weekend on a Laptop.
    • [GLST22] Exploring SAT for Cryptanalysis: (Quantum) Collision Attacks against 6-Round SHA-3.
  • Lower bounds
    • [CHM20] How much time and memory are needed to invert a function? The solution to this simple question is not as simple.
    • [BHKU22] The Price of Verifiability: Lower Bounds for Verifiable Random Functions (VRFs are essential in Proof-of-Stake blockchain technology).
    • [HNY22] Lower Bound on SNARGs in the Random Oracle Model. SNARGs are a vital building block in ZCash and many more cryptocurrency schemes.
  • (Post-) quantum cryptography
    • [MY21 AQY22 AGQY22] Cryptography from quantum pseudorandomness. What is the minimal assumption for cryptography?
    • [HMY22] From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments.
    • [GJMZ22] Commitments to Quantum States.
    • [LMQW22] A new set of examples demonstrating classical security fails to imply quantum security.