Score:3

Crypto

CRYSTALS-Dilithium - How do the supporting algorithms work?

Rory

3/21/24, 9:48 AM

I am studying the Dilithium signature from Ducas et al's CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme.

Wanting to understand how the supporting algorithms work together, I am trying to work out and visualize an example by hand. If I understand correctly we have the HighBits and LowBits algorithms calling the Decompose algorithm. For instance, how the $ HighBits $ algorithm is called in during $ Sign(sk, M) $:

$$ \vec{w_1} := HighBits_q(\vec{w}, 2\gamma_2) $$

I have tried looking at $ \vec{w} $ as a vector in the ring $ \mathbb{Z_q}[X] / ( X^n + 1 ) $ where the algorithm uses the coefficients for the polynomials as $r$ in the supporting algorithms.

I have tried using $ n = 256 $ and $ q = 23 $ and as far as $\gamma_2$ and the alpha value I am not sure what to use.

Any thoughts or ideas on intuition on how to work this out for concrete values (and what values to use) and see how the algorithms work together would be greatly appreciated. :)

(Also, curious if anyone knows why $ \gamma_2 $ is defined as $ \gamma_1 / 2 $ but when $ \gamma_2 $ is used it is always used as $ 2\gamma_2 $.)

318

1 + 0

quantum-cryptography

lattice-crypto

modular-arithmetic

dilithium

Score:3

Crypto

swineone

3/21/24, 11:49 AM

These algorithms are described in the beginning of section 2.4 (and by the way, you might want to use an updated version -- I believe this one is the latest).

Decompose works basically like writing a number in a given base (like binary, decimal, hexadecimal, etc.), specifically base $\alpha$. However, unlike conventional base conversion, it uses a center-balanced representation for the least-significant "digit" stored in $r_0$. It is applied to all elements in the vector. Decompose thus returns $r_1 \alpha + r_0$, and then HighBits and LowBits simply return the most-significant "digit" ($r_1$) and the least-significant digit ($r_0$), respectively.

As for $q$, not sure where you got 23 from. All parameters, including $q = 2^{23} - 2^{13} + 1 = 8380417$, $\gamma_1$ and $\gamma_2$, are found in Table 2 in page 15 of the updated specification. The latter two change from one security level to the other.

+ 6

Rory

3/21/24, 12:00 PM

Thank you for the response! I understand that the parameters from the table works. However, I am wanting to do this by hand for smaller numbers to explore how the algorithms interact. Do you have any ideas for a small prime $q$ and value for $\alpha$ as well as a way of thinking of $r$ in the $Decompose$ algorithm?

swineone

3/21/24, 12:49 PM

First of all, I suggest rereading my explanation, especially the part about the algorithm being similar to a base conversion. The value of $\alpha$ is taken as $2 \gamma_2$ in lines 16 and 20 of the Sign algorithm. As you can see in table 2, $\gamma_2$ is of the form $(q - 1)/k$ for different $k$s depending on security levels. You could try to generate smaller parameters of a similar form, or just use a calculator such as PARI/GP or SageMath to work with the full parameters.

Rory

3/22/24, 1:09 PM

Hi! I understand how this works, but as a theoretical mathematician I was looking for a way to conceptualise this manually, not running code. Coding is a skillset I do not have nor is it relevant for the way I am studying the signature (of course would I like to understand it, but it is not super helpful right now).

yoyo

3/22/24, 5:37 PM

@Rory (Some unsolicited advice.) Working out small examples by hand and writing a small program to work out examples are the same thing. If Euler or Gauss had had a computer, it'd be blazing hot all day long. Depending on your current and planned status in mathematics (student, researcher etc.) and your area (anything with a potentially computational bent, number theory, algebraic geometry, some aspects of geometry/topology, combinatorics, PDE, etc.), I would recommend adding programming to your skillset.

swineone

3/22/24, 6:43 PM

@yoyo absolutely correct and excellent advice. Moreover, my suggestion was to use PARI/GP and SageMath essentially as calculators with fancier “buttons” available, which by the way you do not even need to use for the problem at hand. At no point would you need to declare a function, use a programming construct like `if`, `for`, `while`, etc. It’s literally a fancy calculator. But I’ve learned you can only take a horse to water, you can’t make the horse drink it.

Rory

3/24/24, 3:07 PM

@yoyo and @ swineone thank you for the advice (unsolicited or not). Ended up doing it both using python and by hand (the horse is drinking water ;) ). I guess I should have been more clear in my question. Wanted to study the algorithm for more tangible values than those introduced in the papers and had a hard time doing this.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: CRYSTALS-Dilithium - How do the supporting algorithms work?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.