Building Lattice Reduction (LLL) Intuition
> The Lenstra–Lenstra–Lovász (LLL) algorithm is an algorithm that efficiently transforms a “bad” basis for a lattice L into a “pretty good” basis for the same lattice. This transformation of a bad basis into a better basis is known as lattice reduction, and it has useful applications. For example, there is attack against ECDSA implementations that leverage biased RNGs that can lead to private key recovery. However, my experience learning why LLL works has been pretty rough. Most material covering LLL seems targeted towards mathematicians and I had to (I guess I wanted to) spend a lot of time trying to weasel out the intuition and mechanics of the algorithm. This blog post is a semi-organized brain dump of that process. My goal is to cover LLL in such a way that slowly ratchets down the hand-waving, so feel free to read until you are happy with your level of understanding.
The Hidden Number Problem
> The Hidden Number Problem (HNP) is a problem that poses the question: Are the most signficant bits of a Diffie-Hellman shared key as hard to compute as the entire secret? The original problem was defined in the paper “Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes” by Dan Boneh and Ramarathnam Venkatesan.
> In this paper Boneh and Venkatesan demonstrate that a bounded number of most signifcant bits of a shared secret are as hard to compute as the entire secret itself. They also demonstrate an efficient algorithm for recovering secrets given a significant enough bit leakage. This notebook walks through some of the paper and demonstrates some of the results.
Big Data+Small Bias
> Among experts it’s well understood that “big data” doesn’t solve problems of bias. But how much should one trust an estimate from a big but possibly biased data set compared to a much smaller random sample? In Statistical paradises and paradoxes in big data, Xiao-Li Meng provides some answers which are shocking, even to experts.
> Rolling forward 15 years, isogeny-based cryptography is another area with many technical subtleties, but is moving into the mainstream of cryptography. Once again, not everything that can be done with discrete logarithms can necessarily be done with isogenies. It is therefore not surprising to find papers that have issues with their security.
> It is probably time for an Isogenies for Cryptographers paper, but I don’t have time to write it. Instead, in this blog post I will mention several recent examples of incorrect papers. My hope is that these examples are instructional and will help prevent future mistakes. My intention is not to bring shame upon the authors.
Signed distance fields
> It would be fun, I thought, to be able to specify the desired cross-sections, and have something generate the required 3D shape (if it existed) in real-time.
> Dealing with all of the details of creating a mesh with the right vertices etc. sounded painful though. Fortunately, I had been reading recently about a different kind of 3D rendering technique which makes these kind of boolean operations trivial – signed distance fields.
The Deadly Consequences of Rounding Errors
> In politics, stock markets, space, and the battlefield, tiny software calculation mistakes have had enormous consequences.
> Sometimes those fractional cents aren’t stolen—they simply vanish. In the early 1980s, a new stock index at the Vancouver Stock Exchange tracked a steady and mysterious loss in value. An investigation revealed that floor() was being used instead of round(), with the lost fractions of cents accumulating to almost a 50 percent loss of value in 22 months. The programming mistake was finally fixed; the index closed around 500 on a Friday and reopened the following Monday at over 1,000, the lost value restored.
Incenters of chocolate-iced cakes
> Grandma made a cake whose base was a square of size 30 by 30 cm and the height was 10 cm. She put chocolate icing on top of the cake and on the sides, but not on the bottom. She wanted to divide the cake fairly among her 9 grandchildren so that each child would get an equal amount of the cake and the icing. How should she cut the cake?
A fast alternative to the modulo reduction
> Assume that x and N are 32-bit integers, consider the 64-bit product x * N. You have that (x * N) div 2^32 is in the range, and it is a fair map.
Where Theory Meets Chalk, Dust Flies
> A photo survey of the blackboards of mathematicians.
> For the last year, Jessica Wynne, a photographer and professor at the Fashion Institute of Technology in New York, has been photographing mathematicians’ blackboards, finding art in the swirling gangs of symbols sketched in the heat of imagination, argument and speculation. “Do Not Erase,” a collection of these images, will be published by Princeton University Press in the fall of 2020.
Visual Information Theory
> Information theory gives us precise language for describing a lot of things. How uncertain am I? How much does knowing the answer to question A tell me about the answer to question B? How similar is one set of beliefs to another? I’ve had informal versions of these ideas since I was a young child, but information theory crystallizes them into precise, powerful ideas. These ideas have an enormous variety of applications, from the compression of data, to quantum physics, to machine learning, and vast fields in between.
> Unfortunately, information theory can seem kind of intimidating. I don’t think there’s any reason it should be. In fact, many core ideas can be explained completely visually!
Marty Weitzman’s Noah’s Ark Problem
> Marty Weitzman passed away suddenly yesterday. He was on many people’s shortlist for the Nobel. His work is marked by high-theory applied to practical problems. The theory is always worked out in great generality and is difficult even for most economists. Weitzman wanted to be understood by more than a handful of theorists, however, and so he also went to great lengths to look for special cases or revealing metaphors. Thus, the typical Weitzman paper has a dense middle section of math but an introduction and conclusion of sparkling prose that can be understood and appreciated by anyone for its insights.
> The Noah’s Ark Problem illustrates the model and is my favorite Weitzman paper.
On studying mathematics
> I understand that most of us do not have a good experience when studying mathematics in high school or college. I assure you that this is a common problem, not only in Vietnam, but all over the world. Mathematics is taught and learned mechanically, without joy. But don’t worry, and please be optimistic, school is not the only place we can learn. I have never had a college degree, and if I can study math, anyone can learn it. The only thing we need is an open mind, daring to try new things, the rest can be left to math!
The Only Way to Win Is Not to Play the Game
> When I became a math and science writer, I had no idea that one of the most common requests I would get would be to weigh in on order of operations problems that somehow go viral in some segment of the internet.
> The real answer, the one I believe any mathematician, physicist, engineer, other number-cruncher would tell you is to make sure your expressions aren’t ambiguous.
Another take: https://danso.ca/blog/order-of-operations/
Decades-Old Computer Science Conjecture Solved in Two Pages
> “This conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science,” wrote Scott Aaronson of the University of Texas, Austin, in a blog post. “The list of people who tried to solve it and failed is like a who’s who of discrete math and theoretical computer science,” he added in an email.
> Over the years, computer scientists have developed many ways to measure the complexity of a given Boolean function. Each measure captures a different aspect of how the information in the input string determines the output bit. For instance, the “sensitivity” of a Boolean function tracks, roughly speaking, the likelihood that flipping a single input bit will alter the output bit. And “query complexity” calculates how many input bits you have to ask about before you can be sure of the output.
> Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
One law to rule them all?
> Power-law distributions seem to be everywhere, and not just in word-counts and whale whistles. Most people know that Vilfredo Pareto found them in the distribution of wealth, two or three decades before Udny Yule showed that stochastic processes like those in evolution lead to such distributions, and George Kingsley Zipf found his eponymous law in word frequencies. Since then, power-law distributions have been found all over the place
> Or maybe not? Many of the alleged “power-law” examples are actually log-normal, or some other heavy-tailed distribution, according to a paper by Aaron Clauset, Cosma Rohilla Shalizi, and M. E. J. Newman, “Power-law distributions in empirical data” (SIAM Review 2009). As an alternative to the paper, you can read Cosma’s blog post “So You Think You Have a Power Law — Well Isn’t That Special?”, 6/15/2007; or this summary of the results in “Cozy Catastrophes”, 2/15/2012:
I found two identical packs of Skittles, among 468 packs with a total of 27,740 Skittles
> This is a follow-up to a post from earlier this year discussing the likelihood of encountering two identical packs of Skittles, that is, two packs having exactly the same number of candies of each flavor. Under some reasonable assumptions, it was estimated that we should expect to have to inspect “only about 400-500 packs” on average until encountering a first duplicate.
> So, on 12 January of this year, I started buying boxes of packs of Skittles. This past week, “only” 82 days, 13 boxes, 468 packs, and 27,740 individual Skittles later, I found the following identical 2.17-ounce packs:
A Go implementation of Poly1305 that makes sense
> Although it’s really a fraction of the complexity of e.g. elliptic curves, most of the implementations I’ve read look decidedly like magic, mysteriously multiplying values by enchanted constants, and shuffling bits like The Sorcerer’s Apprentice in Fantasia. Even the paper does not explain why and how its design decisions lead to faster code!
> Still, after reverse-engineering what the implementations were doing, I grew convinced that cryptography code could be perfectly understandable if only we commented it.
How to generate uniformly random points on n-spheres and n-balls
> For many Monte Carlo methods, such as those in graphical computing, it is critical to uniformly sample from $d$-dimensional spheres and balls. This post describes over twenty different methods to uniformly random sample from the (surface of) a $d$-dimensional sphere or the (interior of) a $d$-dimensional ball.
Just going to link to the whole blog.
A Deep Dive on RSA Accumulators
> Accumulators are a topic of interest in academia since 1994. Similarly to a Merkle Tree, they are used to cryptographically commit to the knowledge of a set of data. At a later point in time, proving membership of a subset of the dataset in the dataset can be proven by publishing a proof. In Merkle Trees the proof is called a Merkle Branch (or Merkle Proof), and grows logarithmically to the size of the committed data (commit 16 elements, prove inclusion by revealing log_2(16)=4).
> Accumulators on the other hand, allow proving membership in constant size, as well as batching of proofs for multiple elements (which is not a feature of Merkle trees).
> The focus of this post will be on describing the building blocks of RSA Accumulators, how we can construct proofs of (non-)membership as well as batch them across multiple blocks. This particular technique also has applications in UTXO-Based Plasma, and has given birth to the Plasma Prime variant. A lot of effort is being put into designing an accumulator that allows compaction of the UTXO-set in Plasma.