This summer, I was hosted by Mariana Raykova and Baiyu Li at Google to work on Single Server PIR. This internship led to a paper. Rather than try to put together some tweet-thread (or X-thread? who knows) talking about the result, I thought it best to write it up somewhere that supports latex, e.g. here.

Today, NIST put out its preliminary choice of PQC algorithms to standardize. I wrote an introduction to lattice-based KEMs (for non-cryptographers) this last weekend in preparation for the report, where one implements an (aggressively unoptimized) variant of FrodoKEM. FrodoKEM ended up not being standardized, but the “broad picture” of the construction should still be useful to understand Kyber.

This is a continuation on my series on a simple construction of (public-key) lattice-based encryption. We’re finally ready to construct public-key encryption! Similarly to the private-key setting, we will first give a construction in the (simpler, but insecure) noiseless setting, before adapting the construction to handle noise.

In the previous post, we discussed

This is a first post in a series of blog posts where I plan on building a relatively simple lattice-based public-key encryption scheme. This construction is not novel at all [¹], but the intention is to

Earlier this week, a paper was posted on eprint claiming to be authored by Schnorr, and claiming (in the abstract at least) to break RSA. The paper itself appears to have been a work-in-progress (a version of it made the Crypto 2009 rump session), and some comments by Ducas (who is an expert on lattices) make it sound like a known strategy that doesn’t seem to work out (he pointed to the paper here from 2010, and also experimentally tested some of the claims, demonstrating a gap between Schnorr’s claim and experimental evidence). Of course, this does not mean that RSA is completely safe (see Heninger’s comments on the matter), but it does dampen much of the excitement.

After attending a talk by Psi Vessely on Quantum Key Distribution (in particular on BB84), the UCSD crypto group discussed some of the alleged benefits of QKD. We mentioned the “standard list”:

Differential Privacy is an area which has seen wide interest (both in academia and real-life) in recent years. But what is differential privacy? As I don’t work in this area, I’m rather ill-suited to say anything — but at least why does it have that name? Frank McSherry (one of the founders of the area, who shares the Godel Prize as a result) states that it was one of several names considered, including others like “Marginal Privacy” or “Incremental Privacy”. He further states that he thinks the name “stuck” due to an analogy with differential cryptanalysis.