SMAUG-T is an efficient post-quantum key encapsulation mechanism (KEM). It is the winner of Korean PQC Competition.
SMAUG-T uses a Hamming Weight Sampler $HWT_h$ to sample secret polynomial vectors $s, r$ with hamming weight $h_s$ and $h_r$ respectively. The rationale behind $HWT_h$ is summarized in Section 3.2.2 Figure 2 of the official documentation https://github.com/hmchoe0528/SMAUG-T_public/blob/main/document/SMAUG-T_spec_24.03_v3.0.1.pdf
Our hamming weight sampler, HWTh , is a hybrid of the SampleInBall algorithm in Dilithium [31] and the CWW (constant weight word) sampler in BIKE [56], which have a constant running time. However, when applying the SampleInBall sampling from BIKE directly, there was a need to reduce the sampling error inevitably arising from the Fisher-Yates Shuffle. Therefore, we eliminate the cause of this deviation by using division operations and a rejection technique.
1 void hwt(uint8_t *res, uint8_t *cnt_arr, const uint8_t *input, const size_t input_size, const uint16_t hmwt) {
2 uint32_t pos = 0, div = 0, remain = 0;
3 uint32_t buf[SHAKE256_RATE * 2] = {0};
4 uint8_t xof_block = (hmwt == HS) ? HS_XOF : HR_XOF;
5 keccak_state state;
6 shake256_init(&state);
7 shake256_absorb_once(&state, input, input_size);
8 shake256_squeezeblocks((uint8_t *)buf, xof_block, &state);
9
10 for (int i = 0; i < xof_block * 32; i++) {
11 uint32_t deg = buf[i];
12 div = 0xffffffff / (DIMENSION - hmwt + pos + 1);
13 remain = 0xffffffff - remain * (DIMENSION - hmwt + pos + 1);
14 remain++;
15 deg = deg / div;
16 if (((0xffffffff - remain) > deg) && pos < hmwt) {
17 res[DIMENSION - hmwt + pos] = res[deg];
18 res[deg] =
19 ((buf[(xof_block * 32 + (i >> 4))] >> (i & 0x0f)) & 0x02) - 1;
20 pos++;
21 }
22 }
We do have a few questions regarding this code:
Q1 > Till now I have understood that deg in [0, 2**32-1]
is scaled such that it lies in the range 0 <= deg <= DIMENSION-hmwt+pos+1
. It is not clear to me why $2^{32} - 1$ is used instead of $2^{32}$? For example, if we want to scale number $x \in [0,9]$ to $[0,3]$ we will use $round((4/10)*x)$
Q2> Line 16 in the code above: if (((0xffffffff - remain) > deg)
. It is not entirely clear the purpose of the inequality used here.