3
$\begingroup$

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

enter image description here

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 $.)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Rory
    Commented Mar 21, 2023 at 12:00
  • $\begingroup$ 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. $\endgroup$
    – swineone
    Commented Mar 21, 2023 at 12:49
  • $\begingroup$ 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). $\endgroup$
    – Rory
    Commented Mar 22, 2023 at 13:09
  • $\begingroup$ @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. $\endgroup$
    – yoyo
    Commented Mar 22, 2023 at 17:37
  • $\begingroup$ @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. $\endgroup$
    – swineone
    Commented Mar 22, 2023 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.