Public Key Lattice-based Encryption

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.

Read More

Textbook RSA and LWE

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 [1], but the intention is to

  1. For experts, the intention is to present FrodoKEM, without any of 

Read More

Continuous and Discrete Prime Lattices

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.

Read More

Sensitivity as the Operator Norm of a Derivative

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.

Read More