This post hopefully makes reading this paper easier.
In group-based cryptography, we often find ourselves working over the ring where is most often a prime or a product of a few large primes (in the setting of composite-order groups). Either way, most elements in the ring are invertible — a fact that is quite convenient for constructing knowledge extractors in -protocols and performing polynomial interpolation.
In lattice-based cryptography, however, our playground has been switched to , the ring of integers of the -th cyclotomic field, which we call a cyclotomic ring for short. After some experimentation, one can be easily convinced that most elements of are not invertible over , i.e. they are not units. Furthermore, even if we pick a modulus such that most elements in are invertible over , the inverses of short elements are often not short. This issue makes many techniques that we take for granted in group-based cryptography inapplicable in the lattice setting.
Long story short, suppose we have a set , which could be the challenge set of a -protocol or the set of evaluation points of a Shamir secret sharing scheme. Let be any -subset of . It would be great if we can solve the following (dual) Vandermonde systems
over for given some and a vector . Here, the matrix is the Vandermonde matrix defined by the set . That is, if , then
The element in the above equations, called the slack, is a measure of how good the solution is (if it exists). On one hand, we want (the norm of) to be as close to as possible. On the other hand, we would like the size to be as large as possible since it is inversely-proportional to the soundness error of the -protocol using as a challenge set, and equals to the number of parties to whom we can share our secret. (We might want to be large for secret sharing as well as it corresponds to the recovery threshold.)
Motivated by the above, we define the notion of -subtractive set as a sufficient condition of the solvability of the above (dual) Vandermonde systems. We say that a set is -subtractive, if for any -subset , it holds that for all . It is a sufficient condition in the sense that, if a set is -subtractive, then any (dual) Vandermonde system defined by the slack , any target vector , and any -subset is solvable over .
Note that in the special case where is invertible over for any distinct , then is a -subtractive set for any . In this case we simply call a subtractive set.
Some Math Background and Intuition
In the above definition of -subtractive sets, the notation denotes the ideal generated by the element . That is, . Another way of seeing is that it contains all the elements in which are divisible by . So, saying that is the same as saying that is divisible by .
Much of the results presented in this work are ultimately due to the presence or absence of certain ideals in . To get a more concrete feeling about the ideals in , the following observation might be useful.
We observe that, over , the ring of rational integers, the element is one of the two smallest primes (with the other being ). Another way of saying this is that is the “smallest” prime ideal, where the “smallness” is measured by the algebraic norm which measures the number of cosets of , which is . Since is a rational prime, it would be hopeless to find a large -subtractive set over , since only a handful of elements, and , divide .
The situation is quite different in when is a power of . There, the ideal is not prime but actually splits completely into factors. Indeed, we have
That is to say, there are quite a lot of elements in that divide , which is a good start.
Subtractive Sets over Prime-Power Cyclotomic Rings
Unlike in the paper, we first deal with the easy case. That is to present subtractive sets over prime-power cyclotomic rings, i.e. where is a power of a prime . These sets are simply
where . Note that is of size , and is therefore most interesting when and .
Although the proof of the above claim is straightforward, I find it somewhat cute and plausibly insightful. Therefore I decided to include it here.
First, we notice that for , the element
is a unit. Indeed, it is called a cyclotomic unit and its inverse is given by
Next, we notice that can be written as a prefix sum of the sequence of powers of . Consequently, for , we have
which is invertible.
-Subtractive Sets over Power-of- Cyclotomic Rings
If all the world cares about is prime-power cyclotomic rings, then we would have been done. However, power-of- cyclotomic rings are more preferable in implementations due to convenient tools such as the number theoretic transform (NTT). To be clear, these rings are where is a power of .
For the purpose of constructing lattice-based Bulletproof over power-of- cyclotomic rings, we are interested in constructing large -subtractive sets over . In this blog post, we pick as an example, and prove that
is -subtractive. Note that in the above I wrote for .
First, we note that we get the element in the set for free, since all other elements are units. It therefore suffices to prove that
is -subtractive. To this end, consider any -subset
where we assume without loss of generality that
We want to show that
To do this, we first note that
since is a unit. Next, by some routine calculation, we can see that
where denotes the even part of , i.e. the largest power of which divides . To proceed, we perform some more routine calculation to be convinced that
Finally, we observe that and therefore
Impossibility of Large -Subtractive Sets
We conclude this blog post by showing that one cannot find -subtractive sets that are much better than those constructed above.
For the impossibility result, it would be convenient to introduce the notion of weak -subtractive sets, which are sets such that, for any -subset , it holds that . Here, the set is defined as
and is the ideal generated by the elements in the set . From the definitions of (weak) -subtractive sets, one can immediately see that an -subtractive set is also weakly -subtractive. Therefore, if we can rule out the existence of certain weakly -subtractive sets, we would also be able to rule out the existence of certain -subtractive sets.
Power-of-2 Cyclotomic Rings
We first consider power-of- cyclotomic rings where is a power of . Suppose that is a prime (which is called a Fermat prime, with known examples being , , , ), then splits into factors each having algebraic norm . That is, each factor of has cosets.
Fix one of these factors . Suppose is a weakly -subtractive set of size greater than , we can partition such that each subset contains elements belonging to the same coset of , with one of the subset containing at least elements by the pigeonhole principle. However, since all elements in belong to the same coset of , we have . Since is weakly -subtractive, we have and hence . This however is a contradiction because is clearly not in (since the latter has norm which is coprime with ).
From the above, we conclude that, for any , it is impossible to construct a family (parameterised by ) of -subtractive sets each of size greater than . We note that, however, this result only rules out families of constructions but not individual constructions. That is, it might still happen that there exists a -subtractive set of size in the -th cyclotomic ring.
Prime-Power Cyclotomic Rings
We finish by considering prime-power cyclotomic rings where is a power of a prime . Here, we notice that the ideal has algebraic norm — it has cosets — and . Thus, by the same argument as above, we can conclude that there is no subtractive set of size greater than over prime-power cyclotomic rings. In other words, the constructions that we gave above are in a sense optimal.
Last Updated on 11/07/2022.