Modulus Switching in LWE

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{Z} for some q, and in LWE cryptosystems an LWE sample can be modified so that it hides a secret message m. Modulus switching allows one to convert an LWE encryption from having entries in \mathbb{Z}/q{Z} to entries in some other \mathbb{Z}/q'{Z}, i.e., change the modulus from q to q' < q.

The reason you’d want to do this are a bit involved, so I won’t get into them here and instead back-reference this article in the future.

LWE encryption

Briefly, the LWE encryption scheme I’ll use has the following parameters:

  • A plaintext space \mathbb{Z}/q\mathbb{Z}, where q \geq 2 is a positive integer. This is the space that the underlying message comes from.
  • An LWE dimension n \in \mathbb{N}.
  • A discrete Gaussian error distribution D with a mean of zero and a fixed standard deviation.

An LWE secret key is defined as a vector in \{0, 1\}^n (uniformly sampled). An LWE ciphertext is defined as a vector a = (a_1, \dots, a_n), sampled uniformly over (\mathbb{Z} / q\mathbb{Z})^n, and a scalar b = \langle a, s \rangle + m + e, where e is drawn from D and all arithmetic is done modulo q.

Without the error term, an attacker could determine the secret key from a polynomial-sized collection of LWE ciphertexts with something like Gaussian elimination. The set of samples looks like a linear (or affine) system, where the secret key entries are the unknown variables. With an error term, the problem of solving the system is believed to be hard, and only exponential time/space algorithms are known.

However, the error term in an LWE encryption encompasses all of the obstacles to FHE. For starters, if your message is m=1 and the error distribution is wide (say, a standard deviation of 10), then the error will completely obscure the message from the start. You can’t decrypt the LWE ciphertext because you can’t tell if the error generated in a particular instance was 9 or 10. So one thing people do is have a much smaller cleartext space (actual messages) and encode cleartexts as plaintexts by putting the messages in the higher-order bits of the plaintext space. E.g., you can encode 10-bit messages in the top 10 bits of a 32-bit integer, and leave the remaining 22 bits of the plaintext for the error distribution.

Moreover, for FHE you need to be able to add and multiply ciphertexts to get the corresponding sum/product of the underlying plaintexts. One can easily see that adding two LWE ciphertexts produces an LWE ciphertext of the sum of the plaintexts (multiplication is harder and beyond the scope of this article). Summing ciphertexts also sums the error terms together. So the error grows with each homomorphic operation, and eventually the error may overtake the message, at which point decryption fails. How to deal with this error accumulation is 99% of the difficulty of FHE.

Finally, because the error can be negative, even if you store a message in the high-order bits of the plaintext, you can’t decrypt by simply clearing the low order error bits. In that case an error of -1 would result in a corrupted message. Instead, to decrypt, we round the value b - \langle a, s \rangle = m + e to the nearest multiple of 2^k, where $k$ is the number of bits “reserved” for error, as described above. In particular, decryption will only succeed if the error is small enough in absolute value. So to make this work in practice, one must coordinate the encoding scheme (how many bits to reserve for error), the dimension of the vector a, and the standard deviation of the error distribution.

Modulus switching

With a basic outline of an LWE ciphertext, we can talk about modulus switching.

Start with an LWE ciphertext for the plaintext m. Call it (a_1, \dots, a_n, b) \in (\mathbb{Z}/q\mathbb{Z})^{n+1}, where

\displaystyle b = \left ( \sum_{i=1}^n a_i s_i \right ) + m + e_{\textup{original}}

Given q' < q, we would like to produce a vector (a'_1, \dots, a'_n, b') \in (\mathbb{Z}/q'\mathbb{Z})^{n+1} (all that has changed is I’ve put a prime on all the terms to indicate which are changing, most notably the new modulus q') that also encrypts m, without knowing m or e_{\textup{original}}, i.e., without access to the secret key.

Failed attempt: why not simply reduce each entry in the ciphertext vector modulo q'? That would set a'_i = a_i \mod q' and b' = b \mod q'. Despite the fact that this operation produces a perfectly valid equation, it won’t work. The problem is that taking m \mod q' destroys part or all of the underlying message. For example, say x is a 12-bit number stored in the top 12 bits of the plaintext, i.e., m = x \cdot 2^{20}. If q' = 2^{15}, then the message is a multiple of q' already, so the proposed modulus produces zero.

For this reason, we can’t hope to perfectly encrypt m, as the output ciphertext entries may not have a modulus large enough to represent m at all. Rather, we can only hope to encrypt something like “the message x that’s encoded in m, but instead with x stored in lower order bits than m originally used.” In more succinct terms, we can hope to encrypt m' = m q' / q. Indeed, the operation of m \mapsto m q' / q shifts up by \log_2(q') many bits (temporarily exceeding the maximum allowable bit length), and then shifting down by \log_2(q) many bits.

For example, say the number x=7 is stored in the top 3 bits of a 32-bit unsigned integer (q = 2^{32}), i.e., m = 7 \cdot 2^{29} and q' = 2^{10}. Then m q' / q = 7 \cdot 2^{29} \cdot 2^{10} / 2^{32} = 7 \cdot 2^{29+10 - 32} = 7 \cdot 2^7, which stores the same underlying number x=7, but in the top three bits of a 10-bit message. In particular, x is in the same “position” in the plaintext space, while the plaintext space has shrunk around it.

Side note: because of this change to the cleartext-to-plaintext encoding, the decryption/decoding steps before and after a modulus switch are slightly different. In decryption you use different moduli, and in decoding you round to different powers of 2.

So the trick is instead to apply z \mapsto z q' / q to all the entries of the LWE ciphertext vector. However, because the entries like a_i use the entire space of bits in the plaintext, this transformation will not necessarily result in an integer. So we can round the result to an integer and analyze that. The final proposal for a modulus switch is

\displaystyle a'_i = \textup{round}(a_i q' / q)

\displaystyle b' = \textup{round}(b q' / q)

Because the error growth of LWE ciphertexts permeates everything, in addition to proving this transformation produces a valid ciphertext, we also have to understand how it impacts the error term.

Analyzing the modulus switch

The statement summarizing the last section:

Theorem: Let \mathbf{c} = (a_1, \dots, a_n, b) \in (\mathbb{Z}/q\mathbb{Z})^{n+1} be an LWE ciphertext encrypting plaintext m with error term e_\textup{original}. Let q' < q. Then c' = \textup{round}(\mathbf{c} q' / q) (where rounding is performed entrywise) is an LWE encryption of m' = m q' / q, provided m' is an integer.

Proof. The only substantial idea is that \textup{round}(x) = x + \varepsilon, where |\varepsilon| \leq 0.5. This is true by the definition of rounding, but that particular way to express it allows us to group the error terms across a sum-of-rounded-things in isolation, and then everything else has a factor of q'/q that can be factored out. Let’s proceed.

Let c' = (a'_1, \dots, a'_n, b'), where a'_i = \textup{round}(a_i q' / q) and likewise for b'. need to show that b' = \left ( \sum_{i=1}^n a'_i s_i \right ) + m q' / q + e_{\textup{new}}, where e_{\textup{new}} is a soon-to-be-derived error term.

Expanding b' and using the “only substantial idea” above, we get

\displaystyle b' = \textup{round}(b q' / q) = bq'/q + \varepsilon_b

For some \varepsilon_b with magnitude at most 1/2. Continuing to expand, and noting that b is related to the a_i only modulo q, we have

\displaystyle \begin{aligned} b' &= bq'/q + \varepsilon_b \\ b' &= \left ( \left ( \sum_{i=1}^n a_i s_i \right ) + m + e_{\textup{original}} \right ) \frac{q'}{q} + \varepsilon_b \mod q \end{aligned}

Because we’re switching moduli, it makes sense to rewrite this over the integers, which means we add a term Mq for some integer M and continue to expand

\displaystyle \begin{aligned} b' &= \left ( \left ( \sum_{i=1}^n a_i s_i \right ) + m + e_{\textup{original}} + Mq \right ) \frac{q'}{q} + \varepsilon_b \\ &= \left ( \sum_{i=1}^n \left ( a_i \frac{q'}{q} \right) s_i \right ) + m \frac{q'}{q} + e_{\textup{original}}\frac{q'}{q} + Mq \frac{q'}{q} + \varepsilon_b \\ &= \left ( \sum_{i=1}^n \left ( a_i \frac{q'}{q} \right) s_i \right ) + m' + e_{\textup{original}}\frac{q'}{q} + Mq' + \varepsilon_b \end{aligned}

The terms with a_i are still missing their rounding, so, just like b', rewrite a'_i = a_i q'/q + \varepsilon_i as a_i q'/q = a'_i - \varepsilon_i, expanding, simplifying, and finally reducing modulo q' to get

\displaystyle \begin{aligned} b' &= \left ( \sum_{i=1}^n \left ( a'_i - \varepsilon_i \right) s_i \right ) + m' + e_{\textup{original}}\frac{q'}{q} + Mq' + \varepsilon_b \\ &= \left ( \sum_{i=1}^n a'_i s_i \right ) - \left ( \sum_{i=1}^n \varepsilon_i s_i \right) + m' + e_{\textup{original}}\frac{q'}{q} + Mq' + \varepsilon_b \\   &= \left ( \sum_{i=1}^n a'_i s_i \right ) + m' + Mq' +  \left [ e_{\textup{original}}\frac{q'}{q} - \left ( \sum_{i=1}^n \varepsilon_i s_i \right)  + \varepsilon_b \right ] \\   &=  \left ( \sum_{i=1}^n a'_i s_i \right ) + m' + \left [ e_{\textup{original}}\frac{q'}{q} - \left ( \sum_{i=1}^n \varepsilon_i s_i \right)  + \varepsilon_b \right ]  \mod q' \end{aligned}

Define the square bracketed term as e_{\textup{new}}, and we have proved the theorem.


The error after modulus switching is laid out. It’s the original error scaled, plus at most n+1 terms, each of which is at most 1/2. However, note that this is larger than it appears. If the new modulus is, say, q'=1024, and the dimension is n = 512, then in the worst case the error right after modulus switching will leave us only 1 bit left for the message. This is not altogether unrealistic, as production (128-bit) security parameters for LWE put n around 600. But it is compensated for by the fact that the secret s is chosen uniformly at random, and the errors are symmetric around zero. So in expectation only half the bits will be set, and half of the set bits will have a positive error, and half a negative error. Using these facts, you can bound the probability that the error exceeds, say, \sqrt{n \log n} using a standard Hoeffding bound argument. I further believe that the error is bounded by \sqrt{n}. I have verified it empirically, but haven’t been able to quite nail down a proof.

Until next time!

“Practical Math” Preview: Collect Sensitive Survey Responses Privately

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.


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.5
    return true_answer if be_honest else random_answer

def aggregate_responses(responses: List[bool]) -> Tuple[float, float]:
    '''Return the estimated fraction of survey respondents that have a truthful
    Yes answer to the survey question.
    yes_response_count = sum(responses)
    n = len(responses)
    mean = 2 * yes_response_count / n - 0.5
    # Use n-1 when estimating variance, as per Bessel's correction.
    variance = 3 / (4 * (n - 1))
    return (mean, variance)

In the late 1960’s, most abortions were illegal in the United States. Daniel G. Horvitz, a statistician at The Research Triangle Institute in North Carolina and a leader in survey design for social sciences, was tasked with estimating how many women in North Carolina were receiving illegal abortions. The goal was to inform state and federal policymakers about the statistics around abortions, many of which were unreported, even when done legally.

The obstacles were obvious. As Horvitz put it, “a prudent woman would not divulge to a stranger the fact that she was party to a crime for which she could be prosecuted.” [Abernathy70] This resulted in a strong bias in survey responses. Similar issues had plagued surveys of illegal activity of all kinds, including drug abuse and violent crime. Lack of awareness into basic statistics about illegal behavior led to a variety of misconceptions, such as that abortions were not frequently sought out.

Horvitz worked with biostatisticians James Abernathy and Bernard Greenberg to test out a new method to overcome this obstacle, without violating the respondent’s privacy or ability to plausibly deny illegal behavior. The method, called randomized response, was invented by Stanley Warner in 1965, just a few years earlier. [Warner65] Warner’s method was a bit different from what we present in this Tip, but both Warner’s method and the code sample above use the same strategy of adding randomization to the survey.

The mechanism, as presented in the code above, requires respondents to start by flipping a coin. If heads, they answer the sensitive question truthfully. If tails, they flip a second coin to determine how to answer the question—heads resulting in a “yes” answer, tails in a “no” answer. Naturally, the coin flips are private and controlled by the respondent. And so if a respondent answers “Yes” to the question, they may plausibly claim the “Yes” was determined by the coin, preserving their privacy. The figure below describes this process as a diagram.

A branching diagram showing the process a survey respondent takes to record their response.

Another way to describe the outcome is to say that each respondent’s answer is a single bit of information that is flipped with probability 1/4. This is half way between two extremes on the privacy/accuracy tradeoff curve. The first extreme is a “perfectly honest” response, where the bit is never flipped and all information is preserved. The second extreme has the bit flipped with probability 1/2, which is equivalent to ignoring the question and choosing your answer completely at random, losing all information in the aggregate responses. In this perspective, the aggregate survey responses can be thought of as a digital signal, and the privacy mechanism adds noise to that signal.

It remains to determine how to recover the aggregate signal from these noisy responses. In other words, the surveyor cannot know any individual’s true answer, but they can, with some extra work, estimate statistics about the underlying population by correcting for the statistical bias. This is possible because the randomization is well understood. The expected fraction of “Yes” answers can be written as a function of the true fraction of “Yes” answers, and hence the true fraction can be solved for. In this case, where the random coin is fair, that formula is as follows (where \mathbf{P} stands for “the probability of”).

\displaystyle \mathbf{P}(\textup{Yes answer}) = \frac{1}{2} \mathbf{P}(\textup{Truthful yes answer}) + \frac{1}{4}

And so we solve for \mathbf{P}(\textup{Truthful yes answer})

\displaystyle \mathbf{P}(\textup{Truthful yes answer}) = 2 \mathbf{P}(\textup{Yes answer}) - \frac{1}{2}

We can replace the true probability \mathbf{P}(\textup{Yes answer}) above with our fraction of “Yes” responses from the survey, and the result is an estimate \hat{p} of \mathbf{P}(\textup{Truthful yes answer}). This estimate is unbiased, but has additional variance—beyond the usual variance caused by picking a finite random sample from the population of interest—introduced by the randomization mechanism.

With a bit of effort, one can calculate that the variance of the estimate is

\displaystyle \textup{Var}(\hat{p}) = \frac{3}{4n}

And via Chebyshev’s inequality, which bounds the likelihood that an estimator is far away from its expectation, we can craft a confidence interval and determine the needed sample sizes. Specifically, the estimate \hat{p} has additive error at most q with probability at most \textup{Var}(\hat{p}) / q^2. This implies that for a confidence of 1-c, one requires at least n \geq 3 / (4 c q^2) samples. For example, to achieve error 0.01 with 90 percent confidence (c=0.1), one requires 7,500 responses.

Horvitz’s randomization mechanism didn’t use coin flips. Instead they used an opaque box with red or blue colored balls which the respondent, who was in the same room as the surveyor, would shake and privately reveal a random color through a small window facing away from the surveyor. The statistical principle is the same. Horvitz and his associates surveyed the women about their opinions of the privacy protections of this mechanism. When asked whether their friends would answer a direct question about abortion honestly, over 80% either believed their friends would lie, or were unsure. [footnote: A common trick in survey methodology when asking someone if they would be dishonest is to instead ask if their friends would be dishonest. This tends to elicit more honesty, because people are less likely to uphold a false perception of the moral integrity of others, and people also don’t realize that their opinion of their friends correlates with their own personal behavior and attitudes. In other words, liars don’t admit to lying, but they think lying is much more common than it really is.] But 60% were convinced there was no trick involved in the randomization, while 20% were unsure and 20% thought there was a trick. This suggests many people were convinced that Horvitz’s randomization mechanism provided the needed safety guarantees to answer honestly.

Horvitz’s survey was a resounding success, both for randomized response as a method and for measuring abortion prevalence. [Abernathy70] They estimated the abortion rate at about 22 per 100 conceptions, with a distinct racial bias—minorities were twice as likely as whites to receive an abortion. Comparing their findings to a prior nationwide study from 1955—the so-called Arden House estimate—which gave a range of between 200,000 and 1.2 million abortions per year, Horvitz’s team estimated more precisely that there were 699,000 abortions in 1955 in the United States, with a reported standard deviation of about 6,000, less than one percent. For 1967, the year of their study, they estimated 829,000.

Their estimate was referenced widely in the flurry of abortion law and court cases that followed due to a surging public interest in the topic. For example, it is cited in the 1970 California Supreme Court opinion for the case Ballard v. Anderson, which concerned whether a minor needs parental consent to receive an otherwise legal abortion. [Ballard71, Roemer71] It was also cited in amici curiae briefs submitted to the United States Supreme Court in 1971 for Roe v. Wade, the famous case that invalidated most U.S. laws making abortion illegal. One such brief was filed jointly by the country’s leading women’s rights organizations like the National Organization for Women. Citing Horvitz for this paragraph, it wrote, [Womens71]

While the realities of law enforcement, social and public health problems posed by abortion laws have been openly discussed […] only within a period of not more than the last ten years, one fact appears undeniable, although unverifiable statistically. There are at least one million illegal abortions in the United States each year. Indeed, studies indicate that, if the local law still has qualifying requirements, the relaxation in the law has not diminished to any substantial extent the numbers in which women procure illegal abortions.

It’s unclear how the authors got this one million number (Horvitz’s estimate was 20% less for 1967), nor what they meant by “unverifiable statistically.” It may have been a misinterpretation of the randomized response technique. In any event, randomized response played a crucial role in providing a foundation for political debate.

Despite Horvitz’s success, and decades of additional research on crime, drug use, and other sensitive topics, randomized response mechanisms have been applied poorly. In some cases, the desired randomization is inextricably complex, such as when requiring a continuous random number. In these cases, a manual randomization mechanism is too complex for a respondent to use accurately. Trying to use software-assisted devices can help, but can also produce mistrust in the interviewee. See [Rueda16] for additional discussion of these pitfalls and what software packages exist for assisting in using randomized response. See [Fox16] for an analysis of the statistical differences between the variety of methods used between 1970 and 2010.

In other contexts, analogues to randomized response may not elicit the intended effect. In the 1950’s, Utah used death by firing squad as capital punishment. To avoid a guilty conscience of the shooters, one of five marksmen was randomly given a blank, providing him some plausible deniability that he knew he had delivered the killing shot. However, this approach failed on two counts. First, once a shot was fired the marksman could tell whether the bullet was real based on the recoil. Second, a 20% chance of a blank was not enough to dissuade a guilty marksman from purposely missing. In the 1951 execution of Elisio Mares, all four real bullets missed the condemned man’s heart, hitting his chest, stomach, and hip. He died, but it was neither painless nor instant.

Of many lessons one might draw from the botched execution, one is that randomization mechanisms must take into account both the psychology of the participants as well as the severity of a failed outcome.


  title = {{Randomized Response and Related Methods: Surveying Sensitive Data}},
  author = {James Alan Fox},
  edition = {2nd},
  year = {2016},
  doi = {10.4135/9781506300122},

  author = {Abernathy, James R. and Greenberg, Bernard G. and Horvitz, Daniel G.
  title = {{Estimates of induced abortion in urban North Carolina}},
  journal = {Demography},
  volume = {7},
  number = {1},
  pages = {19-29},
  year = {1970},
  month = {02},
  issn = {0070-3370},
  doi = {10.2307/2060019},
  url = {},

  author = {Stanley L. Warner},
  journal = {Journal of the American Statistical Association},
  number = {309},
  pages = {63--69},
  publisher = {{American Statistical Association, Taylor \& Francis, Ltd.}},
  title = {Randomized Response: A Survey Technique for Eliminating Evasive
           Answer Bias},
  volume = {60},
  year = {1965},

  title = {{Ballard v. Anderson}},
  journal = {California Supreme Court L.A. 29834},
  year = {1971},
  url = {},

  title = {{Motion for Leave to File Brief Amici Curiae on Behalf of Women’s
           Organizations and Named Women in Support of Appellants in Each Case,
           and Brief Amici Curiae.}},
  booktitle = {{Appellate Briefs for the case of Roe v. Wade}},
  number = {WL 128048},
  year = {1971},
  publisher = {Supreme Court of the United States},

  author = {R. Roemer},
  journal = {Am J Public Health},
  pages = {500--509},
  title = {Abortion law reform and repeal: legislative and judicial developments
  volume = {61},
  number = {3},
  year = {1971},

  title = {Chapter 10 - Software for Randomized Response Techniques},
  editor = {Arijit Chaudhuri and Tasos C. Christofides and C.R. Rao},
  series = {Handbook of Statistics},
  publisher = {Elsevier},
  volume = {34},
  pages = {155-167},
  year = {2016},
  booktitle = {Data Gathering, Analysis and Protection of Privacy Through
               Randomized Response Techniques: Qualitative and Quantitative Human
  doi = {},
  author = {M. Rueda and B. Cobo and A. Arcos and R. Arnab},

The Gadget Decomposition in FHE

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 based on matrix multiplication, and are conceptually much simpler. Even more recent FHE schemes build on GSW or use it as a core subroutine.

All of these schemes inject random noise into the ciphertext, and each homomorphic operation increases noise. Once the noise gets too big, you can no longer decrypt the message, and so every now and then you must apply a process called “bootstrapping” that reduces noise. It also tends to be the performance bottleneck of any FHE scheme, and this bottleneck is why FHE is not considered practical yet.

To help reduce noise growth, many FHE schemes like GSW use a technical construction dubbed the gadget decomposition. Despite the terribly vague name, it’s a crucial limitation on noise growth. When it shows up in a paper, it’s usually remarked as “well known in the literature,” and the details you’d need to implement it are omitted. It’s one of those topics.

So I’ll provide some details. The code from this post is on GitHub.

Binary digit decomposition

To create an FHE scheme, you need to apply two homomorphic operations to ciphertexts: addition and multiplication. Most FHE schemes admit one of the two operations trivially. If the ciphertexts are numbers as in RSA, you multiply them as numbers and that multiplies the underlying messages, but addition is not known to be possible. If ciphertexts are vectors as in the “Learning With Errors” scheme (LWE)—the basis of many FHE schemes—you add them as vectors and that adds the underlying messages. (Here the “Error” in LWE is synonymous with “random noise”, I will use the term “noise”) In LWE and most FHE schemes, a ciphertext hides the underlying message by adding random noise, and addition of two ciphertexts adds the corresponding noise. After too many unmitigated additions, the noise will grow so large it obstructs the message. So you stop computing, or you apply a bootstrapping operation to reduce the noise.

Most FHE schemes also allow you to multiply a ciphertext by an unencrypted constant A, but then the noise scales by a factor of A, which is undesirable if A is large. So you either need to limit the coefficients of your linear combinations by some upper bound, or use a version of the gadget decomposition.

The simplest version of the gadget decomposition works like this. Instead of encrypting a message m \in \mathbb{Z}, you would encrypt m, 2m, 4m, ..., 2^{k-1} m for some choice of k, and then to multiply A < 2^k you write the binary digits of A = \sum_{i=0}^{k-1} a_i 2^i and you compute \sum_{i=0}^{k-1} a_i \textup{Enc}(2^i m). If the noise in each encryption is E, and summing ciphertexts sums noise, then this trick reduces the noise growth from O(AE) to O(kE) = O(\log(A)E), at the cost of tracking k ciphertexts. (Calling the noise E is a bit of an abuse—in reality the error is sampled from a random distribution—but hopefully you see my point).

Some folks call the mapping \textup{PowersOf2}(m) = m \cdot (2^0, 2^1, 2^2, \dots, 2^{k-1}), and for the sake of this article let’s call the operation of writing a number A in terms of its binary digits \textup{Bin}(A) = (a_0, \dots, a_{k-1}) (note, the first digit is the least-significant bit, i.e., it’s a little-endian representation). Then PowersOf2 and Bin expand an integer product into a dot product, while shifting powers of 2 from one side to the other.

\displaystyle A \cdot m = \langle \textup{Bin}(A), \textup{PowersOf2}(m) \rangle

This inspired the following “proof by meme” that I can’t resist including.

Working out an example, if the message is m=7 and A = 100, k=7, then \textup{PowersOf2}(7) = (7, 14, 28, 56, 112, 224, 448, 896) and \textup{Bin}(A) = (0,0,1,0,0,1,1,0) (again, little-endian), and the dot product is

\displaystyle 28 \cdot 1 + 224 \cdot 1 + 448 \cdot 1 = 700 = 7 \cdot 2^2 + 7 \cdot 2^5 + 7 \cdot 2^6

A generalized gadget construction

One can generalize the binary digit decomposition to different bases, or to vectors of messages instead of a single message, or to include a subset of the digits for varying approximations. I’ve been puzzling over an FHE scheme that does all three. In my search for clarity I came across a nice paper of Genise, Micciancio, and Polyakov called “Building an Efficient Lattice Gadget Toolkit: Subgaussian Sampling and More“, in which they state a nice general definition.

Definition: For any finite additive group A, an Agadget of size w and quality \beta is a vector \mathbf{g} \in A^w such that any group element u \in A can be written as an integer combination u = \sum_{i=1}^w g_i x_i where \mathbf{x} = (x_1, \dots , x_w) has norm at most \beta.

The main groups considered in my case are A = (\mathbb{Z}/q\mathbb{Z})^n, where q is usually 2^{32} or 2^{64}, i.e., unsigned int sizes on computers for which we get free modulus operations. In this case, a (\mathbb{Z}/q\mathbb{Z})^n-gadget is a matrix G \in (\mathbb{Z}/q\mathbb{Z})^{n \times w}, and the representation x \in \mathbb{Z}^w of u \in (\mathbb{Z}/q\mathbb{Z})^n satisfies Gx = u.

Here n and q are fixed, and w, \beta are traded off to make the chosen gadget scheme more efficient (smaller w) or better at reducing noise (smaller \beta). An example of how this could work is shown in the next section by generalizing the binary digit decomposition to an arbitrary base B. This allows you to use fewer digits to represent the number A, but each digit may be as large as B and so the quality is \beta = O(B\sqrt{w}).

One commonly-used construction is to convert an A-gadget to an A^n-gadget using the Kronecker product. Let g \in A^w be an A-gadget of quality \beta. Then the following matrix is an A^n-gadget of size nw and quality \sqrt{n} \beta:

\displaystyle G = I_n \otimes \mathbf{g}^\top = \begin{pmatrix} g_1 & \dots & g_w & & & & & & & \\ & & & g_1 & \dots & g_w & & & & \\ & & & & & & \ddots & & & \\ & & & & & & & g_1 & \dots & g_w \end{pmatrix}

Blank spaces represent zeros, for clarity.

An example with A = (\mathbb{Z}/16\mathbb{Z}). The A-gadget is \mathbf{g} = (1,2,4,8). This has size 4 = \log(q) and quality \beta = 2 = \sqrt{1+1+1+1}. Then for an A^3-gadget, we construct

Now given a vector (15, 4, 7) \in \mathbb{A}^3 we write it as follows, where each little-endian representation is concatenated into a single vector.

\displaystyle \mathbf{x} = \begin{pmatrix} 1\\1\\1\\1\\0\\0\\1\\0\\1\\1\\1\\0 \end{pmatrix}

And finally,

To use the definition more rigorously, if we had to write the matrix above as a gadget “vector”, it would be in column order from left to right, \mathbf{g} = ((1,0,0), (2,0,0), \dots, (0,0,8)) \in A^{wn}. Since the vector \mathbf{x} can be at worst all 1’s, its norm is at most \sqrt{12} = \sqrt{nw} = \sqrt{n} \beta = 2 \sqrt{3}, as claimed above.

A signed representation in base B

As we’ve seen, the gadget decomposition trades reducing noise for a larger ciphertext size. With integers modulo q = 2^{32}, this can be fine-tuned a bit more by using a larger base. Instead of PowersOf2 we could define PowersOfB, where B = 2^b, such that B divides 2^{32}. For example, with b = 8, B = 256, we would only need to track 4 ciphertexts. And the gadget decomposition of the number we’re multiplying by would be the little-endian digits of its base-B representation. The cost here is that the maximum entry of the decomposed representation is 255.

We can fine tune this a little bit more by using a signed base-B representation. To my knowledge this is not the same thing as what computer programmers normally refer to as a signed integer, nor does it have anything to do with the two’s complement representation of negative numbers. Rather, instead of the normal base-B digits n_i \in \{ 0, 1, \dots, B-1 \} for a number N = \sum_{i=0}^k n_i B^i, the signed representation chooses n_i \in \{ -B/2, -B/2 + 1, \dots, -1, 0, 1, \dots, B/2 - 1 \}.

Computing the digits is slightly more involved, and it works by shifting large coefficients by -B/2, and “absorbing” the impact of that shift into the next more significant digit. E.g., if B = 256 and N = 2^{11} - 1 (all 1s up to the 10th digit), then the unsigned little-endian base-B representation of N is (255, 7) = 255 + 7 \cdot 256. The corresponding signed base-B representation subtracts B from the first digit, and adds 1 to the second digit, resulting in (-1, 8) = -1 + 8 \cdot 256. This works in general because of the following “add zero” identity, where p and q are two successive unsigned digits in the unsigned base-B representation of a number.

\displaystyle \begin{aligned} pB^{k-1} + qB^k &= pB^{k-1} - B^k + qB^k + B^k \\ &= (p-B)B^{k-1} + (q+1)B^k \end{aligned}

Then if q+1 \geq B/2, you’d repeat and carry the 1 to the next higher coefficient.

The result of all this is that the maximum absolute value of a coefficient of the signed representation is halved from the unsigned representation, which reduces the noise growth at the cost of a slightly more complex representation (from an implementation standpoint). Another side effect is that the largest representable number is less than 2^{32}-1. If you try to apply this algorithm to such a large number, the largest digit would need to be shifted, but there is no successor to carry to. Rather, if there are k digits in the unsigned base-B representation, the maximum number representable in the signed version has all digits set to B/2 - 1. In our example with B=256 and 32 bits, the largest digit is 127. The formula for the max representable integer is \sum_{i=0}^{k-1} (B/2 - 1) B^i = (B/2 - 1)\frac{B^k - 1}{B-1}.

max_digit = base // 2 - 1
max_representable = (max_digit 
    * (base ** (num_bits // base_log) - 1) // (base - 1)

A simple python implementation computes the signed representation, with code copied below, in which B=2^b is the base, and b = \log_2(B) is base_log.

def signed_decomposition(
  x: int, base_log: int, total_num_bits=32) -> List[int]:
    result = []
    base = 1 << base_log
    digit_mask = (1 << base_log) - 1
    base_over_2_threshold = 1 << (base_log - 1)
    carry = 0

    for i in range(total_num_bits // base_log):
        unsigned_digit = (x >> (i * base_log)) & digit_mask
        if carry:
            unsigned_digit += carry
            carry = 0

        signed_digit = unsigned_digit
        if signed_digit >= base_over_2_threshold:
            signed_digit -= base
            carry = 1

    return result

In a future article I’d like to demonstrate the gadget decomposition in action in a practical setting called key switching, which allows one to convert an LWE ciphertext encrypted with key s_1 into an LWE ciphertext encrypted with a different key s_2. This operation increases noise, and so the gadget decomposition is used to reduce noise growth. Key switching is used in FHE because some operations (like bootstrapping) have the side effect of switching the encryption key.

Until then!

Group Actions and Hashing Unordered Multisets

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. I couldn’t think of any at the time, and years later Kevin has provided me with a tidy example. I took the liberty of rephrasing his argument to be a bit simpler (I hope), but I encourage you to read Kevin’s post to see the reasoning in its original form.

Hashes are useful in programming, and occasionally one wants to hash an unordered set or multiset in such a way that the hash does not depend on the order the elements were added to the set. Since collection types are usually generic, one often has to craft a hash function for a set<T> or multiset<T> that relies on a hash function hash(t) of an unknown type T. To make things more efficient, rather than requiring one to iterate over the entire set each time a hash is computed, one might seek out a hash function that can be incrementally updated as new elements are added, and provably does not depend on the order of insertion.

For example, having a starting hash of zero, and adding hashes of elements as they are added (modulo 2^{64}) has this incremental order-ignorant property, because addition is commutative and sums can be grouped. XOR-ing the bits of the hashes is similar. However, both of these strategies have downsides.

For example, if you adopt the XOR strategy for a multiset hash, then any element that has an even quantity in the multiset will be the same as if it were not in the set at all (or if it were in the set with some other even quantity). This is because x XOR x == 0. On the other hand, if you use the addition approach, if an element hashes to zero, its inclusion in any set has no effect on the hash. In Java the integer hash is the identity, so zero would be undetectable as a member of a multiset of ints in any quantity. Less drastically, a multiset with all even counts of elements will always hash to a multiple of 2, and this makes it easier to find hash collisions.

A natural question arises: given the constraint that the hash function is accumulative and commutative, can we avoid such degenerate situations? In principle the answer should obviously be no, just by counting. I.e., the set of all unordered sets of 64-bit integers has size 2^{2^{64}}, while the set of 64-bit hashes has size merely 2^{64}. You will have many many hash collisions, and would need a much longer hash to avoid them in principle.

More than just “no,” we can characterize the structure of such hash functions. They impose an abelian group structure on the set of hashes. And due to the classification theorem of finite abelian groups, up to isomorphism (and for 64-bit hashes) that structure consists of addition on blocks of bits with various power-of-2 moduli, and the blocks are XOR’ed together at the end.

To give more detail, we need to review some group theory, write down the formal properties of an accumulative hash function, and prove the structure theorem.

Group actions, a reminder

This post will assume basic familiarity with group theory as covered previously on this blog. Basically, this introductory post defining groups and actions, and this followup post describing the classification theorem for commutative (abelian) groups. But I will quickly review group actions since they take center stage today.

A group G defines some abstract notion of symmetries in a way that’s invertible. But a group is really meaningless by itself. They’re only useful when they “act” upon a set. For example, a group of symmetries of the square acts upon the square to actually rotate its points. When you have multiple group structures to consider, it makes sense to more formally separate the group structure from the set.

So a group action is formally a triple of a group G, a set X, and a homomorphism f:G \to S_X, where S_X is the permutation group (or symmetry group) of X, i.e., the set of all bijections X \to X. The permutation group of a set encompasses every possible group that can act on X. In other words, every group is a subgroup of a permutation group. In our case, G and f define a subgroup of symmetries on X via the image of f. If f is not injective, some of the structure in G is lost. The homomorphism determines which parts of G are kept and how they show up in the codomain. The first isomorphism theorem says how: G / \textup{ker} f \cong \textup{im} f.

This relates to our hashing topic because an accumulative hash—and a nicely behaved hash, as we’ll make formal shortly—creates a group action on the set of possible hash values. The image of that group action is the “group structure” imposed by the hash function, and the accumulation function defines the group operation in that setting.

Multisets as a group, and nice hash functions

An appropriate generalization of multisets whose elements come from a base set X forms a group. This generalization views a multiset as a “counting function” T: X \to \mathbb{Z}. The empty set is the function that assigns zero to each element. A positive value of k implies the entry shows up in the multiset k times. And a negative value is like membership “debt,” which is how we represent inverses, or equivalently set difference operations. The inverse of a multiset T, denoted -T, is the multiset with all counts negated elementwise. Since integer-valued functions generally form a group under point-wise addition, these multisets also do. Call this group \textup{MSet}(X). We will freely use the suggestive notation T \cup \{ x \} to denote the addition of T and the function that is 1 on x and 0 elsewhere. Similarly for T - \{ x \}.

\textup{MSet}(X) is isomorphic to the free abelian group on X (because an instance of a multiset only has finitely many members). Now we can define a hash function with three pieces:

  • An arbitrary base hash function \textup{hash}: X \to \mathbb{Z} / 2^n \mathbb{Z}.
  • An arbitrary hash accumulator \textup{h}: \mathbb{Z} / 2^n \mathbb{Z} \times \mathbb{Z} / 2^n \mathbb{Z} \to \mathbb{Z} / 2^n \mathbb{Z}
  • A seed, i.e., a choice for the hash of the empty multiset s \in \mathbb{Z} / 2^n \mathbb{Z}

With these three data we want to define a multiset hash function h^*: \textup{MSet}(X) \to \mathbb{Z} / 2^n \mathbb{Z} recursively as

  • h^*(\left \{ \right \}) = s
  • h^*(T \cup \left \{ x \right \}) = h(h^*(T), \textup{hash}(x))
  • h^*(T - \left \{ x \right \}) = \dots

In order for the second bullet to lead to a well-defined hash, we need the property that the accumulation order of individual elements does not matter. Call a hash accumulator commutative if, for all a, b, c \in \mathbb{Z} / 2^n \mathbb{Z},

\displaystyle h(h(a,b), c) = h(h(a,c), b)

This extends naturally to being able to reorder any sequence of hashes being accumulated.

The third is a bit more complicated. We need to be able to use the accumulator to “de-accumulate” the hash of an element x, even when the set that gave rise to that hash didn’t have x in it to start.

Call a hash accumulator invertible if for a fixed hash z = \textup{hash}(x), the map a \mapsto h(a, z) is a bijection. That is, accumulating the hash z to two sets with different hashes under h^* will not cause a hash collision. This defines the existence of an inverse map (even if it’s not easily computable). This allows us to finish the third bullet point.

  • Fix z = \textup{hash}(x) and let g be the inverse of the map a \mapsto h(a, z). Then h^*(T - \left \{ x \right \}) = g(h^*(T))

Though we don’t have a specific definition for the inverse above, we don’t need it because we’re just aiming to characterize the structure of this soon-to-emerge group action. Though, in all likelihood, if you implement a hash for a multiset, it should support incremental hash updates when removing elements, and that formula would apply here.

This gives us the well-definition of h^*. Commutativity allows us to define h^*(T \cup S) by decomposing S arbitrarily into its constituent elements (with multiplicity), and applying h^*(T \cup \{ x \}) or h^*(T - \{ x \}) in any order.

A group action emerges

Now we have a well-defined hash function on a free abelian group.

\displaystyle h^*: \textup{MSet}(X) \to \mathbb{Z} / 2^n \mathbb{Z}

However, h^* is not a homomorphism. There’s no reason hash accumulation needs to mesh well with addition of hashes. Instead, the family of operations “combine a hash with the hash of some fixed set” defines a group action on the set of hashes. Let’s suppose for simplicity that h^* is surjective, i.e., that every hash value can be achieved as the hash of some set. Kevin’s post gives the more nuanced case when this fails, and in that case you work within S_{\textup{im}(h^*)} instead of all of S_{\mathbb{Z} / 2^n \mathbb{Z}}.

The group action is defined formally as a homomorphism

\displaystyle \varphi : \textup{MSet}(X) \to S_{\mathbb{Z} / 2^n \mathbb{Z}}

where \varphi(T) is the permutation a \mapsto h(a, h^*(T)). Equivalently, we start from a, pick some set S with h^*(S) = a, and output h^*(T \cup S).

The map \varphi is a homomorphism. The composition of two accumulations is order-independent because h is commutative. This is how we view h as “the binary operation” in \textup{im} \varphi, because combining two permutations a \mapsto h(a, h^*(T)) and a \mapsto h(a, h^*(S)) is the permutation a \mapsto h(a, h^*(S \cup T)).

And now we can apply the first isomorphism theorem, that

\displaystyle \textup{MSet}(X) / \textup{ker} \varphi \cong \textup{im} \varphi \subset S_{\mathbb{Z} / 2^n \mathbb{Z}}

This is significant because any quotient of an abelian group is abelian, and this quotient is finite because S_{\mathbb{Z} / 2^n \mathbb{Z}} is finite. This means that the group \textup{im} \varphi is isomorphic to

\displaystyle \textup{im} \varphi \cong \bigoplus_{i=1}^k \mathbb{Z}/2^{n_i} \mathbb{Z}

where n = \sum_i n_i, and where the operation in each component is the usual addition modulo n_i. The i-th summand corresponds to a block of n_i bits of the hash, and within that block the operation is addition modulo 2^{n_i}. Here the “block” structure is where XOR comes in. Each block can be viewed as a bitmask with zeros outside the block, and two members are XOR’ed together, which allows the operations to apply to each block independently.

For example, the group might be \mathbb{Z} / 2^{4} \mathbb{Z} \times \mathbb{Z} / 2^{26} \mathbb{Z}\times \mathbb{Z} / 2^{2} \mathbb{Z} for a 32-bit hash. The first block corresponds to 32-bit unsigned integers whose top 4 bits may be set but all other bits are zero. Addition is done within those four bits modulo 16, leaving the other bits unchanged. Likewise, the second component has the top four bits zero and the bottom two bits zero, but the remaining 26 bits are summed mod 2^{24}. XOR combines the bits from different blocks.

In one extreme case, you only have one block, and your group is just \mathbb{Z} / 2^n \mathbb{Z} and the usual addition combines hashes. In the other extreme, each bit is its own block, your group is (\mathbb{Z} / 2 \mathbb{Z})^n, the operation is a bitwise XOR.

Note, if instead of 2^n we used a hash of some other length m, then in the direct sum decomposition above, m would be the product of the sizes of the components. The choice m = 2^n maximizes the number of different structures you can have.

Implications for hash function designers

Here’s the takeaway.

First, if you’re trying to design a hash function that avoids the degeneracies mentioned at the beginning of this article, then it will have to break one of the properties listed. This could happen, say, by maintaining additional state.

Second, if you’re resigned to use a commutative, invertible, accumulative hash, then you might as well make this forced structure explicit, and just pick the block structure you want to use in advance. Since no clever bit shifting will allow you to outrun this theorem, you might as well make it simple.

Until next time!