Final Project

Overview

For the course project, you will be doing independent work to understand and explore an area in cryptography. Your deliverable will be a recorded presentation of your findings. Your goal should be to understand a new concept in crypto by reading original sources, and then to communicate this concept clearly and concisely. You should aim to cover a topic from your own perspective, not just to summarize a single paper. Your target audience should be your fellow students in the course. If you would like to do some original research as part of your project, this is very much encouraged, but not required.

The project runs across the second half of the semester as the sequence of steps listed below; the deadline and weight for each is in the table.

You start by settling on a topic in late September — one line saying what you intend to cover, plus a backup in case the first does not pan out. Before you commit, you are encouraged to discuss possible topics with the course staff during office hours. You then write a topic summary: less than a page describing the topic, a timeline for exploring it, and a list of selected references. This should show that you have thought about your topic and have a clear picture of what you plan to cover in your presentation.

By the start of November you submit a presentation outline — the structure of the talk itself, together with the final reading list you are working from. In late November you record a draft of the presentation, a complete first pass with rough edges and all, and then write peer feedback on the drafts you are assigned. The point of these two steps is to give and get concrete advice while there is still time to act on it.

Your final recording is due at the end of the semester and is the bulk of the project grade. It should be at most 15 minutes long, and can take whatever form you want it to.

Deadlines

All deadlines are subject to change; changes will be announced on the course site.

Possible topics

The list below is a menu of areas, each with a few threads worth pulling on. It is meant as a starting point, not a restriction: you are welcome to propose something that does not appear here, and most of these entries are broad enough that you will need to narrow them considerably. Come talk to me if you want help finding the right scope.

Post-quantum cryptography

• NIST-standardized algorithms and what their proofs actually cover. NIST has standardized a new set of algorithms that are believed to be post-quantum secure: ML-KEM, ML-DSA, and SLH-DSA. These are being rolled out right now, and there is a rich line of work that developed these techniques and have been stress testing them.
• Cryptanalysis of post-quantum assumptions. Many of the assumptions on which new post-quantum cryptographic constructions are based are quite new, and therefore have received significantly less cryptanalysis than older assumptions. Figuring out how to set parameters tends to also be more complicated for these assumptions.
• Post-quantum signatures from symmetric primitives alone. If every structured algebraic assumption is one cryptanalytic paper away from trouble, a signature whose only assumption is “AES is one-way” is the ultimate hedge. There has been significant recent work building post-quantum signatures that rely only on symmetric primitives.

Advanced signatures

• Ring and group signatures. Both let a signer hide inside a set, but they differ on whether anyone can ever open the signature — ring signatures are setup-free and unconditionally anonymous, group signatures add a manager who can trace. Recent work pushes on logarithmic-size constructions, post-quantum instantiations, and what accountability should mean.
• Adaptor signatures. An adaptor signature is a “pre-signature” that becomes a valid signature only when a secret witness is revealed, and revealing the signature reveals the witness.
• Blind signatures. The signer learns nothing about the message it signs, which underpins e-cash, anonymous tokens, and credential issuance. Practical schemes have repeatedly been broken by concurrent-attack subtleties (ROS/mROS), so the thread is a nice case study in definition writing.
• Aggregate and multi-signatures. Compressing many signatures on many messages into one short object, which is what makes large validator sets tractable in consensus protocols. The interesting difficulties are rogue-key attacks, tight security in the multi-user setting, and getting it under post-quantum assumptions.
• Functional and policy-based signatures. Signatures where the signing key certifies a policy rather than an identity, so the holder can sign exactly the messages a predicate allows. Sits alongside ABE conceptually and shares much of its machinery.

Advanced encryption

• Attribute-based and identity-based encryption. ABE ties decryption to a predicate over attributes rather than to a named recipient. IBE allows you to encrypt to an identity rather than a key, and makes it possible for the identity to get their key from a central issuer later.
• AEADs and committing encryption modes. Sometimes you need even more than CCA security. In particular, modern systems generally require stronger notions of symmetric key encryption that bind in public key context and make it impossible to produce keys that open the ciphertext to something wrong.
• Registration-based encryption and registered ABE. These schemes remove the trusted key-issuing authority that has been the practical obstacle to deploying IBE and ABE. Instead, users sample their own keys and register them with an untrusted key aggregator.
• Predicate encryption and witness encryption. Witness encryption lets you encrypt to an NP statement so that only someone holding a witness can decrypt — a primitive powerful enough to imply much of the rest of the field, and correspondingly hard to build. Predicate encryption is the more tractable cousin where the policy itself may need to stay hidden.
• Broadcast encryption without trusted setup. Distributed broadcast encryption lets each user generate their own key independently and still be addressed by a ciphertext short in the number of recipients. Recent lattice constructions reach unbounded user sets without pairings or a trusted authority.
• Updatable encryption. Schemes that let a server rotate the key on stored ciphertexts without decrypting them, which sounds routine and turns out to have a subtle definitional landscape around what the update token leaks.

Zero-knowledge for structured statements

• Lookup arguments. Sometimes you just want to prove that a particular value is part of a set of values (represented as a table). It turns out that many things you want to prove can be efficiently reduced to this, including range checks and byte decompositions, which turn out to be very helpful in modern zkVM design. Modern lookup arguments allow you to prove table membership in time (and size) that is sublinear in the table size.
• Incrementally verifiable computation. IVC proves “I ran this step N times correctly” with a proof that stays small, and folding/accumulation schemes are a particular approach to this that removes ugly, non-blackbox approaches to achieving this notion.
• Batch arguments (BARGs). A single short proof for many NP statements at once, which is weaker than a full SNARK but achievable from standard assumptions — and, surprisingly, strong enough to bootstrap into much more. Good topic for a student who is more theory/foundations oriented, but still interested in zero-knowledge.
• TLS oracles and TLS Notary. Proving statements about TLS-attested web data in zero-knowledge promises to be a very nice way to easily allow us to hook all the world’s existing data into our cryptographic machinery in an authenticated way. These techniques allow you to prove statements about any data that is served by a TLS-enabled server — but it turns out doing this efficiently is more complicated than you would first think.

Lattice-based zero-knowledge

• Succinct lattice arguments. Almost all deployed succinct arguments rely on assumptions that are known to be no longer hard against quantum adversaries. Lattice-based proof systems are the main plausible post-quantum replacement.
• Lattice folding and recursion. Similar to the IVC discussion above, but now with lattice-based underpinnings.

Polynomial commitment schemes

• Pairing-based commitments and the trusted setup. Polynomial commitment schemes allow someone to commit not only to a value, but to a polynomial, and then allow openings to particular evaluations of those polynomials. This line is pairing-based commitments, including KZG, which are the most widely used, but rely on structured reference strings.
• Hash- and code-based commitments. Merkle-tree commitments to codewords give transparent, plausibly post-quantum schemes at the cost of larger proofs — the FRI/Brakedown/BaseFold family.
• Lattice-based polynomial commitments. The post-quantum alternative that keeps proofs short rather than trading size for transparency.
• Multilinear versus univariate. There are other proof systems which, instead of using univariate representations, rely on multivariate (and multilinear) representations instead. Doing this requires multilinear polynomial commitment schemes.

Advanced garbling schemes

• Arithmetic garbling. Garbled circuits were built for Boolean gates, and encoding arithmetic operations bit-by-bit is enormously wasteful for the numeric workloads people actually want. Recent work garbles arithmetic gates directly, in some regimes at less than λ bits per wire.
• Garbled RAM. Garbling a circuit forces you to unroll every memory access into a full scan; garbled RAM aims for cost proportional to the actual running time of a RAM program. Achieving this with black-box use of cryptography, and with practical constants, took a long time.
• Garbling from homomorphic secret sharing. A structurally different route to garbling that gets better rates by borrowing share-conversion machinery from the homomorphic secret sharing literature.

Silent preprocessing (pseudorandom correlation generators)

• PCGs for different correlations. Two parties expand short correlated seeds into millions of oblivious transfers or Beaver triples with essentially no communication, which changes the economics of MPC preprocessing.

Private set intersection and fuzzy PSI

• PSI from OPRFs and vector-OLE. The core constructions of efficient private set intersection.
• Structure-aware and fuzzy PSI. Real applications rarely want exact intersection — they want intersection of geometric balls, of approximate records, or under a distance threshold — and each relaxation changes the protocol design fundamentally.
• Updatable and circuit PSI. Sets that change over time (so recomputing from scratch is wasteful), and protocols that reveal a function of the intersection rather than the intersection itself.
• Malicious security and its cost. What breaks when we can no longer assume that the participating parties are semi-honest?

Private information retrieval

• Concretely efficient single-server PIR. Making PIR fast enough to deploy has been an FHE-engineering problem, and the last few years have brought order-of-magnitude improvements through better packing, preprocessing, and query compression.
• Doubly efficient PIR. Schemes where both the server’s per-query work and the client’s work are sublinear in the database, which is impossible without preprocessing and is the main theoretical frontier.
• Multi-server PIR. Assuming non-colluding servers buys dramatically better efficiency and information-theoretic security, at the cost of a trust assumption people argue about.
• Keyword PIR and applications. Retrieval by key rather than index, and the deployed systems built on it — private Safe Browsing, certificate checking, private contact discovery.

Timed cryptography

• Verifiable delay functions. Functions that probably take a set amount of sequential time to evaluate but are fast to verify, used for randomness beacons and leader election.
• Time-lock puzzles. Encrypting to the future, so that the message becomes readable only after a set amount of sequential work. Homomorphic and batched variants make them usable in protocols rather than only as curiosities.
• Space-hardness: memory-hard functions and proofs of space. Memory, not time, is the resource that resists ASICs and parallelism, which gives a parallel theory with its own lower bounds in the parallel random oracle model.

Fine-grained cryptography

• Cryptography from fine-grained hardness. If one-way functions do not exist, is there still cryptography where the adversary merely pays more than the honest party — say, quadratically more?

Topics in end-to-end encrypted messaging

• Key transparency. End-to-end encryption is only as strong as the key directory behind it, and key transparency turns “trust the server’s key lookup” into an auditable, append-only claim. Several major messengers have now deployed it, with different efficiency tradeoffs.
• Message franking. Cryptographically binding a reported message to its sender so that abuse reports are verifiable without breaking confidentiality for everyone else. This is where committing encryption meets a real deployment.
• Content moderation in encrypted systems. The broader and more contested design space — source tracing, perceptual hashing, client-side scanning — and the arguments about whether any of it is compatible with E2EE. A good topic for a student who wants to think about social tradeoffs rather than only theorems.
• MLS and group messaging. The MLS standard is the new way that billions of devices are going to do group messaging in end-to-end encryption.
• Signal, ratcheting and post-compromise security. What “healing” after a device compromise means formally, and the gap between the Signal double ratchet as deployed and the ratcheting constructions the literature proves things about.
• Metadata privacy. Sealed sender, private contact discovery, and anonymous delivery — the parts of a messenger that encryption alone does not protect.

Anonymous credentials

• Algebraic MAC and BBS-based credentials. The constructions currently heading toward standardization, and why the choice between a MAC-based and a signature-based scheme changes the trust model.
• Anonymous tokens and Privacy Pass. Letting a server distinguish “a client that already passed a check” from a bot without learning who. The deployed line has grown rate limits, attached metadata, and decentralized issuance, each with a new security definition.
• Revocation and accountability. The hard part of any anonymous system: withdrawing a credential, or holding a misbehaving holder responsible, without undoing the anonymity.
• Digital identity wallets and age verification. mDL and the EU digital identity wallet are pushing selective disclosure into law, often with designs cryptographers object to.
• Post-quantum anonymous credentials. Most efficient credential systems are built on pairings or discrete log; the lattice replacements are dramatically larger, and closing that gap is an open engineering-and-theory problem.

Consensus and blockchains

• The cryptography inside BFT consensus. Threshold signatures, aggregation, and VRFs are what make modern consensus protocols scale, and their security assumptions are often stated loosely in the systems literature.
• Distributed randomness beacons. Producing unbiasable public randomness that no participant can predict or grind, which underpins leader election and sortition.
• Committee selection and player replaceability. Cryptographic sortition lets a huge validator set act through small, unpredictable committees — the idea that makes proof-of-stake tractable.
• Encrypted mempools and MEV. Hiding transactions until they are ordered is the leading cryptographic answer to front-running, and batched threshold encryption is the primitive that makes per-block decryption cheap enough to be real.
• Light clients and succinct bridges. Using succinct proofs so a resource-poor client can verify chain state, which is where SNARKs meet an actual deployment with adversarial incentives.

Random oracles (or not)

• Uninstantiability results. Schemes that are provably secure in the random oracle model and provably insecure for every concrete hash function — the standard argument that ROM proofs are heuristic, and the counterargument that the counterexamples are contrived.
• Standard-model alternatives. Correlation-intractable hash functions and the recent successes and failures in instantiating Fiat–Shamir soundly — including concrete attacks on deployed Fiat–Shamir applications.
• Idealized models beyond the ROM. Generic group, algebraic group, and ideal cipher models, plus the question of what these mean against a quantum adversary.

Lower bounds

• Black-box separations. The main tool for showing that primitive A cannot be built from primitive B by the techniques we know, and a good lens on why the field’s assumption hierarchy looks the way it does.
• Communication lower bounds for secure computation. How much must parties talk to compute a function securely, and where the known protocols are provably optimal versus merely the best we have.

Privacy-preserving and verifiable machine learning

• Secure inference. Running a model on a client’s input without either side learning the other’s secret, via MPC, FHE, or a hybrid. The cost is dominated by nonlinear activations, which is where most of the protocol design goes.
• Verifiable inference (zkML). Proving that a claimed output really came from a specific model on a specific input, which matters as soon as an API provider has an incentive to serve a cheaper model than advertised.
• Secure aggregation and federated learning. Combining many clients’ updates so the server sees only the sum, at a scale where dropout and malicious clients are the real difficulty.

Fully homomorphic encryption

• Bootstrapping. The primary cost for FHE is bootstrapping, which requires decrypting the ciphertext and then re-encrypting it under a different key. Understanding why this is important and how it is done is at the heart of understanding modern FHE.
• Approximate FHE. CKKS is one of the state-of-the-art FHE schemes and computes on approximate values instead of concrete values. Turns out this is much cheaper and more efficient than other approaches, but comes with some interesting caveats.
• Threshold and multi-key FHE. One of the downfalls of fully homomorphic encryption is that someone has the decryption key. These notions allow us to “spread the key around,” such that there is not a single failure point.
• Circuit privacy. One might assume that when using FHE to outsource computation, the decryptor would not learn the function that was computed on the data. Turns out — not the case at all! Circuit privacy is a property that hides exactly this.

Practical generic MPC

• Dishonest-majority protocols with preprocessing. The SPDZ family and its successors, where an expensive offline phase buys a cheap, information-theoretic online phase.
• Honest-majority three- and four-party protocols. The regime where MPC is fastest, and where most real deployments actually sit, with a distinctive set of tricks that do not generalize.
• Getting malicious security cheaply. The above generally assumes that even the corrupt parties will not deviate from the protocol (that they are semi-honest). Getting malicious security, where we can achieve security against adversaries that can do anything, is harder. There are lots of interesting and efficient techniques for doing this, but we can reduce the overhead to basically nothing.

Threshold cryptography

• Threshold signatures. Splitting a signing key so you need t of n parties to agree on signing a message before you can get a signature.
• Distributed key generation. Producing the shared key in the first place without a single trusted dealer. This allows us to do threshold signatures without ever needing the signing key to exist in a single place.
• Threshold decryption and public-key encryption. The encryption-side analogue, including the batched variants that encrypted mempools need.

Quantum cryptography

If you want to work on something within quantum cryptography, please come check with me first.

Symmetric cryptanalysis

If you want to work on something within symmetric cryptography, please come check with me first.