Digital signatures underpin identity, authenticity, and trust in modern computer systems. Cryptography research has shown that it is possible to prove possession of a valid message and signature for some public key, without revealing the message or signature. These proofs of possession work only for specially-designed signature schemes. Though these proofs of possession have many useful applications to improving security, privacy, and anonymity, they are not currently usable for widely deployed, legacy signature schemes—like RSA, ECDSA, and Ed25519. Unlocking practical proofs of possession for these legacy signature schemes requires closing a huge efficiency gap. This work brings proofs of possession for legacy signature schemes very close to practicality. Our design strategy is to encode the signature's verification algorithm as a rank-one constraint system (R1CS), then use a zkSNARK to prove knowledge of a solution. To do this efficiently we (1) design and analyze a new zkSNARK called Dorian that supports randomized computations, (2) introduce several new techniques for encoding hashes, elliptic curve operations, and modular arithmetic, (3) give a new approach that allows performing the most expensive parts of ECDSA and Ed25519 verifications outside R1CS, and (4) generate a novel elliptic curve that allows expressing Ed25519 curve operations very efficiently. Our techniques reduce R1CS sizes by up to 200× and prover times by more than 20×. We can generate a 240-byte proof of possession of an RSA signature over a message the size of a typical TLS certificate—two kilobytes—in only three seconds.

For CS50 at Harvard, we have developed a suite of free, open-source tools to help students with writing, testing, and submitting programming assignments and to help teachers grade those assignments and check them for similarities. help50 parses often-cryptic error messages and explains them in beginner-friendly terms. check50 runs a set of automated tests on students' code, providing feedback on errors. style50 lints students' code, highlighting that don't adhere to the course's style guide. submit50 allows students to submit assignments to a GitHub repository, without students needing to have knowledge of git or version control themselves. And compare50 allows teachers to analyze submissions for similarity, looking for pairs or clusters of submissions that might be the result of improper collaboration. In this workshop, we'll introduce each of these tools and discuss how other teachers can use them in their own classrooms. Along the way, we'll discuss how to use the tools effectively, compare and contrast them with alternatives, identify how the tools have changed students' behavior for the better and for worse, and highlight pedagogical and technological changes we've made to redress the latter.

We present check50, an open-source, extensible tool for assessing the correctness of students' code that provides a simple, functional framework for writing checks as well as an easy-to-use API that abstracts away common tasks, among them compiling and running programs, providing their inputs, and checking their outputs. As a result, check50 has allowed us to provide students with immediate feedback on their progress as they complete an assignment while also facilitating automatic and consistent grading, allowing teaching staff to spend more time giving tailored, qualitative feedback. We have found, though, that since introducing check50 in 2012 in CS50 at Harvard, students have begun to perceive the course's programming assignments as more time-consuming and difficult than in years past. We speculate that the feedback that check50 provides prior to students' submission of each assignment has compelled students to spend more time debugging than they had in the past. At the same time, students' correctness scores are now higher than ever.

For CS50 at Harvard, we have developed a suite of free, open-source tools to help students with writing, testing, and submitting programming assignments; and to help teachers grade those assignments and check them for plagiarism. help50, a program that parses error messages and provides beginner-friendly advice to interpreting them, helps students understand and resolve often-cryptic compiler errors. check50 runs a set of automated tests on students' code, providing feedback and hints about where students have made errors. style50 lints students' code, highlighting places where it doesn't meet the course's style guide. submit50 allows students to submit assignments to a GitHub repository, without students needing to have knowledge of git or version control themselves. And compare50, an open-source and customizable alternative to Moss, allows teachers to analyze submissions for similarity, looking for pairs or clusters of submissions that might be the result of improper collaboration. The grading and submission tools require only a GitHub account to use, and can serve as free, extensible alternatives to tools like Codio, Gradescope, and Vocareum. In this workshop, we'll introduce each of the tools, and discuss how to use them for your own classroom. To date, each tool has been deployed to hundreds of students on campus and thousands online. Along the way, we'll discuss how to use the tools effectively, compare and contrast them with other options, identify how the tools have changed students' behavior for the better and for worse, and highlight pedagogical and technological changes we've made to redress the latter. Laptop (with Wi-Fi) required. Linux, macOS, or Windows. Latest version of Chrome.

Fully Homomorphic Encryption (FHE) is a cryptographic "holy grail" that allows a worker to perform arbitrary computations on client-encrypted data, without learning anything about the data itself. Since the first plausible construction in 2009, a variety of FHE implementations have been given and used for particular applications of interest. Unfortunately, using FHE is currently very complicated, and a great deal of expertise is required to properly implement nontrivial homomorphic computations. This work introduces ALCHEMY, a modular and extensible system that simplifies and accelerates the use of FHE. ALCHEMY compiles "in-the-clear" computations on plaintexts, written in a modular domain-specific language~(DSL), into corresponding homomorphic computations on ciphertexts---with no special knowledge of FHE required of the programmer. The compiler automatically chooses (most of the) parameters by statically inferring ciphertext noise rates, generates keys and "key-switching hints," schedules appropriate ciphertext "maintenance" operations, and more. In addition, its components can be combined modularly to provide other useful functionality, such logging the empirical noise rates of ciphertexts throughout a computation, without requiring any changes to the original DSL code. As a testbed application, we demonstrate fast homomorphic evaluation of a pseudorandom function~(PRF) based on Ring-LWR, whose entire implementation is only a few dozen lines of simple DSL code. For a single (non-batched) evaluation, our unoptimized implementation takes only about 10 seconds on a commodity PC, which is more than an order of magnitude faster than state-of-the-art homomorphic evaluations of other PRFs, including some specifically designed for amenability to homomorphic evaluation.