I work on homomorphic encryption (HE or FHE for “fully” homomorphic encryption) and I have written a lot about it on this blog (see the relevant tag). This article is a collection of short answers to questions I see on various threads and news aggregators discussing FHE. Facts If a service uses FHE and can respond to encrypted queries, can’t the service see your query? How is it possible to operate on encrypted data without seeing it?| Math ∩ Programming
Editor’s note: This essay was originally published on Medium on 2016-03-05. I have made minor edits in this republishing and added a few small retrospective notes. 2010–2011 (Year 0) I had just switched my major at Cal Poly State University from computer science to math. I wanted to double major but California was in a budget crisis and a few weeks before I tried submitting my double-major request the Provost for the CSU system put a blanket ban on double majors.| Math ∩ Programming
It’s April Cools! Last year I wrote about parenting, in 2023 about friendship bracelets. and in 2022 about cocktails. This year it’s a bit of a meandering stroll through some ideas around mutual aid and self-reliance. Maternity wards If you walk around the maternity ward at Kaiser Permanente’s Sunnyside medical center outside of Portland, Oregon, you might notice the same two things I did. The first was how many signs were posted on the hallways describing the maternity team’s KRs and...| Math ∩ Programming
In this article I’ll derive a trick used in FHE called sample extraction. In brief, it allows one to partially convert a ciphertext in the Ring Learning With Errors (RLWE) scheme to the Learning With Errors (LWE) scheme. Here are some other articles I’ve written about other FHE building blocks, though they are not prerequisites for this article. Modulus Switching in LWE Key Switching in LWE The Gadget Decomposition in FHE Negacyclic Polynomial Multiplication Estimating the Security of Rin...| Math ∩ Programming
This article was written by my colleague, Cathie Yun. Cathie is an applied cryptographer and security engineer, currently working with me to make fully homomorphic encryption a reality at Google. She’s also done a lot of cool stuff with zero knowledge proofs. In previous articles, we’ve discussed techniques used in Fully Homomorphic Encryption (FHE) schemes. The basis for many FHE schemes, as well as other privacy-preserving protocols, is the Learning With Errors (LWE) problem.| Math ∩ Programming
Welcome to the 209th Carnival of Mathematics! 209 has a few distinctions, including being the smallest number with 6 representations as a sum of 3 positive squares: $$\begin{aligned}209 &= 1^2 + 8^2 + 12^2 \\\ &= 2^2 + 3^2 + 14^2 \\\ &= 2^2 + 6^2 + 13^2 \\\ &= 3^2 + 10^2 + 10^2 \\\ &= 4^2 + 7^2 + 12^2 \\\ &= 8^2 + 8^2 + 9^2 \end{aligned}$$ As well as being the 43rd Ulam number, the number of partitions of 16 into relatively prime parts and the number of partitions of 63 into squares.| Math ∩ Programming
Last time we covered an operation in the LWE encryption scheme called modulus switching, which allows one to switch from one modulus to another, at the cost of introducing a small amount of extra noise, roughly $\sqrt{n}$, where $n$ is the dimension of the LWE ciphertext. This time we’ll cover a more sophisticated operation called key switching, which allows one to switch an LWE ciphertext from being encrypted under one secret key to another, without ever knowing either secret key.| Math ∩ Programming
The Learning With Errors problem is the basis of a few cryptosystems, and a foundation for many fully homomorphic encryption (FHE) schemes. In this article I’ll describe a technique used in some of these schemes called modulus switching. In brief, an LWE sample is a vector of values in $\mathbb{Z}/q\mathbb{Z}$ for some $q$, and in LWE cryptosystems an LWE sample can be modified so that it hides a secret message $m$.| Math ∩ Programming
This is a draft of a chapter from my in-progress book, Practical Math for Programmers: A Tour of Mathematics in Production Software. Tip: Determine an aggregate statistic about a sensitive question, when survey respondents do not trust that their responses will be kept secret. Solution: import random def respond_privately(true_answer: bool) -> bool: '''Respond to a survey with plausible deniability about your answer.''' be_honest = random.random() < 0.5 random_answer = random.random() < 0.| Math ∩ Programming
Previous posts in this series: Silent Duels and an Old Paper of Restrepo Silent Duels—Parsing the Construction Silent Duels—Constructing the Solution part 1 Since it’s been three years since the last post in this series, and the reason for the delay is that I got totally stuck on the implementation. I’m publishing this draft article as partial progress until I can find time to work on it again. If you haven’t read the last post, please do.| Math ∩ Programming
tl;dr: I’m writing a new book, sign up for the announcements mailing list. I’ve written exactly zero new technical blog posts this year because I’ve been spending all my writing efforts on my next book, Practical Math for Programmers (PMFP, subtitle: A Tour of Mathematics in Production Software). I’ve written a little bit about it in my newsletter, Halfspace. There I rant, critique, brainstorm, and wax poetic about math and software.| Math ∩ Programming
I learned of a neat result due to Kevin Ventullo that uses group actions to study the structure of hash functions for unordered sets and multisets. This piqued my interest because a while back a colleague asked me if I could think of any applications of “pure” group theory to practical computer programming that were not cryptographic in nature. He meant, not including rings, fields, or vector spaces whose definitions happen to be groups when you forget the extra structure.| Math ∩ Programming
Welcome to the 197th Carnival of Mathematics! 197 is an unseemly number, as you can tell by the Wikipedia page which currently says that it has “indiscriminate, excessive, or irrelevant examples.” How deviant. It’s also a Repfigit, which means if you start a fibonacci-type sequence with the digits 1, 9, 7, and then continue with $ a_n = a_{i-3} + a_{i-2} + a_{i-1}$, then 197 shows up in the sequence. Indeed: 1, 9, 7, 17, 33, 57, 107, 197, …| Math ∩ Programming
Recently I’ve been helping out with a linear algebra course organized by Tai-Danae Bradley and Jack Hidary, and one of the questions that came up a few times was, “why should programmers care about the concept of a linear combination?” For those who don’t know, given vectors $ v_1, \dots, v_n$, a linear combination of the vectors is a choice of some coefficients $ a_i$ with which to weight the vectors in a sum $ v = \sum_{i=1}^n a_i v_i$.| Math ∩ Programming
We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded integers Deploying with Docker Performance Profiling Scaling up In the last article we rearchitected the application so that we could run as many search instances as we want in parallel, and speed up the application by throwing more compute resources at the problem. This is good, but comes with a cost. The complexity of this new architecture requires us t...| Math ∩ Programming
We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded integers Deploying with Docker Performance Profiling Last time we made the audacious choice to remove primary keys from the RiemannDivisorSums table for performance reasons. To help with that, we will do two things in this post Reduce the storage footprint of the whole application (it was 60 GiB when it crashed, and we got up to 84 prime factors).| Math ∩ Programming
We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded integers Deploying with Docker In the last article we ran into some performance issues with our deployed docker application. In this article we’ll dig in to see what happened, fix the problem, run into another problem, fix it, and run the search until we rule out RH witness-value-based counterexamples among all numbers with fewer than 85 prime factors.| Math ∩ Programming
We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded Integers In this article we’ll deploy the application on a server, so that it can search for RH counterexamples even when I close my laptop. Servers and containers When deploying applications to servers, reproducibility is crucial. You don’t want your application to depend on the details of the computer it’s running on. This is a higher-level versio...| Math ∩ Programming
In a recent newsletter article I complained about how researchers mislead about the applicability of their work. I gave SAT solvers as an example. People provided interesting examples in response, but what was new to me was the concept of SMT (Satisfiability Modulo Theories), an extension to SAT. SMT seems to have more practical uses than vanilla SAT (see the newsletter for details). I wanted to take some time to explore SMT solvers, and I landed on Z3, an open-source SMT solver from Microsoft.| Math ∩ Programming
We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search strategies In the last article, we improved our naive search from “try all positive integers” to enumerate a subset of integers (superabundant numbers), which RH counterexamples are guaranteed to be among. These numbers grow large, fast, and we quickly reached the limit of what 64 bit integers can store. Unbounded integer arithmetic is possible on computers, but it requir...| Math ∩ Programming
We’re glibly searching for counterexamples to the Riemann Hypothesis, to trick you into learning about software engineering principles. In the first two articles we configured a testing framework and showed how to hide implementation choices behind an interface. Next, we’ll improve the algorithm’s core routine. As before, I’ll link to specific git commits in the final code repository to show how the project evolves. Superabundant numbers A superabundant number $ n$ is one which has ...| Math ∩ Programming
In the last article we set up pytest for a simple application that computes divisor sums $ \sigma(n)$ and tries to disprove the Riemann Hypothesis. In this post we’ll show how to extend the application as we add a database dependency. The database stores the computed sums so we can analyze them after our application finishes. As in the previous post, I’ll link to specific git commits in the final code repository to show how the project evolves.| Math ∩ Programming
Some mathy-programmy people tell me they want to test their code, but struggle to get set up with a testing framework. I suspect it’s due to a mix of: There are too many choices with a blank slate. Making slightly wrong choices early on causes things to fail in unexpected ways. I suspect the same concerns apply to general project organization and architecture. Because Python is popular for mathy-programmies, I’ll build a Python project that shows how I organize my projects and and test my...| Math ∩ Programming
In my book, A Programmer’s Introduction to Mathematics, I describe the Taylor Series as a “hammer for every nail.” I learned about another nail in the design of modern smartphone accelerometers from “Eight Amazing Engineering Stories” by Hammack, Ryan, and Ziech, which I’ll share here. These accelerometers are designed using a system involving three plates, which correspond to two capacitors. A quick recap on my (limited) understanding of how capacitors work.| Math ∩ Programming
In my book I discuss the importance of context in reading and writing mathematics. An early step in becoming comfortable with math is deciphering the syntax of mathematical expressions. Another is in connecting the symbols to their semantic meanings. Embedded in these is the subproblem of knowing what to call the commonly used symbols. The more abstract you go, the more exotic the symbols tend to get. Wikipedia has an excellent list for deciphering those symbols that have a typically well-und...| Math ∩ Programming
This essay is a slightly modified version of the closing chapter of A Programmer’s Introduction to Mathematics. We are no longer constrained by pencil and paper. The symbolic shuffle should no longer be taken for granted as the fundamental mechanism for understanding quantity and change. Math needs a new interface. –Bret Victor, “Kill Math” Math is a human activity. It’s messy and beautiful, complicated and elegant, useful and bull-headedly frustrating. But in reading this book, A P...| Math ∩ Programming
The Second Edition of A Programmer’s Introduction to Mathematics is now available on Amazon. The second edition includes a multitude of fixes to typos and some technical errata, thanks to my readers who submitted over 200 errata. Readers who provided names are credited in the front matter. I also added new exercises, and three new appendices: a notation table to augment the notation index, a summary of elementary formal logic, and an annotated list of further reading.| Math ∩ Programming
A year ago today I self-published “A Programmer’s Introduction to Mathematics” (PIM). In this short note I want to describe the success it’s had, summarize the complaints of some readers and the praise of others, and outline what’s next. Since publication PIM has sold over 11,000 copies. A rough chart showing the sales of paperback and ebook copies of PIM. Here’s a table: Month Paperback Ebook Total 2018-12 4,323 1,866 6,189 2019-01 1,418 258 1,676 2019-02 852 128 980 2019-03 762 ...| Math ∩ Programming
Previous posts in this series: Silent Duels and an Old Paper of Restrepo Silent Duels—Parsing the Construction Last time we waded into Restrepo’s silent duel paper. You can see the original and my re-typeset version on Github along with all of the code in this series. We digested Section 2 and a bit further, plotting some simplified examples of the symmetric version of the game. I admit, this paper is not an easy read.| Math ∩ Programming
At Google, our organization designs, owns, and maintains a number of optimization models that automate the planning of Google’s datacenter growth and health. As is pretty standard in supply chain optimization and planning, these models are often integer linear programs. It’s a core competency of operations research, after all. One might think, “Large optimization problems? That sounds hard!” But it’s actually far from the hardest part of the job. In fact, it’s one of the few excit...| Math ∩ Programming
Our hero, a mathematician, is writing notes in LaTeX and needs to convert it to a format that her blog platform accepts. She’s used to using dollar sign delimiters for math mode, but her blog requires \( \) and \[ \]. Find-and-replace fails because it doesn’t know about which dollar sign is the start and which is the end. She knows there’s some computer stuff out there that could help, but she doesn’t have the damn time to sort through it all.| Math ∩ Programming
Last time we discussed the setup for the silent duel problem: two players taking actions in $ [0,1]$, player 1 gets $ n$ chances to act, player 2 gets $ m$, and each knows their probability of success when they act. The solution is in a paper of Rodrigo Restrepo from the 1950s. In this post I’ll start detailing how I study this paper, and talk through my thought process for approaching a bag of theorems and proofs.| Math ∩ Programming
Two men start running at each other with loaded pistols, ready to shoot! It’s a foggy morning for a duel. Newton and Leibniz have decided this macabre contest is the only way to settle their dispute over who invented Calculus. Each pistol is fitted with a silencer and has a single bullet. Neither can tell when the other has attempted a shot, unless, of course, they are hit. Newton and Leibniz both know that the closer they get to their target, the higher the chance of a successful shot.| Math ∩ Programming
For the last four years I’ve been working on a book for programmers who want to learn mathematics. It’s finally done, and you can buy it today. The website for the book is pimbook.org, which has purchase links—paperback and ebook—and a preview of the first pages. You can see more snippets later in the book on the Amazon listing’s “Look Inside” feature. If you’re a programmer who wants to learn math, this book is written specifically for you!| Math ∩ Programming
Mathematics students often hear about the classic “blue-eyed islanders” puzzle early in their career. If you haven’t seen it, read Terry Tao’s excellent writeup linked above. The solution uses induction and the idea of *common knowledge—*I know X, and you know that I know X, and I know that you know that I know X, and so on—to make a striking inference from a seemingly useless piece of information. Recreational mathematics is also full of puzzles involving prisoners wearing colore...| Math ∩ Programming
Over at Math3ma, Tai-Danae Bradley shared the following puzzle, which she also featured in a fantastic (spoiler-free) YouTube video. If you’re seeing this for the first time, watch the video first. Consider a square in the xy-plane, and let A (an “assassin”) and T (a “target”) be two arbitrary-but-fixed points within the square. Suppose that the square behaves like a billiard table, so that any ray (a.k.a “shot”) from the assassin will bounce off the sides of the square, with th...| Math ∩ Programming
Every now and then I hear some ridiculous things about the equals symbol. Some large subset of programmers—perhaps related to functional programmers, perhaps not—seem to think that = should only and ever mean “equality in the mathematical sense.” The argument usually goes, Functional programming gives us back that inalienable right to analyze things by using mathematics. Never again need we bear the burden of that foul mutant x = x+1! No novice programmer—nay, not even a mathematician!| Math ∩ Programming
Tai-Danae Bradley is one of the hosts of PBS Infinite Series, a delightful series of vignettes into fun parts of math. The video below is about the same of SET, a favorite among mathematicians. Specifically, Tai-Danae explains how SET cards lie in (using more technical jargon) a vector space over a finite field, and that valid sets correspond to lines. If you don’t immediately know how this would work, watch the video.| Math ∩ Programming
Problem: Compute distance between points with uncertain locations (given by samples, or differing observations, or clusters). For example, if I have the following three “points” in the plane, as indicated by their colors, which is closer, blue to green, or blue to red? It’s not obvious, and there are multiple factors at work: the red points have fewer samples, but we can be more certain about the position; the blue points are less certain, but the closest non-blue point to a blue point ...| Math ∩ Programming
When NP-hardness pops up on the internet, say because some silly blogger wants to write about video games, it’s often tempting to conclude that the problem being proved NP-hard is actually very hard! “Scientists proved Super Mario is NP-hard? I always knew there was a reason I wasn’t very good at it!” Sorry, these two are unrelated. NP-hardness means hard in a narrow sense this post should hopefully make clear. After that, we’ll explore what “hard” means in a mathematical sense ...| Math ∩ Programming
Binary search is one of the most basic algorithms I know. Given a sorted list of comparable items and a target item being sought, binary search looks at the middle of the list, and compares it to the target. If the target is larger, we repeat on the smaller half of the list, and vice versa. With each comparison the binary search algorithm cuts the search space in half. The result is a guarantee of no more than $ \log(n)$ comparisons, for a total runtime of $ O(\log n)$.| Math ∩ Programming
Previously in this series: Linear programming and healthy diets — Part 1 Linear programing and the simplex algorithm Foods of the Father My dad’s an interesting guy. Every so often he picks up a health trend and/or weight loss goal that would make many people’s jaw drop. For example, we once went on a 5-day, 50-mile backpacking trip in the Grand Tetons, and my dad brought one packet of Lipton’s Side Dishes noodle soup per day for dinner, and had vitamin tablets for the rest of his sus...| Math ∩ Programming
Last week I was in Boston for the Geometry of Redistricting workshop. It was an optimistic gathering of over 500 mathematicians, computer scientists, lawyers, policy makers, teachers, and interested people of all stripes. There was a ton of information in the talks and subsequent discussions. I’ll try to distill the main ideas and avenues for research as best I can. Unfortunately, due to how preliminary most of the technical work is, I won’t be presenting any concrete code or algorithms.| Math ∩ Programming
In this living document, I will document reactions to uses of homomorphic encryption by members of the public. By “member of the public,” I mean people who may be technical, but are not directly involved in the development or deployment of homomorphic encryption systems. This includes journalists, bloggers, aggregator comment threads, and social media posts. My main goal is to understand how the public perceives the risks and benefits of using homomorphic encryption.| Math ∩ Programming
Editor’s note: This essay was originally published in 2019. I have made minor edits in this republishing. There was a MathOverflow thread about mathematically interesting games for 5–6 year olds. A lot of the discussion revolved around how young age 5 really is, and how we should temper expectations because we don’t really remember what it’s like to be 5. In response to an enormous answer by Alexander Chervov, user LSpice quipped, “‘Daddy, daddy, let’s play another in the infini...| Math ∩ Programming
Welcome to the 233rd Carnival of Mathematics! Who can forget 233, the 6th Fibonacci prime? Hey, not all numbers are interesting. Don’t ask me about the smallest positive uninteresting number. You can’t make it interesting with your feeble mind tricks! Anyway, on to the fun. Provers and Shakers The big discovery this month was a new largest known prime number, $2^{136279841} - 1$, as reported by the Great Internet Mersenne Prime Search.| Math ∩ Programming
This article will explain how the blog is organized at a technical level, and show how I implemented various IndieWeb features. Table of Contents: Motivation Structure and Deployment Static search index Running scripts via GitHub Actions Social media syndication and the “shortform” section Links to syndicated versions at the end of each post Warning for a too-long first paragraph Triggering this workflow automatically after deployment Blogroll (the “What I’m Reading” page) Chrome ex...| Math ∩ Programming
I’m Jeremy Kun. I’m currently a staff software engineer at Google and I live in Portland, Oregon.| Math ∩ Programming
In my recent overview of homomorphic encryption, I underemphasized the importance of data layout when working with arithmetic (SIMD-style) homomorphic encryption schemes. In the FHE world, the name given to data layout strategies is called “packing,” because it revolves around putting multiple plaintext data into RLWE ciphertexts in carefully-chosen ways that mesh well with the operations you’d like to perform. By “mesh well” I mean it reduces the number of extra multiplications and...| Math ∩ Programming
In my recent overview of homomorphic encryption, I underemphasized the importance of data layout when working with arithmetic (SIMD-style) homomorphic encryption schemes. In the FHE world, the name given to data layout strategies is called “packing,” because it revolves around putting multiple plaintext data into RLWE ciphertexts in carefully-chosen ways that mesh well with the operations you’d like to perform. By “mesh well” I mean it reduces the number of extra multiplications and...| Math ∩ Programming
Table of Contents In this article I’ll show how to use PDLL, a tool for defining MLIR patterns, which itself is built with MLIR. PDLL is intended to be a replacement for defining patterns in tablegen, though there are few public examples of its use. In fact, the main impetus for PDLL is that tablegen makes it difficult to express things like: Operations that return multiple results Operations with regions Operations with variadic operands Arithmetic on static values While not all these feat...| Math ∩ Programming
Last update: 2024-08-08T21:56:17-0700 In this living document, I will list all production systems I’m aware of that use fully homomorphic encryption (FHE). For background on FHE, see my overview of the field. If you have any information about production FHE systems not in this list, or corrections to information in this list, please send me an email with sufficient detail allow the claim to be publicly verified. Table of contents:| Math ∩ Programming
POSSE stands for Publish (on your) Own Site, Syndicate Elsewhere. I first heard about it from Cory Doctorow. I’m experimenting with automation to convert posts tagged shortform into Mastodon threads (I’m mathstodon.xyz/@j2kun). I’m using Hugo as a static site generator, with the source a (private) GitHub repository, and Netlify for deployments. After a deployment, Netlify calls a serverless function that hits the GitHub API with a POST request to trigger a GitHub action workflow.| Math ∩ Programming
I’ve been learning recently about how to approximate functions by low-degree polynomials. This is useful in fully homomorphic encryption (FHE) in the context of “arithmetic FHE” (see my FHE overview article), where the computational model makes low-degree polynomials cheap to evaluate and non-polynomial functions expensive or impossible. In browsing the state of the art I came across two interesting things. The first is the software package lolremez that implements polynomial (and ratio...| Math ∩ Programming
About two years ago, I switched teams at Google to focus on fully homomorphic encryption (abbreviated FHE, or sometimes HE). Since then I’ve got to work on a lot of interesting projects, learning along the way about post-quantum cryptography, compiler design, and the ins and outs of fully homomorphic encryption. If you’ve heard about FHE and you’re a software person, you’ve probably heard two things: it lets you run programs directly on encrypted data without ever decrypting it; and i...| Math ∩ Programming
It’s April Cools! Last year I wrote about friendship bracelets and the year before about cocktails. This year it’s parenting. Parenting articles are a dime a dozen and always bury the lede behind a long story. I’ll skip that. How to think about your child and your role as a parent These are framing devices. Concrete things to do to work toward these are in the next section. I will refer to the numbers for each action to show what principle it is applying.| Math ∩ Programming
My next book will be Practical Math for Programmers Searching for Riemann Hypothesis Counterexamples Linear Programming and Healthy Diets Hybrid Images Bezier Curves and Picasso Correcting Errors in Data| Math ∩ Programming
There’s a family of tabletop games that are based directly on a nontrivial mathematics problem. As a casual and fun way to inaugurate my new blog (migrated from Wordpress to Hugo, after my work on getting better LaTeX mathmode support in Hugo), I thought I’d write a short listicle about them, so that I have a place to add more as I find them, as well as give the shortest canonical description of the associated math problem.| Math ∩ Programming
Table of Contents In this article we’ll implement a global optimization pass, and show how to use the dataflow analysis framework to verify the results of our optimization. The code for this article is in this pull request, and as usual the commits are organized to be read in order. The noisy arithmetic problem This demonstration is based on a simplified model of computation relevant to the HEIR project. You don’t need to be familiar with that project to follow this article, but if you’...| Math ∩ Programming
Table of Contents In the last article we lowered our custom poly dialect to standard MLIR dialects. In this article we’ll continue lowering it to LLVM IR, exporting it out of MLIR to LLVM, and then compiling to x86 machine code. The code for this article is in this pull request, and as usual the commits are organized to be read in order. Defining a Pipeline The first step in lowering to machine code is to lower to an “exit dialect.| Math ∩ Programming
Table of Contents In previous articles we defined a dialect, and wrote various passes to optimize and canonicalize a program using that dialect. However, one of the main tenets of MLIR is “incremental lowering,” the idea that there are lots of levels of IR granularity, and you incrementally lower different parts of the IR, only discarding information when it’s no longer useful for optimizations. In this article we’ll see the first step of that: lowering the poly dialect to a combinati...| Math ∩ Programming
Can you find a set of cards among these six, such that the socks on the chosen cards can be grouped into matching pairs? (Duplicate pairs of the same sock are OK) Spoilers: If the cards are indexed as 1 2 3 4 5 6 Then the following three subsets work: $\{ 1, 2, 4, 5, 6 \}$, $\{ 2, 3, 6 \}$, and $\{ 1, 3, 4, 5 \}$.| Math ∩ Programming
Table of Contents In a previous article we defined folding functions, and used them to enable some canonicalization and the sccp constant propagation pass for the poly dialect. This time we’ll see how to add more general canonicalization patterns. The code for this article is in this pull request, and as usual the commits are organized to be read in order. Why is Canonicalization Needed? MLIR provides folding as a mechanism to simplify an IR, which can result in simpler, more efficient ops (e.| Math ∩ Programming
In cryptography, we need a distinction between a cleartext and a plaintext. A cleartext is a message in its natural form. A plaintext is a cleartext that is represented in a specific way to prepare it for encryption in a specific scheme. The process of taking a cleartext and turning it into a plaintext is called encoding, and the reverse is called decoding. In homomorphic encryption, the distinction matters. Cleartexts are generally all integers, though the bit width of allowed integers can b...| Math ∩ Programming
Table of Contents Last time we defined folders and used them to enable some canonicalization and the sccp constant propagation pass for the poly dialect. This time we’ll add some additional safety checks to the dialect in the form of verifiers. The code for this article is in this pull request, and as usual the commits are organized to be read in order. Purpose of a verifier Verifiers ensure the types and operations in a concrete MLIR program are well-formed.| Math ∩ Programming
Table of Contents Last time we saw how to use pre-defined MLIR traits to enable upstream MLIR passes like loop-invariant-code-motion to apply to poly programs. We left out -sccp (sparse conditional constant propagation), and so this time we’ll add what is needed to make that pass work. It requires the concept of folding. The code for this article is in this pull request, and as usual the commits are organized to be read in order.| Math ∩ Programming
Table of Contents Last time we defined a new dialect poly for polynomial arithmetic. This time we’ll spruce up the dialect by adding some pre-defined MLIR traits, and see how the application of traits enables some general purpose passes to optimize poly programs. The code for this article is in this pull request, and as usual the commits are organized to be read in order. Traits and Loop Invariant Code Motion As a compiler toolchain, MLIR heavily emphasizes code reuse.| Math ∩ Programming
Problem: Compute 16% of 25 in your head. Solution: 16% of 25 is equivalent to 25% of 16, which is clearly 4. This is true for all numbers: $x\%$ of $y$ is always equal to $y\%$ of $x$. The first one is $\frac{x}{100} y$ and the second is $\frac{y}{100}x$, and because multiplication is commutative and associative, both are equal to $(x \cdot y) / 100$. You can pick the version that is easiest.| Math ∩ Programming
Table of Contents In the last article in the series, we migrated the passes we had written to use the tablegen code generation framework. That was a preface to using tablegen to define dialects. In this article we’ll define a dialect that represents arithmetic on single-variable polynomials, with coefficients in $\mathbb{Z} / 2^{32} \mathbb{Z}$ (32-bit unsigned integers). The code for this article is in this pull request, and as usual the commits are organized to be read in order.| Math ∩ Programming
Table of Contents In the last article in this series, we defined some custom lowering passes that modified an MLIR program. Notably, we accomplished that by implementing the required interfaces of the MLIR API directly. This is not the way that most MLIR developers work. Instead, they use a code generation tool called tablegen to generate boilerplate for them, and then only add the implementation methods that are custom to their work.| Math ∩ Programming
Table of Contents This series is an introduction to MLIR and an onboarding tutorial for the HEIR project. Last time we saw how to run and test a basic lowering. This time we will write some simple passes to illustrate the various parts of the MLIR API and the pass infrastructure. As mentioned previously, the main work in MLIR is defining passes that either optimize part of a program, lower from parts of one dialect to others, or perform various normalization and canonicalization operations.| Math ∩ Programming
Table of Contents Last time, we covered a Bazel build system setup for an MLIR project. This time we’ll give an overview of a simple lowering and show how end-to-end tests work in MLIR. All of the code for this article is contained in this pull request on GitHub, and the commits are nicely organized and quite readable. Two of the central concepts in MLIR are dialects and lowerings. These are the scaffolding within which we can do the truly interesting parts of a compiler—that is, the opti...| Math ∩ Programming
Table of Contents As we announced recently, my team at Google has started a new effort to build production-worthy engineering tools for Fully Homomorphic Encryption (FHE). One focal point of this, and one which I’ll be focusing on as long as Google is willing to pay me to do so, is building out a compiler toolchain for FHE in the MLIR framework (Multi-Level Intermediate Representation). The project is called Homomorphic Encryption Intermediate Representation, or HEIR.| Math ∩ Programming
Today my team at Google published an article on Google’s Developers Blog with some updates on what we’ve been doing with fully homomorphic encryption (FHE). There’s fun stuff in there, including work on video processing FHE, compiling ML models to FHE, an FHE implementation for TPUs, and improvements to the compiler I wrote about earlier this year. TODO: add mower gif video A simple object movement tracking algorithm in FHE, tracking a runaway lawn mower from a Nest camera.| Math ∩ Programming
Before I discovered math, I was a first year undergrad computer science student taking Electrical Engineering 101. The first topic I learned was what bits and boolean gates are, and the second was the two’s complement representation of a negative n-bit integer. At the time two’s complement seemed to me like a bizarre quirk of computer programming, with minutiae you just had to memorize. If the leading bit is 1, it’s negative, and otherwise it’s positive.| Math ∩ Programming
It’s April Cools again. For a few summers in high school and undergrad, I was a day camp counselor. I’ve written before about how it helped me develop storytelling skills, but recently I thought of it again because, while I was cleaning out a closet full of old junk, I happened upon a bag of embroidery thread. While stereotypically used to sew flowers into a pillowcase or write “home sweet home” on a hoop, at summer camps embroidery thread is used to make friendship bracelets.| Math ∩ Programming
Back in May of 2022 I transferred teams at Google to work on Fully Homomorphic Encryption (newsletter announcement). Since then I’ve been working on a variety of projects in the space, including being the primary maintainer on github.com/google/fully-homomorphic-encryption, which is an open source FHE compiler for C++. This article will be an introduction to how to use it to compile programs to FHE, as well as a quick overview of its internals.| Math ∩ Programming
In this article I’ll cover three techniques to compute special types of polynomial products that show up in lattice cryptography and fully homomorphic encryption. Namely, the negacyclic polynomial product, which is the product of two polynomials in the quotient ring $\mathbb{Z}[x] / (x^N + 1)$. As a precursor to the negacyclic product, we’ll cover the simpler cyclic product. All of the Python code written for this article is on GitHub.| Math ∩ Programming
Problem: Compute the product of two polynomials efficiently. Solution: import numpy from numpy.fft import fft, ifft def poly_mul(p1, p2): """Multiply two polynomials. p1 and p2 are arrays of coefficients in degree-increasing order. """ deg1 = p1.shape[0] - 1 deg2 = p1.shape[0] - 1 # Would be 2*(deg1 + deg2) + 1, but the next-power-of-2 handles the +1 total_num_pts = 2 * (deg1 + deg2) next_power_of_2 = 1 << (total_num_pts - 1).| Math ∩ Programming
It’s April Cools! We’re taking back April Fools. When I was younger I had a strange relationship with alcohol, not because of any sort of trauma, but because I found it decidedly boring and disgusting to the taste. I didn’t drink in high school, didn’t enjoy parties in college, and didn’t care for tailgating or other sports-based events where drinking was common. I also never enjoyed wine—red is too tannic, white is just meh—and almost all beer tastes awful to me (lambic is a de...| Math ∩ Programming
Lately I’ve been studying Fully Homomorphic Encryption, which is the miraculous ability to perform arbitrary computations on encrypted data without learning any information about the underlying message. It’s the most comprehensive private computing solution that can exist (and it does exist!). The first FHE scheme by Craig Gentry was based on ideal lattices and was considered very complex (I never took the time to learn how it worked). Some later schemes (GSW = Gentry-Sahai-Waters) are ba...| Math ∩ Programming
Recently my employer (Google) forced me to switch to Mercurial instead of my usual version control system, git. The process of switching sparked a few discussions between me and my colleagues about the value of various version control systems. A question like “what benefit does git provide over Mercurial” yielded no clear answers, suggesting many developers don’t know. An informal Twitter survey didn’t refute this claim. A distinguished value git provides me is the ability to sculpt c...| Math ∩ Programming
We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded integers Deploying with Docker Performance Profiling Scaling up Productionizing In the last article we added a menagerie of “production readiness” features like continuous integration tooling (automating test running and static analysis), alerting, and a simple deployment automation. Then I let it loose on AWS, got extremely busy with buying a house, ...| Math ∩ Programming